Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Pichler, S. Skritek:
"Tractable Counting of the Answers to Conjunctive Queries";
Vortrag: AMW - Alberto Mendelzon International Workshop on Foundations of Data Management,
Santiago, Chile;
09.05.2011
- 12.05.2011; in: "CEUR Workshop Proceedings",
P. Barceló, V. Tannen (Hrg.);
CEUR Workshop Proceedings,
749
(2011),
ISSN: 1613-0073;
Paper-Nr. 4,
12 S.
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.
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Service-orientierte Datenintegration
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.