Coping with Incomplete Data: Recent Advances

Marco Console; Paolo Guagliardo; Leonid Libkin; Etienne Toussaint

doi:10.1145/3375395.3387970

Coping with Incomplete Data: Recent Advances

Marco Console, Paolo Guagliardo, Leonid Libkin, Etienne Toussaint

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently?

The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers

Original language	English
Title of host publication	PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Publisher	ACM
Pages	33-47
Number of pages	15
ISBN (Electronic)	978-1-4503-7108-7
DOIs	https://doi.org/10.1145/3375395.3387970
Publication status	Published - 14 Jun 2020
Event	2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States Duration: 14 Jun 2020 → 19 Jun 2020 https://sigmod2020.org/

Conference

Conference	2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated title	SIGMOD/PODS 2020
Country/Territory	United States
City	Portland
Period	14/06/20 → 19/06/20
Internet address	https://sigmod2020.org/

Keywords / Materials (for Non-textual outputs)

relational databases
incomplete information
certain answers
naive evaluation
approximate query answering
many-valued logics

Access to Document

10.1145/3375395.3387970Licence: All Rights Reserved

Coping with Incomplete_CONSOLE_DOA25032020_AFVAccepted author manuscript, 861 KBLicence: All Rights Reserved

https://dl.acm.org/doi/10.1145/3375395.3387970Licence: All Rights Reserved

MAGIC: MAnaGing InComplete Data - New Foundations
Libkin, L. (Principal Investigator)
EPSRC
1/10/16 → 31/08/22
Project: Research
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
EPSRC
1/04/15 → 30/09/20
Project: Research

Cite this

@inproceedings{c436e3b2426c4fc49100d2fa2e43c295,

title = "Coping with Incomplete Data: Recent Advances",

abstract = "Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently?The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers",

keywords = "relational databases, incomplete information, certain answers, naive evaluation, approximate query answering, many-valued logics",

author = "Marco Console and Paolo Guagliardo and Leonid Libkin and Etienne Toussaint",

year = "2020",

month = jun,

day = "14",

doi = "10.1145/3375395.3387970",

language = "English",

pages = "33--47",

booktitle = "PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems",

publisher = "ACM",

note = "2020 ACM SIGMOD/PODS International Conference on Management of Data, SIGMOD/PODS 2020 ; Conference date: 14-06-2020 Through 19-06-2020",

url = "https://sigmod2020.org/",

}

Console, M, Guagliardo, P , Libkin, L & Toussaint, E 2020, Coping with Incomplete Data: Recent Advances. in PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, pp. 33-47, 2020 ACM SIGMOD/PODS International Conference on Management of Data, Portland, Oregon, United States, 14/06/20. https://doi.org/10.1145/3375395.3387970

TY - GEN

T1 - Coping with Incomplete Data: Recent Advances

AU - Console, Marco

AU - Guagliardo, Paolo

AU - Libkin, Leonid

AU - Toussaint, Etienne

PY - 2020/6/14

Y1 - 2020/6/14

N2 - Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently?The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers

AB - Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently?The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers

KW - relational databases

KW - incomplete information

KW - certain answers

KW - naive evaluation

KW - approximate query answering

KW - many-valued logics

U2 - 10.1145/3375395.3387970

DO - 10.1145/3375395.3387970

M3 - Conference contribution

SP - 33

EP - 47

BT - PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - ACM

T2 - 2020 ACM SIGMOD/PODS International Conference on Management of Data

Y2 - 14 June 2020 through 19 June 2020

ER -

Coping with Incomplete Data: Recent Advances

Abstract

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

MAGIC: MAnaGing InComplete Data - New Foundations

VADA: Value Added Data Systems: Principles and Architecture

Cite this