License
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://drops.dagstuhl.de/opus/volltexte/2017/7065/
Go to the corresponding LIPIcs Volume Portal


Marx, Dániel

Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)

pdf-format:
LIPIcs-ICDT-2017-2.pdf (0.2 MB)


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
Seminar: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 14.03.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI