Scalar aggregation in inconsistent databases

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.

Authors

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

Keywords

No keywords are indexed for this paper.