Algebraic optimization of recursive queries

Over the past few years, much attention has been paid to deductive databases. They offer a logic-based interface, and allow formulation of complex recursive queries. However, they do not offer appropriate update facilities, and do not support existing applications. To overcome these problems an SQL-like interface is required besides a logic-based interface.

In the PRISMA project we have developed a tightly-coupled distributed database, on a multiprocessor machine, with two user interfaces: SQL and PRISMAlog. Query optimization is localized in one component: the relational query optimizer. Therefore, we have defined an eXtended Relational Algebra that allows recursive query formulation and can also be used for expressing executable schedules, and we have developed algebraic optimization strategies for recursive queries. In this paper we describe an optimization strategy that rewrites regular (in the context of formal grammars) mutually recursive queries into standard Relational Algebra and transitive closure operations. We also describe how to push selections into the resulting transitive closure operations.

The reason we focus on algebraic optimization is that, in our opinion, the new generation of advanced database systems will be built starting from existing state-of-the-art relational technology, instead of building a completely new class of systems.     

Decidable containment of recursive queries

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.     

Evaluating recursive queries in distributed databases

The execution of logic queries in a distributed database environment is studied. Conventional optimization strategies, such as the early evaluation of selection conditions and the clustering of processing to manipulate and exchange large sets of tuples, are redefined in view of the additional difficulties due to logic queries, in particular to recursive rules. In order to allow efficient processing of these logic queries, several program transformation techniques that attempt to minimize distribution costs based on the idea of semijoins and generalized semijoins in conventional databases are presented. Although local computation of semijoins is not possible for the general case, classes of programs are indicated for which these transformations succeed in producing set-oriented computation. Processes evaluating the recursive program in a distributed network are described, and an efficient method for testing the termination of the computation is developed. The approach is compared with sequential as well as dataflow-oriented evaluation     

Processing recursive queries on transputers

There is a perceived need within the database community to extend the traditional relational database systems so as to accommodate applications which are deductive in nature. One major problem involved in such an extension is the efficient processing of recursive queries. To this end, parallel processing is expected to play an important role. While substantial work has been done in devising strategies for processing recursive queries in parallel, it is perhaps surprising that little has been reported on the implementation and the run-time performance of these strategies. In the paper we report our experience of implementing a pipelined evaluation strategy on transputers. A wide range of queries, database structures and architectural configurations are considered as benchmarks in this study. The performance is studied in terms of both speed-up factors and communication costs. The experimental results show the potential of processing recursive queries in parallel, and provide insight into the usefulness of using transputers for such applications.     

Evaluation of queries based on the extended relational calculi

An efficient database search algorithm is presented. Four major enhancements on the preceding works have been made. They are (1) relational calculus is extended to enable processing an arbitrary logical function defined on one or more relations, (2) a set of elementary operations which are similar to but are more efficient in processing compound search conditions than the relational algebra is used, (3) the target list processing is completely separated from the search process, and (4) sequential collation procedure is fully utilized to deal with conditions of a certain type defined on two or more relations. The algorithm is composed of two parts: syntactical transformation of the given extended relational calculus and the search execution. Various optimization issues are integrated into these two parts.     

Efficient evaluation for a subset of recursive queries

We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluation of the transformed program the bindings will be used to restrict the set of database facts consulted.     

Linearization of nonlinear recursive rules

The problem of converting a simple nonlinear recursive logic query into an equivalent linear one is considered. A general method is given to transform a nonlinear rule into a sequence of linear ones. For efficient processing it is necessary to convert a nonlinear rule into a single linear rule. For such a conversion, a necessary and sufficient condition is provided for a type of doubly recursive rule to be equivalent to the resulting linear rule. It is also shown that a restricted type of higher order recursive rule is equivalent to the linear rule obtained by its conversion     

Proof rules for recursive procedures

Four proof rules for recursive procedures in a Pascal-like language are presented. The main rule deals with total correctness and is based on results of Gries and Martin. The rule is easier to apply than Martin's. It is introduced as an extension of a specification format for Pascal-procedures, with its associated correctness and invocation rules. It uses well-founded recursion and is proved under the postulate that a procedure is semantically equal to its body.This rule for total correctness is compared with Hoare's rule for partial correctness of recursive procedures, in which no well-founded relation is needed. Both rules serve to prove correctness, i.e. sufficiency of certain preconditions. There are also two rules for proving necessity of preconditions. These rules can be used to give formal proofs of nontermination and refinement. They seem to be completely new.     

Classification and compilation of linear recursive queries indeductive databases

The authors present a graph model which is powerful in classifying and compiling linear recursive formulas in deductive databases. The graph model consists of two kinds of graphs: I-graph and resolution graph. Essential properties of a recursive formula can be extracted from its I-graph, and the compiled formula and the query evaluation plan of the recursive formulas can be determined from its resolution graph. It is demonstrated that based on the graph model all the linear recursive formulas can be classified into a taxonomy of classes and each class shares common characteristics in query compilation and query processing. The compiled formulas and the corresponding query evaluation plans can be derived based on the study of the compilation of each class     

Graphic representation of linear recursive rules

