Chase of recursive queries

Chase of recursive queries?

Nieves R.Brisaboa,Antonio Fari?n a,Miguel R.Luaces,and Jos′e R.Param′a Laboratorio de Bases de Datos.Dept.de Computaci′o n.Univ.Da Coru?n a.Campus de Elvi?n a s/n,15071A Coru?n a.Spain.Tf.+34981167000.Fax.+34981167160 brisaboa@udc.es,fari@udc.es,luaces@udc.es,parama@udc.es

Abstract.In this work,we present a semantic query optimization

technique to improve the e?ciency of the evaluation of a subset of

SQL:1999recursive queries.

Using datalog notation,we can state our main contribution as an

algorithm that builds a program P′equivalent to a given program P,

when both are applied over a database d satisfying a set of functional

dependencies.The input program P is a linear recursive datalog program.

The new program P′has less di?erent variables and,sometimes,less

atoms in rules,thus it is cheaper to https://www.wendangku.net/doc/004967278.html,ing coral,P′is

empirically shown to be more e?cient than the original program.

Keywords:Recursive queries,Semantic Query Optimization.

1Introduction

Although research in recursive queries has been carried out for the last three decades,the appearance of the SQL:1999rea?rmed the necessity of research in this area,given that SQL:1999includes queries with linear recursion.Previous standards of SQL did not include recursion,thus research in recursive query optimization might be able to provide the suitable algorithms,to be included in the query optimizers of the database management systems to speed up the execution of recursive queries.

Although our results are focused on the development of algorithms to be included in commercial object-relational database management systems, we use datalog syntax since it is easier to manipulate.The class of datalog programs considered in this paper can be translated into SQL:1999queries straightforwardly.

Example1.Let us suppose that we have a database with the following relations: stretch(Number,F rom,T o),meaning that a flight with code Number has a stretch from the airport F rom to the airport T o;assig(Number,Employee) meaning that a certain Employee is assigned to the?ight Number.

?This work is partially supported by Grants TIC2003-06593and TIN2006-15071-C03-03of Ministerio de Educaci′o n y Ciencia and PGIDIT05SIN10502PR of Xunta de Galicia.

Let us consider the query that computes the relation conn(Number,From, To,First O?cer,Purser),meaning that?ight Number connects the airport From with the airport T o,possibly using several stopovers.In addition,conn has the information of the First O?cer and the Purser of the?ight.conn is the transitive closure of each?ight code with some additional information about the?ight crew. P:r0:conn(N,F,T,O,P):?stretch(N,F,T),assig(N,O),assig(N,P)

r1:conn(N,F,T,O,P):?stretch(N,F,Z),assig(N,O),assig(N,P),conn(N,Z,T,O,P)

??P is linear,which means it has only one recursive atom in the body of the recursive rule.Linear programs include most real life recursive queries,then much research e?ort has been devoted to this class of programs(see[17]for a survey of optimization techniques for this class of programs).

In addition,P is a single recursive program(sirup).This implies that it has only one recursive rule.Sirups is another class of programs considered by several researchers(see[6,8,1]for example).

The combination of both features(like in our example),is called linear single recursive programs(lsirup).These programs are the programs considered in this work,and they were also studied by several works(see[18,10,8]for example).

An interesting approach to optimize a recursive query is to see if we can transform the query,somehow,to make the recursion“smaller”and“cheaper”to evaluate.One possibility to do that is the semantic query optimization that uses integrity constraints associated with databases in order to improve the e?ciency of the query evaluation[5].In our case,we use functional dependencies(fds)to optimize linear recursive datalog programs.

In this paper we provide an algorithm to optimize single recursive datalog programs under fds.The chase of datalog programs(Chase F(P))is a modi?cation of an algorithm introduced by Lakshmanan and Hern′a ndez[8]. It obtains from a linear single recursive program P a program P′,equivalent to P when both are evaluated over databases that satisfy a set of functional dependencies F.

