Finiteness Properties of Database Queries.
Inderpal Singh Mumick, Oded Shmueli · 1993
) Inderpal Singh Mumick AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974, USA [email protected] Oded Shmueli AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974, USA [email protected] Abstract We investigate the problem of checking whether the number of derivation trees of a Datalog program with duplicate semantics is finite or not. We show that given a safe stratified query and an edb, it is possible to check, in polynomial time, whether the query has a finite number of derivation trees. However, it is undecidable to check whether a safe stratified query has a finite number of derivation trees for every possible edb. We identify two classes of queries for which checking finiteness over all edbs is decidable. We also define duplicate semantics for Datalog (and thereby for the newly proposed variants of recursive SQL) queries with stratified negation. Since evaluation involving counting of duplicates may not terminate in recursive SQL, this ...