Alon Levy
Inderpal Singh Mumick
ABSTRACT
We consider the problems of equivalence, satisfiability and query-reachability for datalog programs with negation and dense-order constraints. 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 are also used to push constraints from a given query to the EDB predicates. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠
- AH88.Serge Abiteboul and Richard Hull. Data fllnctions, datalog, and negation. In Proceedzng.s of A CM SIGMOD 1988 Inlernattonal ('onference on Management of Data, Chicago, IL, June 1988. Google Scholar
Digital Library
- CV92.Surajit C haudhuri and Moshe Vardi. On the equivalence of reeursive and nonrecursive datalog programs. In Proceedings of the Eleventh Symposium on Principles of Dalabase Systems (PODS), pages 55- 66, San Diego, CA, June 2-4 1992. ACM SIGACT-SIGMOD-SIGART. Google ScholarDigital Library
- CGKV88.,'5. S. Cosmadakis, H. G#tifman, Paris C. Kanellakis, and Moshe Y. Vardi. Decidable optimization problems for database logic progra.ms. In Proceedings of lhe Twentieth S#lmposium on Theory of Compu/ing, pages 477-490, 1988. Google ScholarDigital Library
- GMSV87.H. Gaifman, H. Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. Undecidable optimization problems for database logic programs, In Proceedings of the Second IEEE Symposium. on Logic in Computer Sczence(LICS), pages 106-115, Ithaca, NY, 1987.Google Scholar
- KKR90.Paris C. Kanellakis, Gabriel M. Kuper, and Peter Z. Revesz. Constraint query languages, in Proceedings of lhe Ninth Sympo.s#um on Prznciples of Database Systems (PODS), pages 299-313, Nashville, TN, April 2-4 1990. ACM SIGACT-SIGMOD- SIGART. Google ScholarDigital Library
- Levy93.Alon Y. Levy. Relevance Reasoning in Knowledge Based Systems.Pb.D These.s. 5'tal#ford Un#versily, 1993. Google ScholarDigital Library
- LS92.Alon Levy and Yehoshua Sagiv. Constraints and redundancy in datalog. In Proceedtngs of lhe Eleventh Symposium on Principles of Database Systems (PODS), pages 67- 80. San Diego, CA, June 2-4 1992. ACh{ ,qI G ACT- SIG M O D-SI G ART. Google ScholarDigital Library
- Shm87.Oded Shmueli. Decidability and expressivehess aspects of logic queries. In Proceed- #,gs of the Sixth Symposium o7# Prznczples of Database Systems (PODS), pages 237-249, San Diego, CA, March 1987. ACM SIGACT- SIGMOD-SIGART. Google ScholarDigital Library
- Ull88.Jeffrey D. Utlman. Pmnciples of Database a#d Knowledge-Base Systems,Volume 1. ('omputer Science Press, 1988. Google ScholarDigital Library
- Ull89.Jeffrey D. Ullman. Principles of Database (li#d Knowledge-Base Systems,Volume 2. Computer Science Press, 1989. Google ScholarDigital Library
- UV88.Jeffrey D. Ullman and Allen Van Gelder. Parallel complexity of logical query programs. Algorithm,ca, 3:5-42, 1988.Google Scholar
- vdM92.Ronald van der Meyden. The Complexity of Querying b#.definile h#formation: Defined Relal'lons, Recurs'#on and Linear Order. PhD thesis, Rutgers, The State University of New Jersey, New Brunswick, NJ, October 1992. Google ScholarDigital Library
- Var89.#ioshe Y. Vardi. Automata theory for dat.a.base theoreticians, in Proceedzngs of/he Etghth Symposium on PmT#c#ples of Database S.qstems (PODS'), pages 83-92, Philadelphia, PA, March 1989. ACM SIGACT- SIGMOD-SIGART. Google ScholarDigital Library
Index Terms
- Equivalence, query-reachability and satisfiability in Datalog extensions
Recommendations
Static analysis in datalog extensions
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 ...
Datalog LITE: a deductive query language with linear time model checking
We present Datalog LITE, a new deductive query language with a linear-time model-checking algorithm, that is, linear time data complexity and program complexity. Datalog LITE is a variant of Datalog that uses stratified negation, restricted variable ...
Disjunctive datalog
We consider disjunctive Datalog, a powerful database query language based on disjunctive logic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads; advanced versions also allow for negation ...
Comments