Optimizing existential datalog queries
- 1 March 1988
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
The problem of pushing projections in recursive rules has received little attention. The objective of this paper is to motivate this problem and present some (partial) solutions. We consider programs with function-free rules, also known as Datalog programs. After formally defining existential subqueries, we present a syntactic criterion for detecting them and then consider optimization in three areas 1) We identify the existential subqueries and make them explicit by rewriting the rules. This, in effect, automatically captures some aspects of Prolog's cut operator that are appropriate to the bottom-up model of computation 2) We eliminate argument positions in recursive rules by “pushing projections” 3) We observe that “pushing projections” in rules also has the effect of making some rules (even recursive rules) redundant and try to (identify and) discard themThis publication has 6 references indexed in Scilit:
- On the power of magicPublished by Association for Computing Machinery (ACM) ,1987
- Decidability and expressiveness aspects of logic queriesPublished by Association for Computing Machinery (ACM) ,1987
- An amateur's introduction to recursive query processing strategiesPublished by Association for Computing Machinery (ACM) ,1986
- Implementation of logical query languages for databasesACM Transactions on Database Systems, 1985
- Convergence of sideways query evaluationPublished by Association for Computing Machinery (ACM) ,1985
- Magic sets and other strange ways to implement logic programs (extended abstract)Published by Association for Computing Machinery (ACM) ,1985