The chase of a datalog program P obtains an equivalent program P′,where the recursive rule may has smaller number of di?erent variables and,less number of atoms.That is,it obtains a program where the variables(in the recursive rule) are equated among them due to the e?ect of fds.Moreover,those equalizations of variables,sometimes reveal that an unbounded datalog program P is in fact (due to the fds)a bounded datalog program.

Example2.Considering the program of Example1,let us suppose that our company decides that the?rst o?cer should act as purser as well.This imposes a constraint specifying that one?ight code only has one employee assigned,that is assig:{1}→{2}.The set of functional dependencies F indicates that the values of the?rst argument determine the values in the second position in the set of facts over the predicate assig.For example,the atoms assiged(ib405,peter) and assig(ib405,mary)violate the fd assig:{1}→{2}.

Using the algorithm of the chase of datalog programs shown in this paper,it is possible to compute the new program Chase F(P)that we call,for short,P′:

s0:conn(N,F,T,O,O):?stretch(N,F,T),assig(N,O)

s1:conn(N,F,T,O,O):?stretch(N,F,Z),assig(N,O),conn(N,Z,T,O,O)

There are two combined bene?cial e?ects.First,there are6di?erent variables in r0,but only5in s0.Second,the number of predicates in the bodies of the rules also decreases:3and4in r0and r1,respectively,but only2and3respectively in s0and s1.

The reader can observe that in this case P′is very similar to the original program,the only di?erence is that some variables have been equalized.This equalization comes from the fact that the database ful?lls the functional dependency assig:{1}→{2}.Therefore,if during the evaluation of the query, an atom,let say assig(N,O),is mapped to the ground fact assig(IB405,peter), then another atom assig(N,P)should be mapped to the same ground fact. Observe that assig(N,O)and assig(N,P)have the same variable in the?rst position,thus by assig:{1}→{2},O and P are necessarily mapped to the same ground term.??2Related Work

Several strategies have been proposed to tackle the process of recursive queries. Bancilhon,Maier,Sagiv and Ullman[3]introduced a technique called magic-sets for rewriting linear queries taking advantage of binds between nodes in rule goal trees.There is a family of papers that try to reduce the work done by a query execution by remembering previous executions of queries that can have intermediate values useful for the current execution.These techniques are called memoing(see[4]for a survey).

Since in practice the great majority of recursions are linear,this class of queries has attracted much work.From a logic programming perspective,several works deal with the placement of the recursive atom in the body of the rules.“Right-linear”and“left-linear”give better performance in linear recursion than magic-sets[11].

The chase as a tool to optimize queries in the framework of datalog is also used by several https://www.wendangku.net/doc/004967278.html,kshmanan and Hern′a ndez[8]introduced an algorithm called the chase of datalog programs which is based in the use of the chase[9,2].Recent data models have also adopted the chase to optimize queries. In the semistructured model,it has been also used as a rewriting technique for optimizing queries[7].Popa et.al.[14]used it to optimize queries in the framework of the object/relational model.

3De?nitions

3.1Basic Concepts

We assume the notation and de?nitions of[16]and then we only de?ne the non-standard concepts.We use EDB(P)to refer to the set of EDB predicate names in a datalog program P.We denote variables in datalog programs by capital

letters,while we use lower case letters to denote predicate names.For simplicity, we do not allow constants in the programs.Let a i be a atom,a i[n]is the term in the n th position of a i.

We say that a program P de?nes a predicate p,if p is the only IDB predicate name in the program.A single recursive rule program(sirup)[6]is a program that consists of exactly one recursive rule and several non-recursive rules and the program de?nes a predicate p.A2-sirup is a sirup that contains only one non-recursive rule(and one recursive rule).

A rule is linear if there is at most one ID

B atom in its body.A linear sirup (lsirup)[18]is a sirup such that its rules are linear.A2-lsirup[18]is a2-sirup such that its rules are linear.That is,a2?lsirup is a program de?ning a predicate p with one non-recursive rule and one recursive rule,which has only one IDB atom in its body.

Example3.The program of Example1is a2-lsirup.??For the sake of simplicity,many of the de?nitions will apply to2?lsirups although the algorithm presented in this paper is valid for lsirups as well.In addition,from now on,we denote with r0the non-recursive rule in a2?lsirup, and r1to denote the recursive rule.

