Certain Counting under the Open World Assumption

32 concepts13 papers1 proposal

In traditional relational databases, counting is straightforward. If a database contains three rows matching a query, the answer is three. This relies on the Closed World Assumption (CWA): anything not explicitly recorded in the database is assumed to be false.

However, modern knowledge representation systems and ontologies operate under the Open World Assumption (OWA), where missing information is treated as unknown rather than non-existent. As noted by Chari et al. and Eiter et al., this open-world nature makes asserting absolute aggregate values logically difficult. Because we cannot assume a dataset contains all relevant individuals, a standard count can be easily invalidated by the potential existence of unrecorded entities.

This creates a fundamental paradox for numerical aggregation. As Thorne et al. demonstrate, the traditional "certain answer" approach—which requires a query result to be identical across all possible interpretations—is fundamentally incompatible with standard counting. Because an open world allows for an arbitrary number of unseen individuals, the exact count fluctuates boundlessly across different valid worlds, rendering standard aggregate functions like averages or sums mathematically trivial or infinite (Kostylev and Reutter).

To resolve this, a specialized research direction has emerged: certain counting via lower bounds. Instead of seeking an absolute, exact count, these frameworks compute the minimum number of individuals that must exist to satisfy both the explicit data and the logical constraints of the ontology.


Shifting to Certain Lower Bounds

When data is incomplete, a query cannot return a single integer. Instead, systems must evaluate the range of possible counts across all valid models of the knowledge base (Bienvenu et al.; Bienvenu et al.).

Because we can always imagine a valid model containing an infinite number of additional, unrecorded individuals, the upper bound of a count is frequently infinite (Kostylev and Reutter). Consequently, the most informative and mathematically sound answer is the certain lower bound—the minimum possible count that remains valid across every potential interpretation (Kostylev and Reutter; Bienvenu et al.).

  Closed World:  [ Exact Count ] (Assumes complete data)

  Open World:    [ Minimum Count ] -----------------------> Infinity
                 ▲
                 └── Certain Lower Bound (What logically MUST exist)

This lower-bound perspective is not exclusive to ontologies; it also applies to incomplete databases operating under bag (multiset) semantics. As shown by Console et al., when querying incomplete databases where duplicate rows matter, determining the minimum number of occurrences for a query result tuple provides a reliable, efficiently computable lower bound on result frequencies.


The Challenge of Anonymous Individuals

A naive approach to finding a lower bound would be to simply count the unique, explicitly named constants in the dataset that match the query. This is known as epistemic semantics. However, as Kostylev and Reutter argue, epistemic semantics frequently underestimate the true count because they ignore the logical implications of the background knowledge.

Ontologies use rules (such as existential constraints) that mandate the existence of individuals, even if those individuals are not named in the data. For example, consider an ontology containing the rule: $$\text{MedicalClinic} \sqsubseteq \exists \text{hasStaff}.\text{Doctor}$$ If the dataset states that Clinic_A is a MedicalClinic, the system logically infers that at least one Doctor must exist associated with Clinic_A, even if no specific doctor is named in the database.

These inferred entities are called anonymous individuals. As Calvanese et al. and Bienvenu et al. emphasize, capturing this "anonymous contribution" is the core difficulty of open-world counting. If a query asks for the total number of doctors, a system that only counts named constants will incorrectly report zero, failing to reflect the logical reality that a doctor must exist.


The Merging Strategy: Building Intuition

How do we algorithmically compute the minimum number of individuals while accounting for these unseen, anonymous entities? The solution relies on a merging strategy (Bienvenu et al.).

To find the absolute minimum count, the system attempts to construct the most compact model possible that satisfies all logical constraints. It does this by aggressively "merging" anonymous individuals together, or merging them with known constants, unless an explicit constraint prevents it.

Imagine a knowledge base with three clinics: Clinic_A, Clinic_B, and Clinic_C. The ontology dictates that every clinic must have at least one doctor. This generates three anonymous doctors: $\text{doc}_A$, $\text{doc}_B$, and $\text{doc}_C$.

To find the lower bound of the total doctor count, the merging strategy asks: Can these anonymous individuals actually be the exact same person?

  1. Scenario 1 (No restrictions): If the ontology contains no rules stating that the clinics must have distinct doctors, the merging strategy collapses $\text{doc}_A$, $\text{doc}_B$, and $\text{doc}_C$ into a single individual. The certain lower bound for the doctor count is 1.
  2. Scenario 2 (Distinctness constraints): If the ontology includes a constraint stating that a doctor cannot work at more than two clinics, the system can merge $\text{doc}_A$ and $\text{doc}_B$, but $\text{doc}_C$ must remain separate. The certain lower bound becomes 2.

By distinguishing between individuals that must be distinct and those that could potentially be the same, this mechanism identifies the minimum cardinality required to satisfy the ontology (Kostylev and Reutter; Bienvenu et al.).


Computational Complexity and Trade-offs

Calculating these lower bounds introduces significant computational challenges because the system must reason about all potential interpretations (Bienvenu et al.).

For the popular DL-Lite family of description logics—which is widely celebrated because standard query answering is highly efficient (in $\text{AC}^0$ for data complexity)—introducing counting aggregates elevates the data complexity to coNP-complete (Kostylev and Reutter). This jump occurs because finding the minimal model requires solving a combinatorial puzzle of valid merges.

However, recent research has mapped out a nuanced complexity landscape to identify tractable boundaries:

  • Structural Restrictions: Bienvenu et al. identified that enforcing structural constraints like "rootedness" on counting conjunctive queries (CCQs) can significantly lower the computational cost.
  • Query Simplicity: Certain basic cardinality queries remain highly tractable (solvable within $\text{TC}^0$), as demonstrated by Bienvenu et al..
  • Expressive Logics: Even when moving from DL-Lite to more expressive description logics like $\mathcal{ELHI}_\perp$, the data complexity does not necessarily worsen, remaining within the same coNP class (Bienvenu et al.).

By formalizing the interplay between anonymous individuals and merging strategies, this body of work provides the theoretical foundation needed to perform reliable statistical and aggregate reasoning over open-world knowledge graphs.

Key Foundational Work

Answering Counting Aggregate Queries over Ontologies of the DL-Lite Family (2013) — contributed 7 concept elements to this direction.
Complexity of Answering Counting Aggregate Queries over DL-Lite (2013) — contributed 6 concept elements to this direction.
Aggregate queries over ontologies (2008) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 11 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_lower_bound_aggregate_semantics_82f92f6c,
  title = {lower-bound aggregate semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lower-bound-aggregate-semantics/rdr_82f92f6c7a394048be47f43b3f1226de},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_lower_bound_aggregate_semantics_82f92f6c_v2,
  title = {lower-bound aggregate semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lower-bound-aggregate-semantics/rdr_82f92f6c7a394048be47f43b3f1226de/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake