Search Results

Documents authored by Pichler, Reinhard

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.MFCS.2020.41
Fractional Covers of Hypergraphs with Bounded Multi-Intersection

Authors: Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. This allows us to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤ k for some constant k. We also show how our results translate to fractional vertex covers.
Cite as

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. Fractional Covers of Hypergraphs with Bounded Multi-Intersection. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gottlob_et_al:LIPIcs.MFCS.2020.41,
  author =	{Gottlob, Georg and Lanzinger, Matthias and Pichler, Reinhard and Razgon, Igor},
  title =	{{Fractional Covers of Hypergraphs with Bounded Multi-Intersection}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.41},
  URN =		{urn:nbn:de:0030-drops-127317},
  doi =		{10.4230/LIPIcs.MFCS.2020.41},
  annote =	{Keywords: Fractional graph theory, fractional edge cover, fractional hypertree width, bounded multi-intersection, fractional cover, fractional vertex cover}
}
Document
DOI: 10.4230/DagRep.9.5.89
Enumeration in Data Management (Dagstuhl Seminar 19211)

Authors: Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt

Published in: Dagstuhl Reports, Volume 9, Issue 5 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19211 "Enumeration in Data Management". The goal of the seminar was to bring together researchers from various fields of computer science, including the Databases, Computational Logic, and Algorithms communities, and establish the means of collaboration towards considerable progress on the topic. Specifically, we aimed at understanding the recent developments, identifying the important open problems, and initiating collaborative efforts towards solutions thereof. In addition, we aimed to build and disseminate a toolkit for data-centric enumeration problems, including algorithmic techniques, proof techniques, and important indicator problems. Towards the objectives, the seminar included tutorials on the topic, invited talks, presentations of open problems, working groups on the open problems, discussions on platforms to compile the community knowledge, and the construction of various skeletons of such compilations.
Cite as

Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt. Enumeration in Data Management (Dagstuhl Seminar 19211). In Dagstuhl Reports, Volume 9, Issue 5, pp. 89-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{boros_et_al:DagRep.9.5.89,
  author =	{Boros, Endre and Kimelfeld, Benny and Pichler, Reinhard and Schweikardt, Nicole},
  title =	{{Enumeration in Data Management (Dagstuhl Seminar 19211)}},
  pages =	{89--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{5},
  editor =	{Boros, Endre and Kimelfeld, Benny and Pichler, Reinhard and Schweikardt, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.5.89},
  URN =		{urn:nbn:de:0030-drops-113822},
  doi =		{10.4230/DagRep.9.5.89},
  annote =	{Keywords: constant delay, databases, dynamic complexity, enumeration, polynomial delay, query evaluation}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.16
Datalog: Bag Semantics via Set Semantics

Authors: Leopoldo Bertossi, Georg Gottlob, and Reinhard Pichler

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

Abstract
Duplicates in data management are common and problematic. In this work, we present a translation of Datalog under bag semantics into a well-behaved extension of Datalog, the so-called warded Datalog^+/-, under set semantics. From a theoretical point of view, this allows us to reason on bag semantics by making use of the well-established theoretical foundations of set semantics. From a practical point of view, this allows us to handle the bag semantics of Datalog by powerful, existing query engines for the required extension of Datalog. This use of Datalog^+/- is extended to give a set semantics to duplicates in Datalog^+/- itself. We investigate the properties of the resulting Datalog^+/- programs, the problem of deciding multiplicities, and expressibility of some bag operations. Moreover, the proposed translation has the potential for interesting applications such as to Multiset Relational Algebra and the semantic web query language SPARQL with bag semantics.
Cite as

Leopoldo Bertossi, Georg Gottlob, and Reinhard Pichler. Datalog: Bag Semantics via Set Semantics. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bertossi_et_al:LIPIcs.ICDT.2019.16,
  author =	{Bertossi, Leopoldo and Gottlob, Georg and Pichler, Reinhard},
  title =	{{Datalog: Bag Semantics via Set Semantics}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{16:1--16:19},
  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.16},
  URN =		{urn:nbn:de:0030-drops-103188},
  doi =		{10.4230/LIPIcs.ICDT.2019.16},
  annote =	{Keywords: Datalog, duplicates, multisets, query answering, chase, Datalog+/-}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.19
Limits of Schema Mappings

Authors: Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov

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

Abstract
Schema mappings have been extensively studied in the context of data exchange and data integration, where they have turned out to be the right level of abstraction for formalizing data inter-operability tasks. Up to now and for the most part, schema mappings have been studied as static objects, in the sense that each time the focus has been on a single schema mapping of interest or, in the case of composition, on a pair of schema mappings of interest. In this paper, we adopt a dynamic viewpoint and embark on a study of sequences of schema mappings and of the limiting behavior of such sequences. To this effect, we first introduce a natural notion of distance on sets of finite target instances that expresses how "close" two sets of target instances are as regards the certain answers of conjunctive queries on these sets. Using this notion of distance, we investigate pointwise limits and uniform limits of sequences of schema mappings, as well as the companion notions of pointwise Cauchy and uniformly Cauchy sequences of schema mappings. We obtain a number of results about the limits of sequences of GAV schema mappings and the limits of sequences of LAV schema mappings that reveal striking differences between these two classes of schema mappings. We also consider the completion of the metric space of sets of target instances and obtain concrete representations of limits of sequences of schema mappings in terms of generalized schema mappings, i.e., schema mappings with infinite target instances as solutions to (finite) source instances.
Cite as

Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger, and Vadim Savenkov. Limits of Schema Mappings. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kolaitis_et_al:LIPIcs.ICDT.2016.19,
  author =	{Kolaitis, Phokion G. and Pichler, Reinhard and Sallinger, Emanuel and Savenkov, Vadim},
  title =	{{Limits of Schema Mappings}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{19:1--19:17},
  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.19},
  URN =		{urn:nbn:de:0030-drops-57882},
  doi =		{10.4230/LIPIcs.ICDT.2016.19},
  annote =	{Keywords: Limit, Pointwise convergence, Uniform convergence, Schema mapping}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.21
Complexity of Repair Checking and Consistent Query Answering

Authors: Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger

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

Abstract
Inconsistent databases (i.e., databases violating some given set of integrity constraints) may arise in many applications such as, for instance, data integration. Hence, the handling of inconsistent data has evolved as an active field of research. In this paper, we consider two fundamental problems in this context: Repair Checking (RC) and Consistent Query Answering (CQA). So far, these problems have been mainly studied from the point of view of data complexity (where all parts of the input except for the database are considered as fixed). While for some kinds of integrity constraints, also combined complexity (where all parts of the input are allowed to vary) has been considered, for several other kinds of integrity constraints, combined complexity has been left unexplored. Moreover, a more detailed analysis (keeping other parts of the input fixed - e.g., the constraints only) is completely missing. The goal of our work is a thorough analysis of the complexity of the RC and CQA problems. Our contribution is a complete picture of the complexity of these problems for a wide range of integrity constraints. Our analysis thus allows us to get a better understanding of the true sources of complexity.
Cite as

Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger. Complexity of Repair Checking and Consistent Query Answering. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arming_et_al:LIPIcs.ICDT.2016.21,
  author =	{Arming, Sebastian and Pichler, Reinhard and Sallinger, Emanuel},
  title =	{{Complexity of Repair Checking and Consistent Query Answering}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-57900},
  doi =		{10.4230/LIPIcs.ICDT.2016.21},
  annote =	{Keywords: inconsistency, consistent query answering, complexity}
}
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}
}
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