Let P be a program,let r be a rule and let d be a database.Then,P(d) represents the output of P when its input is d and r(d)represents the output of r when its input is d.Let F be a set of functional dependencies,SAT(F) represents the set of databases that satis?es F.

Let P1and P2be programs.P1?SAT(F)P2,if P1(d)?P2(d)for all EDBs d in SAT(F).P1≡SAT(F)P2,if P1?SAT(F)P2and P2?SAT(F)P1.

A substitution is a?nite set of pairs of the form X i/t i where X i is a variable and t i is a term,which is either a variable or a constant,and X i and t i are di?erent.The result of applying a substitution,sayθ,to an atom A,denoted byθ(A),is the atom A with each occurrence of X replaced by t for every pair X/t inθ.For example,considerθ={X/a,Y/b}and the atom p(X,Y),then θ(p(X,Y))is p(a,b).A substitutionθcan be applied to a set of atoms,to a rule or to a tree to get another set of atoms,rule or tree with each occurrence X replaced by t for every X/t inθ.

4Expansion Trees

An expansion tree is a description for the derivation of a set of(intensional) facts by the application of one or more rules to an extensional database.First, we start with the de?nition of a tree generated by only one rule.Let r be the rule q:?q1,q2,...,q k.Then,a tree T can be built from r as follows:the node at the root of T is q,and q has k children,q i,1≤i≤k.We denote this tree as tree(r).

https://www.wendangku.net/doc/004967278.html,ing the program of Example1,Figure1shows tree(r1).

conn (N,F,T,O,P )a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b f f f f f

f f f f f f f f f f f stretch (N,F,Z )assi

g (N,O )assig (N,P )conn (N,Z,T,O,P )

Fig.1.tree (r 1).

?

?In order to be a complete expansion tree,that is,an expansion tree describing the complete execution of a program,the tree should start with the application of a non-recursive rule.

Let S and T be two trees.Then,S and T are isomorphic ,if there are two substitutions θand αsuch that S =θ(T )and T =α(S ).

The variables appearing in the root of a tree T are called the distinguished variables of T .All other variables appearing in atoms of T that are di?erent from the distinguished variables of T are called non-distinguished variables of T .

Let S and T be two trees,where h t denotes the head (the node at the root)of T .Assume that exactly one of the leaves of S is an IDB atom 1,denoted by p s .The expansion (composition)of S with T ,denoted by S ?T is de?ned if there is a substitution θ,from the variables in h t to those in p s ,such that θ(h t )=p s .Then,S ?T is obtained as follows:build a new tree,isomorphic to T ,say T ′,such that T ′and T have the same distinguished variables,but all the non-distinguished variables of T ′are di?erent from all of those in S .Then,substitute the atom p s in the last level of S by the tree θ(T ′).

From now on,we use the expression tree (r j ?r i )to denote tree (r j )?tree (r i )and,tree (r k j )to denote the composition of tree (r j )with itself,k times.Given a 2?lsirup P ={r 0,r 1},T i denotes the tree tree (r i 1?r 0).T i is a complete expansion tree since it describes the derivation of a set of IDB facts from an extensional database.Obviously,since P is a recursive program,we may construct in?nitely many trees considering successive applications of the recursive rule.We call trees (P )the in?nite ordered collection of trees {T 0,T 1,T 2,T 3,...}.

Example https://www.wendangku.net/doc/004967278.html,ing the program of Example 1,Figure 2shows T 2.

From now on,we shall consider only complete expansion trees.For the sake of simplicity we shall refer to expansion trees simply as trees.

Let T be a tree.The level of an atom in T is de?ned as follows:the root of T is at level 0,the level of an atom n of T is one plus the level of its parent.Level j of T is the set of atoms of T with level j .The last level of a tree T i is the level i +1.We say that two levels i and k (in a tree T j )are separated by w levels if |i ?k |=w and i ≤j +1and k ≤j +1.

1That is,the case of the trees generated by lsirups ,since in the recursive rule of such programs,there is only one IDB predicate.

