PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
March 21, 20260 citationsOpen Access

Computing Consistent Least Upper Bounds in Aggregate Logic

View Full Paper
AKAziz Amezian El KhalfiouiJWJef Wijsen

Key Points

  • The aim is to compute the least upper bound (lub) for numerical queries on inconsistent databases.
  • Analyzed the problem of answering conjunctive queries with aggregation on databases violating primary key constraints.
  • Introduced the concept of κ-acyclicity for self-join-free conjunctive queries.
  • Developed a method for computing the lub through rewriting in first-order aggregate logic if queries are κ-acyclic.
  • Demonstrated that if a SUM-query is κ-acyclic, the lub can be computed easily.
  • Established that the computation extends to all monotone and associative aggregate operators.
  • Showed that if a SUM-query is not κ-acyclic, computing the lub in first-order aggregate logic is impossible.

Abstract

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 κ-acyclicity for self-join-free conjunctive queries. We show that if the body of a SUM-query is κ-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 κ-acyclic, then the lub cannot be computed in first-order aggregate logic.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Khalfioui et al. (2026) studied this question.

synapsesocial.com/papers/69be356f6e48c4981c673a7ehttps://doi.org/10.4230/lipics.icdt.2026.4
Ask AI
Helpful
Bookmark
Share
View Full Paper