Recursive rules are important to deductive databases. A recursive rule may be compiled into expansions. In this article, the variable-predicate graph (V-P graph) based on the α-graph by loannidis is developed to represent linear recursive function-free rules and their expansions. A naming convention is used for variables and predicates in the V-P graph so that all equivalent recursive rules may map into a unique V-P graph. We propose a graphic construction method (g.c.m.) which derives V-P graphs of expansions directly from the V-P graph of the original rule. This graphic representation reveals some expansion properties not easy to obtain otherwise. We also propose a rule rewriting method in the context of deductive database so that constants, repeated distinguished variables, and/or repeated recursive variables may be removed from recursive rules.     

On the bottom—up evaluation of recursive queries

In this article, we present an optimal bottom-up evaluation method for handling both linear and nonlinear recursion. Based on the well-known magic-set method, we develop a technique: labeling to record the cyclic paths during the execution of the first phase of the magic-set method and suspending the computation for the cyclic data in the second phase to avoid the redundant evaluation. Then we postpone this computation to an iteration process (the third phase) which evaluates the remaining answers only along each cyclic path. In this way, we can guarantee the completeness. In addition, for a large class of programs we further optimize our method by elaborating the iteration process and generating most answers for each cyclic path directly from the intermediate results instead of evaluating them by performing algebraic operations (after some of the answers for the first cyclic path are produced). Because the cost of generating an answer is much less than that of evaluating an answer, this optimization is significant. © 1996 John Wiley & Sons, Inc.     

递推算法在扩展约瑟夫环问题中的应用

对约瑟夫环问题进行扩展,并将递推算法和静态链表的思想用于解决扩展问题。得到了扩展问题的递推表达式,给出了求解扩展问题的算法,其时间复杂度为O（n）。运行实例表明,与常规的模拟算法相比,大大提高了求解问题的速度。     

关系数据库中分组查询的模糊扩展及去模糊机制

当前关系数据库模糊查询的研究中,涉及到分组查询having子句中的模糊条件或相对语言量词的较少。在模糊理论的基础上对having子句进行了模糊扩展,并利用模糊集合隶属函数的α截集将模糊的having子句转化为标准的SQL语句,因此可以利用RDBMS对记录进行筛选,保证了查询的效率。利用模糊集合基数的非模糊表示法来计算带量词的having语句,计算简单,结果简洁。     

Inference rules for proving the equivalence of recursive procedures

Inspired by Hoare’s rule for recursive procedures, we present three proof rules for the equivalence between recursive programs. The first rule can be used for proving partial equivalence of programs; the second can be used for proving their mutual termination; the third rule can be used for proving the equivalence of reactive programs. There are various applications to such rules, such as proving equivalence of programs after refactoring and proving backward compatibility.     

An extended class of scale-invariant and recursive scale spacefilters

Explores how the functional form of scale space filters is determined by a number of a priori conditions. In particular, if one assumes scale space filters to be linear, isotropic convolution filters, then two conditions (viz. recursivity and scale-invariance) suffice to narrow down the collection of possible filters to a family that essentially depends on one parameter which determines the qualitative shape of the filter. Gaussian filters correspond to one particular value of this shape-parameter. For other values the filters exhibit a more complicated pattern of excitatory and inhibitory regions. This might well be relevant to the study of the neurophysiology of biological visual systems, for recent research shows the existence of extensive disinhibitory regions outside the periphery of the classical center-surround receptive field of LGN and retinal ganglion cells (in cats). Such regions cannot be accounted for by models based on the second order derivative of the Gaussian. Finally, the authors investigate how this work ties in with another axiomatic approach of scale space operators which focuses on the semigroup properties of the operator family. The authors show that only a discrete subset of filters gives rise to an evolution which can be characterized by means of a partial differential equation     

Cancellation rules and extended word problems

Generalizations of the extended word problems of Dolev and Yao (1983) are investigated in the context of Thue systems with the Church-Rosser property.     

Comparing columnar,row and array DBMSs to process recursive queries on graphs

Analyzing graphs is a fundamental problem in big data analytics, for which DBMS technology does not seem competitive. On the other hand, SQL recursive queries are a fundamental mechanism to analyze graphs in a DBMS, whose processing and optimization are significantly harder than traditional SPJ queries. Columnar DBMSs are a new faster class of database system, with significantly different storage and query processing mechanisms compared to row DBMSs, still the dominating technology. With that motivation in mind, we study the optimization of recursive queries on a columnar DBMS focusing on two fundamental and complementary graph problems: transitive closure and adjacency matrix multiplication. From a query processing perspective we consider the three fundamental relational operators: selection, projection and join (SPJ), where projection subsumes SQL group-by aggregation. We present comprehensive experiments comparing recursive query processing on columnar, row and array DBMSs to analyze large graphs with different shape and density. We study the relative impact of query optimizations and we compare raw speed of DBMSs to evaluate recursive queries on graphs. Results confirm classical query optimizations that keep working well in a columnar DBMS, but their relative impact is different. Most importantly, a columnar DBMS with tuned query optimization is uniformly faster than row and array systems to analyze large graphs, regardless of their shape, density and connectivity. On the other hand, there is no clear winner between the row and array DBMSs.