Search Results

Documents authored by Skritek, Sebastian

Document
DOI: 10.4230/LIPIcs.ICDT.2023.10
Diversity of Answers to Conjunctive Queries

Authors: Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expensive if it is too big. In this case, outputting a small, sufficiently diverse subset of the solutions would be preferable. This leads to the Diverse-version of the original enumeration problem, where the goal is to achieve a certain level d of diversity by selecting k solutions. In this paper, we look at the Diverse-version of the query answering problem for Conjunctive Queries and extensions thereof. That is, we study the problem if it is possible to achieve a certain level d of diversity by selecting k answers to the given query and, in the positive case, to actually compute such k answers.
Cite as

Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek. Diversity of Answers to Conjunctive Queries. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{merkl_et_al:LIPIcs.ICDT.2023.10,
  author =	{Merkl, Timo Camillo and Pichler, Reinhard and Skritek, Sebastian},
  title =	{{Diversity of Answers to Conjunctive Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.10},
  URN =		{urn:nbn:de:0030-drops-177529},
  doi =		{10.4230/LIPIcs.ICDT.2023.10},
  annote =	{Keywords: Query Answering, Diversity of Solutions, Complexity, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.20
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection

Authors: Stefan Mengel and Sebastian Skritek

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtaining meaningful results over incomplete data sources as it is common in semantic web settings. Recently, a structural characterization of the classes of well-designed pattern trees that can be evaluated in polynomial time was shown. However, projection - a central feature of many query languages - was not considered in this study. We work towards closing this gap by giving a characterization of all tractable classes of simple well-designed pattern trees with projection (under some common complexity theoretic assumptions). Since well-designed pattern trees correspond to the fragment of well-designed {AND, OPTIONAL}-SPARQL queries this gives a complete description of the tractable classes of queries with projections in this fragment that can be characterized by the underlying graph structures of the queries.
Cite as

Stefan Mengel and Sebastian Skritek. Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mengel_et_al:LIPIcs.ICDT.2019.20,
  author =	{Mengel, Stefan and Skritek, Sebastian},
  title =	{{Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.20},
  URN =		{urn:nbn:de:0030-drops-103220},
  doi =		{10.4230/LIPIcs.ICDT.2019.20},
  annote =	{Keywords: SPARQL, well-designed pattern trees, query evaluation, FPT, characterizing tractable classes}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.22
On the Complexity of Enumerating the Answers to Well-designed Pattern Trees

Authors: Markus Kröll, Reinhard Pichler, and Sebastian Skritek

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Well-designed pattern trees (wdPTs) have been introduced as an extension of conjunctive queries to allow for partial matching - analogously to the OPTIONAL operator of the semantic web query language SPARQL. Several computational problems of wdPTs have been studied in recent years, such as the evaluation problem in various settings, the counting problem, as well as static analysis tasks including the containment and equivalence problems. Also restrictions needed to achieve tractability of these tasks have been proposed. In contrast, the problem of enumerating the answers to a wdPT has been largely ignored so far. In this work, we embark on a systematic study of the complexity of the enumeration problem of wdPTs. As our main result, we identify several tractable and intractable cases of this problem both from a classical complexity point of view and from a parameterized complexity point of view.
Cite as

Markus Kröll, Reinhard Pichler, and Sebastian Skritek. On the Complexity of Enumerating the Answers to Well-designed Pattern Trees. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kroll_et_al:LIPIcs.ICDT.2016.22,
  author =	{Kr\"{o}ll, Markus and Pichler, Reinhard and Skritek, Sebastian},
  title =	{{On the Complexity of Enumerating the Answers to Well-designed Pattern Trees}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.22},
  URN =		{urn:nbn:de:0030-drops-57912},
  doi =		{10.4230/LIPIcs.ICDT.2016.22},
  annote =	{Keywords: SPARQL, Pattern Trees, CQs, Enumeration, Complexity}
}
Document
DOI: 10.4230/DFU.Vol5.10452.185
Peer Data Management

Authors: Armin Roth and Sebastian Skritek

Published in: Dagstuhl Follow-Ups, Volume 5, Data Exchange, Integration, and Streams (2013)

Abstract
Peer Data Management (PDM) deals with the management of structured data in unstructured peer-to-peer (P2P) networks. Each peer can store data locally and define relationships between its data and the data provided by other peers. Queries posed to any of the peers are then answered by also considering the information implied by those mappings. The overall goal of PDM is to provide semantically well-founded integration and exchange of heterogeneous and distributed data sources. Unlike traditional data integration systems, peer data management systems (PDMSs) thereby allow for full autonomy of each member and need no central coordinator. The promise of such systems is to provide flexible data integration and exchange at low setup and maintenance costs. However, building such systems raises many challenges. Beside the obvious scalability problem, choosing an appropriate semantics that can deal with arbitrary, even cyclic topologies, data inconsistencies, or updates while at the same time allowing for tractable reasoning has been an area of active research in the last decade. In this survey we provide an overview of the different approaches suggested in the literature to tackle these problems, focusing on appropriate semantics for query answering and data exchange rather than on implementation specific problems.
Cite as

Armin Roth and Sebastian Skritek. Peer Data Management. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Volume 5, pp. 185-215, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{roth_et_al:DFU.Vol5.10452.185,
  author =	{Roth, Armin and Skritek, Sebastian},
  title =	{{Peer Data Management}},
  booktitle =	{Data Exchange, Integration, and Streams},
  pages =	{185--215},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-61-3},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{5},
  editor =	{Kolaitis, Phokion G. and Lenzerini, Maurizio and Schweikardt, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol5.10452.185},
  URN =		{urn:nbn:de:0030-drops-42949},
  doi =		{10.4230/DFU.Vol5.10452.185},
  annote =	{Keywords: Peer Data Management, PDM, Peer Data Management Systems, PDMS, Survey, P2P}
}
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 About DROPS Imprint Privacy Contact