Linearising nonlinear recursions in polynomial time
- 29 March 1989
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 182-189
- https://doi.org/10.1145/73721.73740
Abstract
The replacement of nonlinear recursions with equivalent linear recursions is a potentially useful query optimization strategy, since it permits the use of efficient algorithms for the evaluation of linear logic programs. We show that a member of a certain class of bilinear recursions is linearizable in a strong sense if and only if a specific partial proof tree derived from this recursion is contained in a bounded number of partial proof trees generated by the recursion. Further, while each such test of containment between proof trees involves an exponential number of conjunctive-query containment tests, we present syntactic conditions on the recursion that are necessary and sufficient for the containment and verifiable in polynomial time.Keywords
This publication has 10 references indexed in Scilit:
- Proof-tree transformation theorems and their applicationsPublished by Association for Computing Machinery (ACM) ,1989
- Optimizing datalog programsPublished by Association for Computing Machinery (ACM) ,1987
- On the power of magicPublished by Association for Computing Machinery (ACM) ,1987
- Magic counting methodsPublished 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
- On the implementation of a simple class of logic queries for databasesPublished 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
- On compiling queries in recursive first-order databasesJournal of the ACM, 1984
- Optimal implementation of conjunctive queries in relational data basesPublished by Association for Computing Machinery (ACM) ,1977