Querying Incomplete Numerical Data: Between Certain and Possible Answers

Marco Console, Leonid Libkin, Liat Peterfreund

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Queries with aggregation and arithmetic operations, as well as incomplete data, are common in real-world database, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide ad-hoc rules for numerical nulls, on the other, theoretical research largely concentrates on the standard notions of certain and possible answers. In the presence of numerical attributes and aggregates, however, these answers are often meaningless, returning either too little or too much. Our goal is to define a principled framework for databases with numerical nulls and answering queries with arithmetic and aggregations over them. Towards this goal, we assume that missing values in numerical attributes are given by probability distributions associated with marked nulls. This yields a model of probabilistic bag databases in which tuples are not necessarily independent since nulls can repeat. We provide a general compositional framework for query answering and then concentrate on queries that resemble standard SQL with arithmetic and aggregation. We show that these queries are measurable, and their outputs have a finite representation. Moreover, since the classical forms of answers provide little information in the numerical setting, we look at the probability that numerical values in output tuples belong to specific intervals. Even though their exact computation is intractable, we show efficient approximation algorithms to compute such probabilities.
Original languageEnglish
Title of host publicationProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’23)
PublisherACM Association for Computing Machinery
Pages349-358
ISBN (Electronic)9798400701276
DOIs
Publication statusPublished - 18 Jun 2023
Event42nd ACM Symposium on Principles of Database Systems - Seattle , United States
Duration: 18 Jun 202323 Jun 2023
https://2023.sigmod.org/

Publication series

NamePODS '23
PublisherAssociation for Computing Machinery

Symposium

Symposium42nd ACM Symposium on Principles of Database Systems
Abbreviated titlePODS 2023
Country/TerritoryUnited States
CitySeattle
Period18/06/2323/06/23
Internet address

Keywords / Materials (for Non-textual outputs)

  • nulls
  • numerical attributes
  • aggregate queries
  • probabilistic databases
  • approximations
  • certain and possible answers

Fingerprint

Dive into the research topics of 'Querying Incomplete Numerical Data: Between Certain and Possible Answers'. Together they form a unique fingerprint.

Cite this