Publications in Scientific Journals:

R. Pichler, S. Skritek:
"Tractable counting of the answers to conjunctive queries";
Journal of Computer and System Sciences (invited), 79 (2013), 6; 984 - 1001.

English abstract:
Conjunctive queries (CQs) are one of the most fundamental forms of database queries. In general, the evaluation of CQs is NP-complete. Consequently, there has been an intensive search for tractable fragments. In this paper, we want to initiate a systematic search for tractable fragments of the counting problem of CQs, i.e., the problem of counting the answers to a CQ. We prove several new tractability and intractability results by starting with acyclic conjunctive queries and generalising these results to CQs of bounded hypertree-width. We also extend our study to the counting problem of unions of CQs.

Computational complexity, Counting complexity, Query answering, Acyclic conjunctive query, Hypertree-width

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Related Projects:
Project Head Reinhard Pichler:
Service-orientierte Datenintegration

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung

Created from the Publication Database of the Vienna University of Technology.