Ontological Reasoning with F-logic Lite and its Extensions

Andrea Calì, Georg Gottlob, Michael Kifer, Thomas Lukasiewicz, Andreas PierisAAAI 2010 · OpenReview

Abstract

This paper introduces the Datalog$^{\pm}$ family of languages, a framework designed to bridge the gap between traditional database constraints and complex ontological reasoning. By identifying tractable fragments such as linear, guarded, and weakly guarded Datalog$^{\pm}$, the authors ensure that query answering remains decidable even when the underlying "chase" procedure is infinite. This work demonstrates that Datalog$^{\pm}$ can effectively subsume and extend popular formalisms like F-Logic Lite and Extended Entity-Relationship (EER) models with high efficiency.

Introduction

In both database management and the Semantic Web, answering queries over data that must satisfy specific rules or constraints is a fundamental challenge. A common tool for this is the chase procedure, which "completes" a database by adding missing information required by the rules. However, for many powerful rule sets, such as tuple-generating dependencies (TGDs), the chase can proceed indefinitely, creating an infinite database and making query answering undecidable.

Previous research focused on restricting rules to ensure chase termination. This paper takes a different approach: it identifies classes of rules where the chase might be infinite, but the resulting structure remains "well-behaved" enough that query answering is still decidable and computationally manageable.

The Datalog$^{\pm}$ Framework

The authors introduce three primary sub-languages within the Datalog$^{\pm}$ family:

  1. Linear Datalog$^{\pm}$: Rules are restricted to a single atom in the body, generalizing standard inclusion dependencies (e.g., "Every manager is an employee").
  2. Guarded Datalog$^{\pm}$: Rules may have multiple atoms in the body, provided there is a "guard" atom containing all variables used in the body. This restricts the complexity of data joins.
  3. Weakly Guarded Datalog$^{\pm}$: A relaxed version where only variables potentially triggering an infinite chase (at "affected positions") require guarding.

Additionally, the framework addresses Key Dependencies (KDs)—uniqueness constraints—through the concepts of separability and non-conflicting rules, allowing these constraints to coexist with TGDs without breaking decidability.

Mapping Existing Formalisms

As a theoretical work, the paper uses existing logical formalisms as primary test cases. It proves that F-Logic Lite (used for object-oriented databases) and Extended Entity-Relationship (EER) models (a standard industrial tool for data modeling) can be mapped into the Datalog$^{\pm}$ family.

An example of an Extended Entity-Relationship (EER) model that can be represented within the Datalog$^{\pm}$ framework.

Key Results and Complexity Analysis

A major contribution of the paper is the comprehensive complexity analysis for Boolean Conjunctive Queries (BCQs). The authors demonstrate that for Linear Datalog$^{\pm}$, queries can be rewritten into standard SQL, achieving $AC_0$ data complexity. This allows complex ontological reasoning to be performed using standard, optimized relational database engines.

Data complexity results for various Datalog$^{\pm}$ fragments, highlighting the efficiency of Linear ($AC_0$) and Guarded (PTIME) variants.
Language Data Complexity Combined Complexity
Linear Datalog$^{\pm}$ $AC_0$ PSPACE-complete
Guarded Datalog$^{\pm}$ PTIME 2EXPTIME-complete
Weakly Guarded EXPTIME 2EXPTIME-complete

The paper specifically proves that query answering in F-Logic Lite is NP-complete, and that EER models can be handled with $AC_0$ efficiency when using non-conflicting criteria.

Conclusion and Future Work

The Datalog$^{\pm}$ family provides a powerful new way to "tame infinity" in ontological reasoning. By ensuring the infinite structures produced by the chase have bounded treewidth, the authors maintain decidability. Future work includes extending these results to handle more general equality-generating dependencies (EGDs), more expressive query languages with negation or recursion, and developing physical implementations to benchmark performance on real-world large-scale data.

Summary updated

BibTeX
@inproceedings{cali2010ontological,
  author = {Andrea Calì and Georg Gottlob and Michael Kifer and Thomas Lukasiewicz and Andreas Pieris},
  title = {{Ontological Reasoning with F-logic Lite and its Extensions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  url = {https://openreview.net/forum?id=5tcyCIoI6B8},
}
Figure