2026-07-20T12:09:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7065 2024-03-06T10:39:24Z ddc:004 open_access

Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk) Marx, Dániel Conjunctive queries treewidth complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx 2017 Is Part Of LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2017.2 urn:nbn:de:0030-drops-70652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.2 eng https://creativecommons.org/licenses/by/3.0/legalcode