LIPIcs.ICDT.2017.2.pdf
- Filesize: 236 kB
- 1 pages
Document
Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)
Author
-
Part of:
Volume:
20th International Conference on Database Theory (ICDT 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-17
Cite As Get BibTex
Dániel Marx. Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICDT.2017.2
Abstract
The complexity of evaluating conjunctive queries can depend significantly on the structure of the query. For example, it is well known that various notions of acyclicity can make the evaluation problem tractable. More generally, it seems that the complexity is connected to the "treelikeness" of the graph or hypergraph describing the query structure. In the lecture, we will review some of the notions of treelikeness that were proposed in the literature and how they are relevant for the complexity of evaluating conjunctive queries and related problems.
Subject Classification
Keywords
- Conjunctive queries
- treewidth
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads