Title :
The complexity of acyclic conjunctive queries
Author :
Gottlob, Georg ; Leone, Nicola ; Scarcello, Francesco
Author_Institution :
Inst. fur Informationssyt., Tech. Univ. Wien, Austria
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;
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-9172-7
DOI :
10.1109/SFCS.1998.743521
