We study the subgraph matching problem, which is to find all subgraph isomorphisms of a given pattern graph p in a data graph G. Traditional approaches typically use a backtracking search approach or worst-case optimal join, both of which directly operate on p. In this paper, we revisit the tree decomposition based approach. For a complex pattern graph p , we find its optimal tree decomposition T based on the fractional hypertree width, where a node in T represents a subgraph of p , which is also called a bag, and a node in p may appear in multiple bags in T. The tree decomposition based approach initially computes and materializes the matches of subgraphs specified by the bags, then treats these matches as new relations and employs an acyclic join to compute the matches of p itself. However, previous approaches fail to integrate the tree decomposition with effective join attribute orders, and conversely, previous join attribute ordering approaches do not consider the need to share computations in multiple bags. Additionally, the materialization strategies in previous tree decomposition based approaches can lead to high computation costs. In this paper, we propose a new subgraph matching algorithm ASDMatch (Adaptive Shared Decomposition-based matching). We propose a new dynamic programming approach that finds optimal attribute orders for each bag based on a cost model that incorporates the computation sharing. Furthermore, we introduce a new adaptive materialization strategy to reduce the computation cost. We confirmed that our ASDMatch outperforms state-of-the-art algorithms and can process many challenging queries that previous algorithms can not finish within the time limit.

Join order selection has been widely studied, and the widely used algorithm to find the optimal join order is Dynamic Programming (DP). However, it is also known that the existing DP algorithms cannot deal with the so-called interesting order (e.g., sort order), or the algorithm to consider sort order together with joins will violate the optimal substructure behind DP. As a result, it is difficult for DBMSs to find the optimal join order given sort orders, as it comes with extremely high overhead. In this paper, we study a novel DP algorithm to find the optimal join order by taking sort orders into consideration. We call it a join&sort orders selection problem, which is to minimize the total join&sort cost to process a join query. This problem is challenging, because both the join order selection and the sort order selection for a given join-tree are known to be NP-hard. In addition, join&sort orders are dependent in the sense that the change of one order affects the selection of the other. We show that the optimal substructure exists in dealing with join&sort orders selection by DP under some simple condition, which we call $$\varOmega $$ -condition. The $$\varOmega $$ -Condition is not a condition to restrict join queries to optimize, but is a condition that allows us to find the optimal for any join queries. We present DP algorithms for bushy and linear join trees, discussing the pruning techniques and the complexity of the algorithms. We conduct extensive experimental studies to show the efficiency and robustness of our approach.

Conjunctive queries ( CQ s) have been widely used in database systems in which acyclic CQ s can be computed efficiently, whereas cyclic CQ s may not. Here, a CQ is acyclic if its hypergraph representation H is acyclic. In order to find a class of CQ s that are "mildly cyclic", hypertree decompositions (HDs) have been studied. The quality of such HDs is by the so-called hypertree width. The class of acyclic queries is the queries whose hypertree width is 1, and a mildly cyclic CQ can be processed efficiently if its hypertree width is bounded. There are several HDs, such as tree decomposition (TD), generalized hypertree decomposition (GHD), fractional hypertree decomposition (FHD), as well as hypertree decomposition (HD). The minimum hypertree width by FHD is the smallest among all, and it is NP-complete to check if the minimum hypertree width by FHD exists for a given hypertree width at most k. In the literature, there is no dynamic programming ( DP ) algorithm or branch-&-bound algorithm reported to compute FHD. In this paper, we show that there is a DP algorithm for FHD, and we give a branch-&-bound algorithm based on our DP algorithm to compute FHD with upper/lower bounds. We confirm the effectiveness and efficiency of our algorithm by testing all 3,648 hypergraphs given in a benchmark for HDs, and we also confirm our approach in query evaluation in real database systems.

Abstract Deep Learning (DL) has been widely used in many applications, and its success is achieved with large training data. A key issue is how to provide a DL solution when there is no large training data to learn initially. In this paper, we explore a meta-learning approach for a specific problem, subgraph isomorphism counting, which is a fundamental problem in graph analysis to count the number of a given pattern graph, p , in a data graph, g , that matches p . There are various data graphs and pattern graphs. A subgraph isomorphism counting query is specified by a pair, ( g , p ). This problem is NP-hard and needs large training data to learn by DL in nature. We design a Gaussian Process (GP) model which combines Graph Neural Network with Bayesian nonparametric, and we train the GP by a meta-learning algorithm on a small set of training data. By meta-learning, we can obtain a generalized meta-model to better encode the information of data and pattern graphs and capture the prior of small tasks. With the meta-model learned, we handle a collection of pairs ( g , p ), as a task, where some pairs may be associated with the ground-truth, and some pairs are the queries to answer. There are two cases. One is there are some with ground-truth (few-shot), and one is there is none with ground-truth (zero-shot). We provide our solutions for both. In particular, for zero-shot, we propose a new data-driven approach to predict the count values. Note that zero-shot learning for our regression tasks is difficult, and there is no hands-on solution in the literature. We conducted extensive experimental studies to confirm that our approach is robust to model degeneration on small training data, and our meta-model can fast adapt to new queries by few-shot and zero-shot learning.

The adoption of temporal expressions into SQL:2011 has continuously driven the extensions of temporal support in relational database systems (a.b.a. RDBMSs). In this paper, we present T-SQL, a lightweight yet efficient built-in temporal implementation in RDBMSs. T-SQL completely relies on multi-version concurrency control (MVCC) which is widely adopted in RDMBSs to manage temporal data. For temporal data, current records are maintained in legacy databases, and historical records, i.e., previoius versions of current records (if any), which used to be periodically reclaimed are separately maintained in KV stores. To enable temporal query processing under SQL:2011, we extend the query engine in legacy RDBMSs to support query processing over either historical records or current records or both. Further, regarding temporal data are ever-increasing, we propose various optimizations to reduce the storage overhead of KV stores while keeping efficient query performance. We elaborate on a publicly available implementation, on how to integrate T-SQL into both centralized and distributed RDBMSs. We conduct extensive experiments on both YCSB and TPC-series benchmarks by comparing T-SQL with other temporal database systems. The results show that T-SQL is both lightweight and efficient.

Deep Learning (DL) has achieved great success in many real applications. Despite its success, there are some main problems when deploying advanced DL models in database systems, such as hyper-parameters tuning, the risk of overfitting, and lack of prediction uncertainty. In this paper, we study a lightweight and accurate cardinality estimation for SQL queries, which is also uncertainty-aware. By lightweight, we mean that we can train a DL model in a few seconds. With uncertainty ensured,it becomes possible to update the estimator to improve its prediction in areas with high uncertainty.The approach we explore is different from the direction of deploying sophisticated DL models as cardinality estimators in database systems. We employ Bayesian deep learning (BDL), which serves as a bridge between Bayesian inference and deep learning. The prediction distribution by BDL provides principled uncertainty calibration for the prediction. In addition, when the network width of a BDL model goes to infinity, the model performs equivalent to Gaussian Process (GP). This special class of BDL, known as Neural Network Gaussian Process (NNGP), inherits the advantages of Bayesian approach while keeping universal approximation of neural networks, and can utilize a much larger model space to model distribution-free data as a nonparametric model. We show our NNGP estimator achieves high accuracy, is built fast, and is robust to query workload shift, in our extensive performance studies by comparing with existing learned estimators. We also confirm the effectiveness of NNGP by integrating it into PostgreSQL.