Efficiently ordering subgoals with access constraints
Authors:
Open Access
- 26 June 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 183-192
Abstract
In this paper, we study the problem of ordering subgoals under binding pattern restrictions for queries posed as nonrecursive Datalog programs. We prove that despite their limited expressive power, the problem is computationally hard—PSPACE-complete in the size of the nonrecursive Datalog program even for fairly restricted cases. As a practical solution to this problem, we develop an asymptotically optimal algorithm that runs in time linear in the size of the query plan. We also study extensions of our algorithm that efficiently solve other query planning problems under binding pattern restrictions. These problems include conjunctive queries with nested grouping constraints, distributed conjunctive queries, and first-order queries.Keywords
This publication has 14 references indexed in Scilit:
- Integration of Heterogeneous Knowledge Sources in the CALO Query ManagerLecture Notes in Computer Science, 2005
- Processing first-order queries under limited access patterns2004
- Processing Unions of Conjunctive Queries with Negation under Limited Access Patterns2004
- Rewriting Queries Using Views with Access Patterns Under Integrity ConstraintsLecture Notes in Computer Science, 2004
- Expressive capabilities description languages and query rewriting algorithmsThe Journal of Logic Programming, 2000
- Recursive query plans for data integrationThe Journal of Logic Programming, 2000
- Capability based mediation in TSIMMIS1998
- Query reformulation for dynamic information integrationJournal of Intelligent Information Systems, 1996
- Safety and translation of relational calculusACM Transactions on Database Systems, 1991
- Optimization of join operations in horizontally partitioned database systemsACM Transactions on Database Systems, 1986