Thumbnail
Access Restriction
Subscribed

Author Gottlob, Georg ♦ Leone, Nicola ♦ Scarcello, Francesco
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword CSP ♦ LOGCFL ♦ Acyclic hypergraph ♦ Algorithm ♦ Bounded treewidth ♦ Conjunctive query ♦ Constraint ♦ Constraint satisfaction problem ♦ Database theory ♦ Degree of cyclicity ♦ Hinge ♦ Join tree ♦ Parallel algorithm ♦ Query containment ♦ Qury-idth ♦ Subsumption ♦ Tree query
Abstract This paper deals with the evaluation of acyclic Booleanconjunctive queries in relational databases. By well-known resultsof Yannakakis[1981], this problem is solvable in polynomial time;its precise complexity, however, has not been pinpointed so far. Weshow that the problem of evaluating acyclic Boolean conjunctivequeries is complete for LOGCFL, the class of decision problems thatare logspace-reducible to a context-free language. Since LOGCFL iscontained in AC1 and NC2, the evaluation problem of acyclic Booleanconjunctive queries is highly parallelizable. We present a paralleldatabase algorithm solving this problem with alogarithmic number ofparallel join operations. The algorithm is generalized to computingthe output of relevant classes of non-Boolean queries. We also showthat the acyclic versions of the following well-known database andAI problems are all LOGCFL-complete: The Query Output Tuple problemfor conjunctive queries, Conjunctive Query Containment, ClauseSubsumption, and Constraint Satisfaction. The LOGCFL-completenessresult is extended to the class of queries of bounded tree widthand to other relevant query classes which are more general than theacyclic queries.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 3
Page Count 68
Starting Page 431
Ending Page 498


Open content in new tab

   Open content in new tab
Source: ACM Digital Library