A fundamental decision problem in the context of databases is deciding whether a conjunctive query produces a nonempty result. This problem, referred to as "Boolean Conjunctive Query (BCQ)" is NP-complete in general but is known to be feasible in polynomial time in case the relation schema of the join query forms an acyclic hypergraph, which happens very often in practice.
The known algorithms for evaluating Boolean acyclic conjunctive queries (ABCQ) are of inherently sequential nature and suggest that the problem may be P-complete; however, the precise complexity of ABCQ was unknown. We solve this issue by proving that ABCQ is LOGCFL-complete. The class LOGCFL consists of all problems/languages that are LOGSPACE reducible to a context-free language. Our result is quite surprising given that LOGCFL is a rather "low" complexity class contained in the parallel complexity classes AC1 and NC2. We exhibit parallel algorithms for solving ABCQ.
We show that a number of other relevant problems in the database and AI areas involving acyclic hypergraphs are logspace equivalent to ABCQ and thus LOGCFL-complete.
Joint work with N. Leone (Vienna) and F. Scarcello (Cosenza)
Referent: Prof. Dr. Georg Gottlob
Vorstand des Instituts für Informationssysteme
Abteilung für Datenbanken u. Expertensysteme
Paniglgasse 16,
A 1040 Wien
Zeitpunkt: Freitag, 18. Dezember 1998, 14 Uhr c. t.
Ort: HS 3 der Universität Klagenfurt