On compile-time query optimization in deductive databases by means of static filtering
- 1 September 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 15 (3) , 385-426
- https://doi.org/10.1145/88636.87121
Abstract
We extend the query optimization techniques known as algebric manipulations with relational expressions [48] to work with deductive databases. In particular, we propose a method for moving data-independent selections and projections into recursive axioms, which extends all other known techniques for performing that task [2, 3, 9, 18, 20]. We also show that, in a well-defined sense, our algorithm is optimal among the algorithms that propagate data-independent selections through recursion.Keywords
This publication has 22 references indexed in Scilit:
- SYGRAF: implementing logic programs in a database styleIEEE Transactions on Software Engineering, 1988
- Efficient tests for top-down termination of logical rulesJournal of the ACM, 1988
- Bounds on the propagation of selection into logic programsPublished by Association for Computing Machinery (ACM) ,1987
- A problem-oriented inferential database systemACM Transactions on Database Systems, 1986
- Implementation of logical query languages for databasesACM Transactions on Database Systems, 1985
- Logic and Databases: A Deductive ApproachACM Computing Surveys, 1984
- On compiling queries in recursive first-order databasesJournal of the ACM, 1984
- On recursive axioms in deductive databasesInformation Systems, 1983
- Optimizing the evaluation of calculus expressions in a relational database systemInformation Systems, 1980
- The Semantics of Predicate Logic as a Programming LanguageJournal of the ACM, 1976