Paper Info
Title
Efficiently ordering subgoals with access constraints
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.
Year
DOI
Venue
2006
10.1145/1142351.1142378
PODS
Keywords
Field
DocType
first-order query,access constraint,nonrecursive datalog program,nested grouping constraint,asymptotically optimal algorithm,binding pattern restriction,conjunctive query,practical solution,limited expressive power,query plan,query planning problem,conjunctive queries,expressive power
Discrete mathematics,Conjunctive query,Computer science,Theoretical computer science,Asymptotically optimal algorithm,Expressive power,Datalog,Boolean conjunctive query,Query plan
Conference
ISBN
Citations 
PageRank 
1-59593-318-2
7
0.55
References 
Authors
17
3
Name
Order
Citations
PageRank
Guizhen Yang140551.01
Michael Kifer23980950.22
Vinay K. Chaudhri3587246.49