Enhancing Disjunctive Datalog by constraints

TLDR

Disjunctive Datalog can be extended with integrity constraints, which come in two forms: strong constraints that must always hold and weak constraints that are satisfied if possible and whose violations are minimized. This paper proposes an extension of Disjunctive Datalog, called DATALOG^V,~c, that incorporates both strong and weak integrity constraints. The authors formally define DATALOG^V,~c, provide a declarative semantics that can be layered over any existing DATALOG^V,~ semantics, and analyze its computational complexity and expressiveness. The extended language is shown to be well suited for common‑sense reasoning and knowledge‑based problems in planning, graph theory optimization, and abductive reasoning, and it significantly increases modeling power compared to the original DATALOG^V,~.

Abstract

This paper presents an extension of Disjunctive Datalog (DATALOG/sup V,/spl sim//) by integrity constraints. These are of two types: strong, that is, classical integrity constraints and weak, that is, constraints that are satisfied if possible. While strong constraints must be satisfied, weak constraints express desiderata, that is, they may be violated-actually, their semantics tends to minimize the number of violated instances of weak constraints. Weak constraints may be ordered according to their importance to express different priority levels. As a result, the proposed language (call it, DATALOG/sup V,/spl sim/,c/) is well-suited to represent common sense reasoning and knowledge-based problems arising in different areas of computer science such as planning, graph theory optimizations, and abductive reasoning. The formal definition of the language is first given. The declarative semantics of DATALOG/sup V,/spl sim/,c/ is defined in a general way that allows us to put constraints on top of any existing (model-theoretic) semantics for DATALOG/sup V,/spl sim// programs. Knowledge representation issues are then addressed and the complexity of reasoning on DATALOG/sup V,/spl sim/,c/ programs is carefully determined. An in-depth discussion on complexity and expressiveness of DATALOG/sup V,/spl sim/,c/ is finally reported. The discussion contrasts DATALOG/sup V,/spl sim/,c/ to DATALOG/sup V,/spl sim// and highlights the significant increase in knowledge modeling ability carried out by constraints.