1 Search Results for "Imber, Aviram"

The Consistency of Probabilistic Databases with Independent Cells

Authors: Amir Gilad, Aviram Imber, and Benny Kimelfeld

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

A probabilistic database with attribute-level uncertainty consists of relations where cells of some attributes may hold probability distributions rather than deterministic content. Such databases arise, implicitly or explicitly, in the context of noisy operations such as missing data imputation, where we automatically fill in missing values, column prediction, where we predict unknown attributes, and database cleaning (and repairing), where we replace the original values due to detected errors or violation of integrity constraints. We study the computational complexity of problems that regard the selection of cell values in the presence of integrity constraints. More precisely, we focus on functional dependencies and study three problems: (1) deciding whether the constraints can be satisfied by any choice of values, (2) finding a most probable such choice, and (3) calculating the probability of satisfying the constraints. The data complexity of these problems is determined by the combination of the set of functional dependencies and the collection of uncertain attributes. We give full classifications into tractable and intractable complexities for several classes of constraints, including a single dependency, matching constraints, and unary functional dependencies.

Cite as

Amir Gilad, Aviram Imber, and Benny Kimelfeld. The Consistency of Probabilistic Databases with Independent Cells. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 22:1-22:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

  author =	{Gilad, Amir and Imber, Aviram and Kimelfeld, Benny},
  title =	{{The Consistency of Probabilistic Databases with Independent Cells}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-177644},
  doi =		{10.4230/LIPIcs.ICDT.2023.22},
  annote =	{Keywords: Probabilistic databases, attribute-level uncertainty, functional dependencies, most probable database}
  • Refine by Author
  • 1 Gilad, Amir
  • 1 Imber, Aviram
  • 1 Kimelfeld, Benny

  • Refine by Classification
  • 1 Information systems → Data management systems

  • Refine by Keyword
  • 1 Probabilistic databases
  • 1 attribute-level uncertainty
  • 1 functional dependencies
  • 1 most probable database

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail