Search Results

Documents authored by Wieczorek, Piotr

Document
DOI: 10.4230/LIPIcs.CONCUR.2023.3
Reachability and Bounded Emptiness Problems of Constraint Automata with Prefix, Suffix and Infix

Authors: Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
We study constraint automata, which are finite-state automata over infinite alphabets consisting of tuples of words. A constraint automaton can compare the words of the consecutive tuples using Boolean combinations of the relations prefix, suffix, infix and equality. First, we show that the reachability problem of such automata is PSpace-complete. Second, we study automata over infinite sequences with Büchi conditions. We show that the problem: given a constraint automaton, is there a bound B and a sequence of tuples of words of length bounded by B, which is accepted by the automaton, is also PSpace-complete. These results contribute towards solving the long-standing open problem of the decidability of the emptiness problem for constraint automata, in which the words can have arbitrary lengths.
Cite as

Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek. Reachability and Bounded Emptiness Problems of Constraint Automata with Prefix, Suffix and Infix. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{michaliszyn_et_al:LIPIcs.CONCUR.2023.3,
  author =	{Michaliszyn, Jakub and Otop, Jan and Wieczorek, Piotr},
  title =	{{Reachability and Bounded Emptiness Problems of Constraint Automata with Prefix, Suffix and Infix}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.3},
  URN =		{urn:nbn:de:0030-drops-189971},
  doi =		{10.4230/LIPIcs.CONCUR.2023.3},
  annote =	{Keywords: constraint automata, emptiness problem}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2022.14
Inference of Shape Graphs for Graph Databases

Authors: Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
We investigate the problem of constructing a shape graph that describes the structure of a given graph database. We employ the framework of grammatical inference, where the objective is to find an inference algorithm that is both sound, i.e., always producing a schema that validates the input graph, and complete, i.e., able to produce any schema, within a given class of schemas, provided that a sufficiently informative input graph is presented. We identify a number of fundamental limitations that preclude feasible inference. We present inference algorithms based on natural approaches that allow to infer schemas that we argue to be of practical importance.
Cite as

Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek. Inference of Shape Graphs for Graph Databases. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{groz_et_al:LIPIcs.ICDT.2022.14,
  author =	{Groz, Beno\^{i}t and Lemay, Aur\'{e}lien and Staworko, S{\l}awek and Wieczorek, Piotr},
  title =	{{Inference of Shape Graphs for Graph Databases}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.14},
  URN =		{urn:nbn:de:0030-drops-158889},
  doi =		{10.4230/LIPIcs.ICDT.2022.14},
  annote =	{Keywords: RDF, Schema, Inference, Learning, Fitting, Minimality, Containment}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.43
Querying Best Paths in Graph Databases

Authors: Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Querying graph databases has recently received much attention. We propose a new approach to this problem, which balances competing goals of expressive power, language clarity and computational complexity. A distinctive feature of our approach is the ability to express properties of minimal (e.g. shortest) and maximal (e.g. most valuable) paths satisfying given criteria. To express complex properties in a modular way, we introduce labelling-generating ontologies. The resulting formalism is computationally attractive - queries can be answered in non-deterministic logarithmic space in the size of the database.
Cite as

Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek. Querying Best Paths in Graph Databases. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{michaliszyn_et_al:LIPIcs.FSTTCS.2017.43,
  author =	{Michaliszyn, Jakub and Otop, Jan and Wieczorek, Piotr},
  title =	{{Querying Best Paths in Graph Databases}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.43},
  URN =		{urn:nbn:de:0030-drops-83989},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.43},
  annote =	{Keywords: graph databases, queries, aggregation}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2015.144
Characterizing XML Twig Queries with Examples

Authors: Slawek Staworko and Piotr Wieczorek

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract
Typically, a (Boolean) query is a finite formula that defines a possibly infinite set of database instances that satisfy it (positive examples), and implicitly, the set of instances that do not satisfy the query (negative examples). We investigate the following natural question: for a given class of queries, is it possible to characterize every query with a finite set of positive and negative examples that no other query is consistent with. We study this question for twig queries and XML databases. We show that while twig queries are characterizable, they generally require exponential sets of examples. Consequently, we focus on a practical subclass of anchored twig queries and show that not only are they characterizable but also with polynomially-sized sets of examples. This result is obtained with the use of generalization operations on twig queries, whose application to an anchored twig query yields a properly contained and minimally different query. Our results illustrate further interesting and strong connections between the structure and the semantics of anchored twig queries that the class of arbitrary twig queries does not enjoy. Finally, we show that the class of unions of twig queries is not characterizable.
Cite as

Slawek Staworko and Piotr Wieczorek. Characterizing XML Twig Queries with Examples. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 144-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{staworko_et_al:LIPIcs.ICDT.2015.144,
  author =	{Staworko, Slawek and Wieczorek, Piotr},
  title =	{{Characterizing XML Twig Queries with Examples}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{144--160},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.144},
  URN =		{urn:nbn:de:0030-drops-49828},
  doi =		{10.4230/LIPIcs.ICDT.2015.144},
  annote =	{Keywords: Query characterization, Query examples, Query fitting, Twig queries}
}
Document
DOI: 10.4230/DFU.Vol5.10452.129
Query Processing in Data Integration

Authors: Paolo Guagliardo and Piotr Wieczorek

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

Abstract
In this chapter we illustrate the main techniques for processing queries in data integration. The first part of the chapter focuses on the problem of query answering in the relational setting, and describes approaches based on variants of the chase, along with how to deal with integrity constraints and access patterns. The second part of the chapter investigates query processing in the context of semistructured data, which is best described by graph-based data models, where the expressiveness of query languages not common in traditional database systems allows to point out the subtle differences between query answering and query rewriting. The chapter is closed by a very brief discussion of query processing in data integration with XML and ontologies.
Cite as

Paolo Guagliardo and Piotr Wieczorek. Query Processing in Data Integration. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Volume 5, pp. 129-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{guagliardo_et_al:DFU.Vol5.10452.129,
  author =	{Guagliardo, Paolo and Wieczorek, Piotr},
  title =	{{Query Processing in Data Integration}},
  booktitle =	{Data Exchange, Integration, and Streams},
  pages =	{129--160},
  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.129},
  URN =		{urn:nbn:de:0030-drops-42929},
  doi =		{10.4230/DFU.Vol5.10452.129},
  annote =	{Keywords: Query processing, Data integration, Relational data, Semistructured data}
}
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