conn (N,F,T,O,P )a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b f f f f f

f f f f f f f f f f f stretch (N,F,Z )assi

g (N,O )assig (N,P )conn (N,Z,T,O,P )a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b f f f f f

f f f f f f f f f f f stretch (N,F,Z ′)assi

g (N,O )assig (N,P )conn (N,Z ′,T,O,P )b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b f f f f f

f f f f f f f f f f f stretch (N,Z ′,T )assi

g (N,O )assig (N,P )

Fig.2.The tree T 2using the program of Example 1.

4.1TopMost and frontier of a tree

TopMost and frontier of a tree are two rules that can be extracted from any tree.Let T be a tree:the frontier of T (also known as resultant ),denoted by frontier (T ),is the rule h :?l 1,...,l n ,where h is the root of T and l 1,...,l n is the set of leaves of T ;the topMost of T ,denoted by topMost (T ),returns the rule h :?c 1,...,c n ,where h is the root of T and c 1,...,c n is the set of atoms that are the children of the root.

Example https://www.wendangku.net/doc/004967278.html,ing the tree of Figure 2:

frontier (T 2):conn (N,F,T,O,P ):-stretch (N,F,Z ),assig (N,O ),assig (N,P )

stretch (N,F,Z ′),assig (N,O ),assig (N,P )stretch (N,Z ′,T ),assig (N,O ),assig (N,P )

topMost (T 2):conn (N,F,T,O,P ):-stretch (N,F,Z ),assig (N,O ),assig (N,P ),conn (N,Z,T,O,P )??

Observe that the frontier of a tree in trees (P )is a non-recursive rule,while the topMost may be a recursive one.Let P be a 2?lsirup ,d an extensional database and T a tree in trees (P ).T (d )represents the result of applying the rules used to build T to the input extensional database d in the order speci?ed by T .That is,T (d )can be seen or computed as frontier (T )(d )2.Let T and Q be two trees,T ≡SAT (F )Q means that T (d )=Q (d )for any extensional database d in SAT (F ).

5Chase of a tree

The chase [9,2]is a general technique that is de?ned as a nondeterministic procedure based on the successive application of dependencies (or generalized dependencies)to a set of tuples (that can be generalized to atoms).

Let us consider the following:Let F be a set of fds de?ned over EDB (P ),for some program P .Let T i be a tree in trees (P ).Let f =p :{n }→{m }be a fd in F .Let q 1and q 2be two atoms in the leaves of T i such that the predicate 2Observe that if T is in trees (P ),the body of the frontier of a tree only contains EDB atoms.

name of q 1and q 2is p ,q 1[n ]=q 2[n ]and q 1[m ]=q 2[m ].Note that n can be a set of positions.In addition,observe that q 1[m ]and q 2[m ]are variables since we are assuming that programs do not contain constants.An application of the fd f to T i is the uniform replacement in T i of q 1[m ]by q 2[m ]or vice versa.By uniform,we mean that q 1[m ]is replaced by q 2[m ](or vice versa)all along the tree.

5.1Partial Chase of a tree

The partial chase of T with respect to F ,denoted by ChaseP F (T ),is obtained by applying every fd in F to the atoms that are the leaves of T except the atoms in the last level,until no more changes can be made.Observe that although the atoms which are taken into account for the computation of the chase do not include the atoms in the last level,if a variable is renamed by the chase,such change is applied all along the tree.

Example 7.Let F be e :{1}→{2}:

T

ChaseP F (T )e (X,Y,Y )e (X,Z,Z )e (X,X,Z )p (X,X,Z )

!!!!!

a a a a p (X,Y,Z )e (X,Y,Y )e (X,Y,Y )e (X,X,Y )p (X,X,Y )!!!!!a a a a p (X,Y,Y )??

Lemma 1.Let P be a 2?lsirup ,let F be a set of fds over EDB (P ).There is a tree T k such that for any tree T l with l >k ,topMost (ChaseP F (T l ))is isomorphic to topMost (ChaseP F (T k )).

