Relational theories with null values and non-herbrand stable models

Vladimir Lifschitz, Karl Pichotta, Fangkai Yang

Introduction

For decades, a conceptual divide has existed between the theoretical foundations of relational databases and the practical application of logic programming. In the 1980s, Ray Reiter proposed a logical framework for databases capable of handling incomplete information, such as disjunctive facts and null values. However, implementing these theories has been difficult because they often relax the Unique Name Assumption (UNA)—the premise that distinct constants always represent distinct entities. In contrast, modern Answer Set Programming (ASP) solvers, like clingo, are fundamentally built upon the UNA and generate Herbrand models. This paper introduces a methodology to utilize these efficient solvers to find models for theories where the UNA is relaxed.

Handling Incompleteness in Databases

Reiter’s framework addresses two primary forms of incompleteness:

  1. Disjunction: Scenarios where it is known that "Supplier A provides Part 1 OR Part 3," without specifying which (or if both).
  2. Null Values: Situations where it is known that "Some supplier provides Part 3," but the identity of that supplier is unknown. This "null" entity might be an existing known supplier or a previously unidentified one.

The core challenge is that in a database with null values, a "null" constant might actually refer to the same object as a "known" constant. Standard ASP solvers would treat them as distinct by default.

Methodology: Simulating Non-Unique Names

The authors developed a general method to calculate stable models under the Domain Closure Assumption (DCA)—which assumes every object in the universe is named—while relaxing the UNA.

The process involves a Syntactic Transformation ($F \mapsto F'_{Eq}$), where every instance of the equality symbol ($=$) is replaced with a new binary predicate, eq/2. To ensure this predicate behaves as true equality, the authors introduce an Equality Axiomatization that enforces reflexivity, symmetry, transitivity, and the substitution property (e.g., if eq(a, b) is true, then any property of a must also apply to b).

To automate this, the authors created nonH.py, a Python-based preprocessor. This tool takes a standard logic program and outputs a version that simulates non-unique names, allowing standard Herbrand-based solvers like claspD to explore the space of non-Herbrand models.

Key Results and Implementation

The authors provide rigorous proofs (Theorems 1-4) establishing that their logic programming translation is both sound and complete relative to Reiter’s original first-order semantics. They demonstrate that for any relational theory, there exists an equivalent logic program whose answer sets correspond exactly to the theory's models.

Using the nonH.py script alongside the gringo grounder and claspD solver, the authors successfully identified all non-isomorphic models for complex database scenarios. For instance, in a scenario involving a null value $\omega$, the system correctly identifies three distinct possibilities: $\omega$ is a new supplier, $\omega$ is Supplier A, or $\omega$ is Supplier B.

The output of the ASP solver showing three distinct models (answers) for a database scenario with incomplete information. Each answer represents a possible world consistent with the provided facts.

By leveraging modern "cardinality constraints" (e.g., 1{A, B}), the authors created significantly more compact and readable encodings than those produced by earlier attempts in the 1990s.

Conclusion and Future Work

This work demonstrates that ASP is a natural and powerful computational engine for Reiter’s "possible world" semantics. By treating equality as a standard predicate defined by specific rules, the authors have enabled the use of high-performance solvers for non-Herbrand model generation.

While the current method relies on the Domain Closure Assumption and faces scaling challenges as the number of constants increases, it opens new doors for "First-Order ASP." Future work may involve integrating this preprocessor with tools like f2lp to handle even more complex first-order formulas, moving toward a more unified logic programming ecosystem.

Summary updated

BibTeX
@article{lifschitz2012relational,
  author = {Vladimir Lifschitz and Karl Pichotta and Fangkai Yang},
  title = {{Relational theories with null values and non-herbrand stable models}},
  journal = {Theory Pract. Log. Program.},
  year = {2012},
  doi = {10.1017/s147106841200018x},
}
Figure