2 Search Results for "Sirangelo, Cristina"

Document
DOI: 10.4230/LIPIcs.ICDT.2023.24
A Simple Algorithm for Consistent Query Answering Under Primary Keys

Authors: Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo

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

Abstract
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: 1) Initialize Δ with all sets S of at most k facts such that S⊧ q. 2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.
Cite as

Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.24,
  author =	{Figueira, Diego and Padmanabha, Anantha and Segoufin, Luc and Sirangelo, Cristina},
  title =	{{A Simple Algorithm for Consistent Query Answering Under Primary Keys}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{24:1--24:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.24},
  URN =		{urn:nbn:de:0030-drops-177663},
  doi =		{10.4230/LIPIcs.ICDT.2023.24},
  annote =	{Keywords: consistent query answering, primary keys, conjunctive queries}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.10
On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds

Authors: Henrik Forssell, Evgeny Kharlamov, and Evgenij Thorstensen

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

Abstract
Data exchange heavily relies on the notion of incomplete database instances. Several semantics for such instances have been proposed and include open (OWA), closed (CWA), and open-closed (OCWA) world. For all these semantics important questions are: whether one incomplete instance semantically implies another; when two are semantically equivalent; and whether a smaller or smallest semantically equivalent instance exists. For OWA and CWA these questions are fully answered. For several variants of OCWA, however, they remain open. In this work we adress these questions for Closed Powerset semantics and the OCWA semantics of [Leonid Libkin and Cristina Sirangelo, 2011]. We define a new OCWA semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and characterize semantic implication and equivalence in terms of such covers. This characterization yields a guess-and-check algorithm to decide equivalence, and shows that the problem is NP-complete. For the minimization problem we show that for several common notions of minimality there is in general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one can find, for any incomplete database, a unique finite set of its subinstances which are subinstances (up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We study properties of this set, and extend the analysis to OCWA*.
Cite as

Henrik Forssell, Evgeny Kharlamov, and Evgenij Thorstensen. On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{forssell_et_al:LIPIcs.ICDT.2020.10,
  author =	{Forssell, Henrik and Kharlamov, Evgeny and Thorstensen, Evgenij},
  title =	{{On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-119343},
  doi =		{10.4230/LIPIcs.ICDT.2020.10},
  annote =	{Keywords: Incomplete Databases, Cores, Semantics, Open and Closed Worlds}
}
  • Refine by Author
  • 1 Figueira, Diego
  • 1 Forssell, Henrik
  • 1 Kharlamov, Evgeny
  • 1 Padmanabha, Anantha
  • 1 Segoufin, Luc
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Database query languages (principles)
  • 1 Theory of computation → Incomplete, inconsistent, and uncertain databases

  • Refine by Keyword
  • 1 Cores
  • 1 Incomplete Databases
  • 1 Open and Closed Worlds
  • 1 Semantics
  • 1 conjunctive queries
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2023

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