Proof Note that for all i,x such that i >x >0,T i includes all the atoms of T i ?x that are considered by the partial chase,then any equalization in ChaseP F (T i ?x )is also included in ChaseP F (T i ).Therefore,there is a limit in the equalizations produced in the topMost given that all trees in trees (P )with more than two levels have the same topMost,and this topMost has a ?nite number of variables.

??

The inclusion of the last level of the tree introduces equalizations that are more di?cult to model.Lemma 1would not be true is such a case.We explored this possibility in [13].

Lemma 2.Let P be a 2-lsirup.Let T i be a tree in trees (P ),and let F be a set of fds over EDB (P ).Then,T i ≡SAT (F )ChaseP F (T i ).

The proof can be done readily,we do not include it by lack of space.6The Chase of datalog Programs

In [12],there is a method to ?nd T k ,the tree such that for any tree T l with l >k ,topMost (ChaseP F (T l ))is isomorphic to topMost (ChaseP F (T k )).The basic idea is sketched below.

Let us consider a tree T i in trees(P)and two atoms q j,k and q l,m of T i. q j,k is in the k th position(numbering the atoms of its level from left to right) of level j.Similarly,q l,m is in the m th position of level l.Now,let us suppose that the variables q j,k[n]and q l,m[n]are equalized by the ChaseP F(T i).Then in T i+1,q j+1,k[n]is equalized to q l+1,m[n]during the ChaseP F(T i+1).When we ?nd a tree,say T p,that for any equalization during its partial chase,say q j,k[n] equalized to q l,m[n],in ChaseP F(T p?r),where1≤r≤2N,q j?r,k[n]is equalized to q l?r,m[n],then we have found T k.Now the question is to?nd N.

6.1The computation of N

To compute N we need to provide a previous tool.

Let P be a2?lsirup.Let p h and p b be the IDB atoms in the head and in the body of r1,the recursive rule of P.The Expansion Graph of a program P is generated with this algorithm.

1.If the arity of the IDB predicate in P is k,add k nodes named1,...,k.

2.Add one arc from the node n to the node m,if a variable X is placed in the

position n of p h,and X is placed in the position m of p b.

3.Add one arc from the node n without target node,if a variable X is placed

in the position n of p h,and it does not appear in p b.

4.Add one arc without source node and target node m,if a variable X is placed

in the position m of p b and it does not appear in p h.

Example8.Let P={r0,r1}where r1contains the following IDB atoms:

p(A,B,C,D,E,F,G,H,I,J,K,L,M):?...p(B,A,E,C,D,F,W,G,G,X,J,L,L) In Figure3,we can see the expansion graph of P.??

P

Let G be N is the least common multiple of the

https://www.wendangku.net/doc/004967278.html,mon multiplier of2, 3,1,2,2,2).

6.2The algorithm

Assuming that we have found T k,the chase of a2?lsirup P w.r.t.a set of fds F is obtained with the algorithm shown in Figure4.

Chase(P:a2?lsirup,F:a set of functional dependencies over EDB(P))

For any tree T i with i

topMost(ChaseP F(T k))is not isomorphic to topMost(ChaseP F(T i)) Output frontier(ChaseP F(T i));

Output topMost(ChaseP F(T k));

Fig.4.Chase of a datalog program.

Our algorithm is based in Lakshmanan and Hern′a ndez’algorithm[8],but our algorithm obtains better results.This improvement comes from the terminating condition.Their algorithm stops when it?nds two consecutive trees with the same topMost after the partial chase.However,it is clear that after two consecutive trees with the same topMost after the partial chase,there would be bigger trees that may introduce more equalizations in the topMost after the partial chase.Our algorithm stops in a tree T k such that it is sure that any bigger tree than T k would not introduce any other equalization in the topMost after the partial chase.Hence,our algorithm introduces more equalities in the recursive rule of the new program.

Theorem1.Let P be a2?lsirup,let F be a set of fds over EDB(P). The Chase F(P)is equivalent to P when both are evaluated over databases in SAT(F).

Proof In order to prove this theorem,we have to prove that P′?SAT(F)P and P?SAT(F)P′.

