𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Equivalence of Recursive and Nonrecursive Datalog Programs

✍ Scribed by Surajit Chaudhuri; Moshe Y Vardi

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
591 KB
Volume
54
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. Since nonrecursive Datalog programs are equivalent to unions of conjunctive queries, we study also the problem of determining whether a given recursive Datalog program is contained in a union of conjunctive queries. For this problem, we prove doubly exponential upper and lower time bounds. For the equivalence problem, we prove triply exponential upper and lower time bounds. ] 1997 Academic Press

It can be shown that 6 2 is not equivalent to the nonrecursive program: buys(X, Y) : &likes(X, Y).

buys(X, Y) : &knows(X, Z), likes(Z, Y).

πŸ“œ SIMILAR VOLUMES

On the Expected Size of Recursive Datalo
On the Expected Size of Recursive Datalog Queries
✍ S. Seshadri; J.F. Naughton πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 998 KB

We present asymptotically exact expressions for the expected sizes of relations defined by three well-studied Datalog recursions, namely the "transitive closure," "same generation," and "canonical factorable recursion." We consider the size of the fixpoints of the recursively defined relations in th