Zeitschriftenartikel:
R. Pichler, S. Skritek:
"Tractable counting of the answers to conjunctive queries";
Journal of Computer and System Sciences (eingeladen),
79
(2013),
6;
S. 984
- 1001.
Kurzfassung englisch:
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.
Schlagworte:
Computational complexity, Counting complexity, Query answering, Acyclic conjunctive query, Hypertree-width
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.jcss.2013.01.012
Elektronische Version der Publikation:
http://dx.doi.org/10.1016/j.jcss.2013.01.012
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Service-orientierte Datenintegration
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.