3 Search Results for "Gogacz, Tomasz"

Document
DOI: 10.4230/LIPIcs.ICDT.2024.22
Evaluating Graph Queries Using Semantic Treewidth

Authors: Cristina Feier, Tomasz Gogacz, and Filip Murlak

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
Unions of conjunctive two-way regular path queries (UC2RPQs) are a common abstraction of query languages for graph databases, much like unions of conjunctive queries (UCQs) in the relational case. As in the case of UCQs, their evaluation is NP-complete in combined complexity. Semantic tree-width, i.e. the minimal treewidth of equivalent queries, has been proposed as a candidate criterion to characterize fixed-parameter tractability of UC2RPQs. It was recently shown how to decide the semantic tree-width of a UC2RPQ, by constructing the best under-approximation of a given treewidth, in the form of a UC2RPQ of size doubly exponential in the size of the original query. This leads to an fpt algorithm for evaluating UC2RPQs of semantic TW k which runs in time doubly exponential in the size of the parameter, i.e. in the UC2RPQ. Here we describe a more efficient fpt algorithm for evaluating UC2RPQs of semantic treewidth k which runs in time singly exponential in the size of the parameter. We do this by a careful construction of a witness query which, while still being doubly exponential, can be represented as a Datalog program of bounded width and singly exponential size.
Cite as

Cristina Feier, Tomasz Gogacz, and Filip Murlak. Evaluating Graph Queries Using Semantic Treewidth. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feier_et_al:LIPIcs.ICDT.2024.22,
  author =	{Feier, Cristina and Gogacz, Tomasz and Murlak, Filip},
  title =	{{Evaluating Graph Queries Using Semantic Treewidth}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.22},
  URN =		{urn:nbn:de:0030-drops-198048},
  doi =		{10.4230/LIPIcs.ICDT.2024.22},
  annote =	{Keywords: conjunctive two-way regular path queries, fixed-parameter tractable evaluation, semantic treewidth, Datalog encoding, optimization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2020.2
What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk)

Authors: Jerzy Marcinkowski

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
This paper was written as the companion paper of the ICDT 2020 invited tutorial. Query determinacy is a broad topic, with literally hundreds of papers published since late 1980s. This paper is not going to be a "survey" but rather a personal perspective of a person somehow involved in the recent developments in the area. First I explain how, in the last 30+ years, the question of determinacy was formalized. There are many parameters here: obviously one needs to choose the query language of the available views and the query language of the query itself. But - surprisingly - there is also some choice regarding what the word "to compute" actually means in this context. Then I concentrate on certain variants of the decision problem of determinacy (for each choice of parameters there is one such problem) and explain how I understand the mechanisms rendering such variants of determinacy decidable or undecidable. This is on a rather informal level. No really new theorems are presented, but I show some improvements of existing theorems and also simplified proofs of some of the earlier results.
Cite as

Jerzy Marcinkowski. What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk). In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{marcinkowski:LIPIcs.ICDT.2020.2,
  author =	{Marcinkowski, Jerzy},
  title =	{{What Makes a Variant of Query Determinacy (Un)Decidable?}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.2},
  URN =		{urn:nbn:de:0030-drops-119265},
  doi =		{10.4230/LIPIcs.ICDT.2020.2},
  annote =	{Keywords: database theory, query, view, determinacy}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.15
Entropy Bounds for Conjunctive Queries with Functional Dependencies

Authors: Tomasz Gogacz and Szymon Torunczyk

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive query Q applied to a database D satisfying given functional dependencies. We provide a characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by [Gottlob, Lee, Valiant and Valiant, J.ACM, 2012] is tight, and that a correspondence of [Chan and Yeung, ACM TOIT, 2002] is preserved in the presence of functional dependencies. However, tightness of a weaker upper bound provided by Gottlob et al., which would have immediate applications to evaluation of join queries ([Khamis, Ngo, and Suciu, PODS, 2016]) remains open. Our result shows that the problem of computing the worst-case size bound, in the general case, is closely related to difficult problems from information theory.
Cite as

Tomasz Gogacz and Szymon Torunczyk. Entropy Bounds for Conjunctive Queries with Functional Dependencies. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gogacz_et_al:LIPIcs.ICDT.2017.15,
  author =	{Gogacz, Tomasz and Torunczyk, Szymon},
  title =	{{Entropy Bounds for Conjunctive Queries with Functional Dependencies}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.15},
  URN =		{urn:nbn:de:0030-drops-70479},
  doi =		{10.4230/LIPIcs.ICDT.2017.15},
  annote =	{Keywords: database theory, conjunctive queries, size bounds, entropy, finite groups, entropy cone}
}
  • Refine by Author
  • 2 Gogacz, Tomasz
  • 1 Feier, Cristina
  • 1 Marcinkowski, Jerzy
  • 1 Murlak, Filip
  • 1 Torunczyk, Szymon

  • Refine by Classification
  • 1 Information systems → Query languages
  • 1 Theory of computation → Automated reasoning
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Database theory
  • 1 Theory of computation → Regular languages
  • Show More...

  • Refine by Keyword
  • 2 database theory
  • 1 Datalog encoding
  • 1 conjunctive queries
  • 1 conjunctive two-way regular path queries
  • 1 determinacy
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2017
  • 1 2020
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact