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.
Keywords:
Computational complexity, Counting complexity, Query answering, Acyclic conjunctive query, Hypertree-width
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.jcss.2013.01.012
Electronic version of the publication:
http://dx.doi.org/10.1016/j.jcss.2013.01.012
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.