.png){kind=icon}
Return
Computing Consistent Least Upper Bounds in Aggregate Logic
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.ICDT.2026.4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the problem of answering conjunctive queries with aggregation on database instances that may violate primary key constraints. In SQL, these queries follow the SELECT-FROM-WHERE-GROUP BY format, where the WHERE clause involves a conjunction of equalities, and the SELECT clause can incorporate aggregate operators like MAX, MIN, SUM, AVG, or COUNT. Repairs of a database instance are defined as inclusion-maximal subsets that satisfy all primary keys. The range-consistent answer to a numerical query over an inconsistent database is a pair [glb, lub], where glb and lub are, respectively, the smallest and the greatest results returned by the query over all possible repairs. While previous work has focused on the computation of the glb, the current paper studies the computation of the lub for a numerical domain of non-negative rational numbers. We introduce the notion of kappa-acyclicity for self-join-free conjunctive queries. We show that if the body of a SUM-query is kappa-acyclic, then the lub can be computed through a rewriting in first-order aggregate logic. Moreover, we show that this result extends to all aggregate operators that are monotone and associative. Importantly, we also prove the inverse: if the body of a SUM-query is not kappa-acyclic, then the lub cannot be computed in first-order aggregate logic.
Keywords:
Consistent query answering
primary key
conjunctive query
aggregate logic
Journal
2
IF:
0
Papers:
28
Citations:
0
Organization
Cited Papers
No cited papers available