Verification of Generalized Inconsistency-Aware Knowledge and Action Bases

Diego Calvanese, Marco Montali, Ario SantosoIJCAI 2015

Introduction

In the design of complex organizational systems, developers must simultaneously manage static domain knowledge—the rules and structures governing data—and dynamic processes—the actions that modify that data over time. Knowledge and Action Bases (KABs) were developed to address this dual requirement, utilizing Description Logics (DL) for static modeling and transition systems for dynamic behavior. However, a persistent challenge in KAB research has been the management of data inconsistencies. When an automated action introduces data that violates a business rule, traditional systems often fail or revert to naive rejection. This paper introduces Golog-KABs (GKABs), a framework that provides a unified, verifiable approach to handling such inconsistencies through high-level process modeling.

The GKAB Framework

The authors extend the traditional KAB model by integrating it with a high-level programming language inspired by Golog. This integration allows for the definition of complex processes using standard programming constructs such as if-then-else blocks, while loops, and non-deterministic choices (|). By moving beyond simple condition-action rules, GKABs allow for more sophisticated control over how a system evolves.

Central to the GKAB framework is the introduction of Parametric Execution Semantics. The authors utilize an abstract "filter relation" to define how the system state transitions. This abstraction allows the framework to accommodate various inconsistency-handling strategies by simply "plugging in" different filters. Key strategies modeled include:

  • b-repair (bold): The system non-deterministically selects a maximal consistent subset of the data.
  • c-repair (certain): The system retains only the data present in every possible repair (the intersection of all repairs).
  • b-evolution: The system prioritizes newly added facts over conflicting legacy data.

Verification via Reduction

The core technical contribution of this research is the demonstration that inconsistency-aware semantics do not inherently increase the expressive power of the system from a verification standpoint. The authors show that a GKAB employing complex inconsistency-handling logic can be mathematically reduced to a "standard" GKAB that manages consistency naively.

This "compilation" approach suggests that inconsistency management can be viewed as "syntactic sugar." By using clever Golog programming and auxiliary data structures, the repair processes are internalized into the system's logic. For instance, a "bold repair" strategy can be modeled as a Golog loop that iteratively deletes conflicting facts until consistency is restored. This reduction is significant because it allows developers to use existing verification tools for standard KABs to check properties in inconsistency-aware systems.

Results and Decidability

The paper establishes several key theoretical results regarding the feasibility of verifying these systems:

  1. Decidability: The authors prove that for "run-bounded" systems—where the number of distinct objects involved in any single execution path is finite—the verification of first-order temporal properties (using $\mu L^{EQL}_A$ logic) is decidable.
  2. Model Checking: The verification problem is shown to be reducible to standard $\mu$-calculus finite-state model checking. This is achieved through Theorems 2 and 4, which formalize the recast of inconsistency-aware GKABs into standard KABs.
  3. Unified Semantics: The framework provides a single mathematical structure that accommodates a wide variety of previously disparate semantics, such as AR-repair and IAR-repair.

Discussion and Future Work

While the paper provides a robust theoretical foundation, it also identifies practical challenges. The reduction process involves duplicating concepts and roles to track the state of data before and after repairs, which may lead to a state-space explosion in practical implementations. Furthermore, the current model focuses on deterministic service calls (external data lookups), though the authors suggest that non-deterministic services could be integrated in future iterations.

Ultimately, the GKAB framework demonstrates that sophisticated data repair strategies can be formally verified without losing decidability. The authors suggest that this "filter" approach is general enough to be extended to more complex data cleaning workflows, marking a promising direction for future research in automated data management.

Summary updated

BibTeX
@inproceedings{calvanese2015verification,
  author = {Diego Calvanese and Marco Montali and Ario Santoso},
  title = {{Verification of Generalized Inconsistency-Aware Knowledge and Action Bases}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure