Thumbnail
Access Restriction
Subscribed

Author Halevy, Alon Y. ♦ Mumick, Inderpal Singh ♦ Sagiv, Yehoshua ♦ Shmueli, Oded
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Abstract interpretation ♦ Datalog ♦ Query containment ♦ Query satisfiability
Abstract We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present can also be used to push constraints from a given query to the EDB predicates. In showing our decidability results we describe a powerful tool, the query-tree, which is used for several optimization problems for datalog programs. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 5
Page Count 42
Starting Page 971
Ending Page 1012


Open content in new tab

   Open content in new tab
Source: ACM Digital Library