Scalar aggregation in inconsistent databases

Marcelo Arenas; Leopoldo Bertossi; Jan Chomicki; Xin He; Vijay Raghavan; Jeremy Spinrad

doi:10.1016/S0304-3975(02)00737-5

Scalar aggregation in inconsistent databases

Marcelo Arenas
, Leopoldo Bertossi
, Jan Chomicki
, Xin He
, Vijay Raghavan
, Jeremy Spinrad

Department of Computer Science and Engineering

University of Toronto
Carleton University
Vanderbilt University

Research output: Contribution to journal › Conference article › peer-review

114 Scopus citations

Abstract

We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce-Codd Normal Form) and present a practical hybrid query evaluation method.

Original language	English
Pages (from-to)	405-434
Number of pages	30
Journal	Theoretical Computer Science
Volume	296
Issue number	3
DOIs	https://doi.org/10.1016/S0304-3975(02)00737-5
State	Published - Mar 14 2003
Event	Database (ICDT) - London, United Kingdom Duration: Jan 4 2001 → Jan 6 2001

Access to Document

10.1016/S0304-3975(02)00737-5

Cite this

@article{4d00c2b3537f4fb68bda72f9499ad237,

title = "Scalar aggregation in inconsistent databases",

abstract = "We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce-Codd Normal Form) and present a practical hybrid query evaluation method.",

author = "Marcelo Arenas and Leopoldo Bertossi and Jan Chomicki and Xin He and Vijay Raghavan and Jeremy Spinrad",

year = "2003",

month = mar,

day = "14",

doi = "10.1016/S0304-3975(02)00737-5",

language = "English",

volume = "296",

pages = "405--434",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

note = "Database (ICDT) ; Conference date: 04-01-2001 Through 06-01-2001",

}

TY - JOUR

T1 - Scalar aggregation in inconsistent databases

AU - Arenas, Marcelo

AU - Bertossi, Leopoldo

AU - Chomicki, Jan

AU - He, Xin

AU - Raghavan, Vijay

AU - Spinrad, Jeremy

PY - 2003/3/14

Y1 - 2003/3/14

N2 - We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce-Codd Normal Form) and present a practical hybrid query evaluation method.

AB - We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce-Codd Normal Form) and present a practical hybrid query evaluation method.

UR - https://www.scopus.com/pages/publications/0037436756

U2 - 10.1016/S0304-3975(02)00737-5

DO - 10.1016/S0304-3975(02)00737-5

M3 - Conference article

AN - SCOPUS:0037436756

SN - 0304-3975

VL - 296

SP - 405

EP - 434

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

T2 - Database (ICDT)

Y2 - 4 January 2001 through 6 January 2001

ER -

Scalar aggregation in inconsistent databases

Abstract

Access to Document

Other files and links

Fingerprint

Cite this