License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2017.2
URN: urn:nbn:de:0030-drops-70652
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7065/
Marx, Dániel
Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)
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.
BibTeX - Entry
@InProceedings{marx:LIPIcs:2017:7065,
author = {D{\'a}niel Marx},
title = {{Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)}},
booktitle = {20th International Conference on Database Theory (ICDT 2017)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-024-8},
ISSN = {1868-8969},
year = {2017},
volume = {68},
editor = {Michael Benedikt and Giorgio Orsi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7065},
URN = {urn:nbn:de:0030-drops-70652},
doi = {10.4230/LIPIcs.ICDT.2017.2},
annote = {Keywords: Conjunctive queries, treewidth, complexity}
}
|
Keywords: |
|
Conjunctive queries, treewidth, complexity |
|
Collection: |
|
20th International Conference on Database Theory (ICDT 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
17.03.2017 |