We start with the proof of P′?SAT(F)P.Let NR be the set of non-recursive rules in P′,and let R be the set of recursive rules in P′.Let s be a rule in NR, by the algorithm in Figure4,s=frontier(ChaseP F(T i))for some tree T i in trees(P).Then,by Lemma2,{s}?SAT(F)r i1?r0,and thus{s}?SAT(F)P. Let r be a rule in R.Therefore,r=θ(topMost(T j)),whereθis the substitution de?ned by ChaseP F(T j)and T j is a tree in trees(P).Since r is a recursive rule and P only has one recursive rule,then j>0and topMost(T j)=r1.Therefore, by construction,using the algorithm of the Chase of datalog programs,r=θ(r1), and hence r?r1.Thus,we have shown that for any rule r in P′,{r}?SAT(F)P.

Now,we tackle the other direction of the proof;P?SAT(F)P′.We are going to prove that any fact q produced by P,when P is applied to an extensional database d in SAT(F),is also produced by P′,when P′is applied to d.

Let us assume that q is in T i(d),that is,q is obtained after the application to d of r0once,and i times r1.We are going to prove that q is in P′(d).We

prove it by induction on the number of levels of the tree T i (in trees (P ))that if q is in T i (d ),then q is in P ′(d ).

Basis i=0,q is in T 0(d ).Then q is in P ′(d ).Observe that P ′always contains frontier (ChaseP F (T 0)),since the topMost F (ChaseP F (T 0))cannot be isomorphic to the topMost of the partial chase of any other tree in trees (P )since r 0is the only non-recursive rule of P .Then,necessarily the algorithm always outputs frontier (ChaseP F (T 0)).Therefore,by Lemma 2,if q is in T 0(d )then q is in ChaseP F (T 0)(d ),and then q is in P ′.

Induction hypothesis (IH):Let assume that ?q ∈T i (d ),1≤i

We have two cases:Case 1:frontier (ChaseP F (T j ))is one of the non-recursive rules of P ′.Then by Lemma 2q is in P ′(d ).

Case 2:frontier (ChaseP F (T j ))is not one of the non-recursive rules of P ′.Thus,by Lemma 2q ∈{ChaseP F (T j )}(d )(assuming that d ∈SAT (F )).Let γbe the substitution de?ned by the ChaseP F (T j ).

Let T sub be the subtree of T j that is rooted in the node at the ?rst level of T j that is,the recursive atom at that level.T sub has one level less than T j ,therefore T sub is isomorphic to T j ?1.Observe that this follows from the fact that in P there is only one recursive rule and one non-recursive rule.

Let q sub be an atom in T sub (d ),since T sub is isomorphic to T j ?1,then q sub is in T j ?1(d ).Hence,by IH q sub ∈P ′(d ).It is easy to see that q ∈{topMost (ChaseP F (T j ))}(d q sub ),that is,q ∈{γ(r 1)}(d q sub ).

By construction of P ′,in P ′there is a rule s t =θ(r 1),where θis the substitution de?ned by the partial chase of T k .By Lemma 1and construction of the algorithm in Figure 4,γ≡θ,otherwise frontier (ChaseP F (T j ))would be one of the non-recursive rules in P ′.

We have already shown that q sub is a fact in P ′(d ).Therefore,since s t (d ∪q sub )obtains q ,thus we have proven that if q is in T j (d )then q is also in P ′(d ).??7Empirical results

We used coral [15],a deductive database,in order to compare the running time of the original program versus the optimized one.We ran 20di?erent programs over databases of di?erent sizes.The datalog programs were synthetic queries developed by us.coral is an experimental system,this is a limitation,since the maximum database size is restricted,because coral loads all tuples in memory and then,if the database has a certain size,an over?ow arises.

The computation time needed to obtain the optimized datalog program,using a program in C++in a 200-MHz Pentium II with 48Mbytes of RAM,takes on average 0.17seconds with a varianza of 0.019.This is a insigni?cant amount of time when the database to which it is applied the query has a normal size.

The average running time of the optimized program is the43.95%of that of the original one with a varianza of0.10.The con?dence interval of this improvement,with a con?dence level of95%,is[28.82%,59.10%].That is,the optimized program is between1.7and3.5times faster than the original one.

8Conclusions and Future Work

Given a lsirup P and a set of fds F,we provide an algorithm that obtains a new program P′equivalent to P when both are applied over databases in SAT(F).In addition,we have shown that the algorithm is correct.The algorithm shown in this paper is based in the partial chase,that does not consider atoms in the last level of the chased trees.As a future work,it would very interesting the inclusion of the last level in the computation of the chase.In that case,the chase would introduce more equalities in the alternative optimized program. References

1.S.Abiteboul.Boundedness is undecidable for datalog programs with a single

recursive https://www.wendangku.net/doc/004967278.html,rmation Processing Letters,(32):282–287,1989.

2.S.Abiteboul,R.Hull,and V.Vianu.Foundations of Databases.Addison Wesley,

1995.

3. F.Bancilhon,D.Maier,Y.Sagiv,and J.D.Ullman.Magic sets and other strange

ways to implement logic programs.In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems,pages1–16,Cambridge, Massachusetts,24–26Mar.1986.

4. F.Bancilhon and R.Ramakrishnan.An amateur’s introduction to recursive query

processing strategies.In Proceedings of ACM SIGMOD International Conference on Management of Data,Washington,DC,pages16–52.ACM,May1986.

5.U.S.Chakravarthy,J.Grant,and J.Minker.Foundations of semantic query

optimization for deductive databases.In J.Minker,editor,Foundations of Deductive Databases and Logic Programming,pages243–273.Morgan Kau?mann Publishers,1988.

6.S.S.Cosmadakis and P.C.Kanellakis.Parallel evaluation of recursive rule queries.

In Proc.Fifth ACM SIGACT-SIGMOD Symposium on Principle of Database Systems,pages280–293,1986.

7. A.Deutsch and V.Tannen.Reformulation of XML queries and constraints.In

ICDT,pages225–241,2003.

https://www.wendangku.net/doc/004967278.html,kshmanan and H.J.Hern′a ndez.Structural query optimization-

a uniform framework for semantic query optimization in deductive databases.

In Proc.Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principle of Database Systems,pages102–114,1991.

9. D.Maier.The Theory of Relational https://www.wendangku.net/doc/004967278.html,puter Science Press,1983.

10.J.Naughton.Data independent recursion in deductive databases.In Proc.Fifth

ACM SIGACT-SIGMOD Symposium on Principle of Database Systems,pages267–279,1986.

11.J.F.Naughton,R.Ramakrishnan,Y.Sagiv,and J.D.Ullman.E?cient evaluation

of right-,left-,and multi-linear rules.ACM SIGMOD RECORD,18(2),June 1989.Also published in/as:19ACM SIGMOD Conf.on the Management of Data, (Portland OR),May.-Jun.1989.

12.J.R.Param′a.Chase of Datalog Programs and its Application to Solve the

Functional Dependencies Implication Problem.PhD thesis,Universidade Da Coru?n a,Departmento de Computaci′o n,A Coru?n a,Espa?n a,2001.

13.J.R.Param′a,N.R.Brisaboa,M.R.Penabad,and A.S.Places.A semantic

approach to optimize linear datalog programs.Acta Informatica.In press.

14.L.Popa,A.Deutsch,A.Sahuguet,and V.Tannen.A chase too far.In SIGMOD,

pages273–284,2000.

15.R.Ramakrishnan,P.Bothner,D.Srivastava,and S.Sudarshan.Coral:A databases

programming language.Technical Report TR-CS-90-14,Kansas State University, Department of Computing and Information Sciences,1990.

16.J.D.Ullman.Principles of Database And Knowledge-Base Systems,volume1.

Computer Science Press,1988.

17.J.D.Ullman.Principles of Database And Knowledge-Base Systems,volume2.

Computer Science Press,1989.

18.M.Y.Vardi.Decidability and undecidability results for boundedness of linear

recursive queries.In Proc.Seventh ACM SIGACT-SIGMOD Symposium on Principle of Database Systems,pages341–351,1988.