DocumentCode
2531212
Title
The complexity of acyclic conjunctive queries
Author
Gottlob, Georg ; Leone, Nicola ; Scarcello, Francesco
Author_Institution
Inst. fur Informationssyt., Tech. Univ. Wien, Austria
fYear
1998
fDate
8-11 Nov 1998
Firstpage
706
Lastpage
715
Abstract
We show that the problem of evaluating acylic Boolean database-queries is LOGCFL-complete and thus highly parallelizable. We present a parallel database algorithm solving this problem with a logarithmic number of parallel join operations. It follows from our main result that the acylic versions of the following important database and Al problems are LOGCFL-complete: The query output tuple problem for conjunctive queries, conjunctive query containment, clause subsumption, and constraint satisfaction
Keywords
Boolean functions; computational complexity; database theory; parallel algorithms; query processing; LOGCFL-complete; acyclic conjunctive queries complexity; acylic Boolean database-queries; clause subsumption; conjunctive queries; constraint satisfaction; parallel database algorithm; parallel join operations; query output tuple problem; Artificial intelligence; Books; Database systems; Electrical capacitance tomography; Microwave integrated circuits; Read only memory; Relational databases;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location
Palo Alto, CA
ISSN
0272-5428
Print_ISBN
0-8186-9172-7
Type
conf
DOI
10.1109/SFCS.1998.743521
Filename
743521
Link To Document