Past and Future of DL-Lite

Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAAAI 2010 · DOI

This research, originally presented at AAAI-10, investigates the "sweet spot" for temporal description logics (TDLs). The goal is to identify the optimal balance between the expressivity required for temporal databases and the computational tractability necessary for practical implementation. By mapping the complexity landscape of various fragments within the DL-Lite family extended with temporal operators, the authors reveal critical thresholds where reasoning shifts from efficient to undecidable.

The Challenge of Temporal Conceptual Modeling

Conceptual data modeling, using frameworks like ER or UML, is the industry standard for database design. However, standard models often struggle to capture how data evolves over time. Real-world applications frequently require constraints such as ensuring a "manager" was previously an "employee" or that a "project" must be completed within a specific duration.

While Description Logics (DLs) provide a formal foundation for reasoning over these models, adding a temporal dimension typically increases computational complexity to EXPTIME or higher. The authors seek to define the most lightweight TDLs capable of capturing essential temporal constraints:

  • Timestamping: Distinguishing between time-invariant classes (e.g., "Person") and temporary ones (e.g., "Student").
  • Evolution: Modeling how objects migrate between classes over time.
  • Temporal Cardinality: Limiting how many times an instance can participate in a relationship over its entire lifespan.
Support for conceptual modeling features across different temporal operators.

Methodology: Extending DL-Lite

The study builds upon the DL-Lite family, specifically $DL-Lite_{bool}$ (supporting full Booleans) and $DL-Lite_{core}$ (the most basic fragment). These are extended with standard operators from Linear Temporal Logic (LTL), including Future/Past ($\Diamond_F, \Diamond_P$), Next/Previous ($\bigcirc_F, \bigcirc_P$), Until/Since ($U, S$), and Always ($\Box^*$).

These operators are applied in two primary ways:

  1. On Concepts: Defining classes based on temporal history (e.g., "A SeniorManager is someone who was a Manager in the past").
  2. On Roles (Temporalised Roles): Constraining relationships over time (e.g., "An employee can work on at most 5 projects throughout their career").

The Complexity Landscape

The authors provide a definitive complexity map for TDLs based on DL-Lite, identifying several surprising results. One of the most significant findings is the "undecidability trap": adding even a simple "next-time" operator ($\bigcirc_F$) to concepts while allowing temporal operators on roles renders the logic undecidable. This stems from the complex interaction between functionality constraints and temporalised roles.

Conversely, the authors discovered that for the $DL-Lite_{core}$ fragment, the logic remains NP-complete even when including next/previous operators. This is a notable departure from standard propositional temporal logic, where the "next" operator usually elevates complexity to PSPACE, making $DL-Lite_{core}$ a highly attractive candidate for practical use.

Complexity results for various temporalized DL-Lite fragments.

Key Results Summary:

  • $T_{US}DL-Lite^N_{bool}$: (Until/Since on concepts) is PSPACE-complete.
  • $T_{FPX}DL-Lite^N_{core}$: (Future/Next on concepts) is NP-complete.
  • $T_U DL-Lite^N_{core}$: (Always/Some time on concepts) is NLOGSPACE-complete.
  • $T^R_X DL-Lite^N_{bool}$: (Next on concepts + Temporalised roles) is Undecidable.
  • $T^R_U DL-Lite^N_{bool}$: (Always on concepts + Temporalised roles) remains NP-complete, suggesting that "undirected" temporal operators on roles are safer than "directed" ones like "Next."

Conclusion and Future Directions

While the complexity bounds for many fragments are promising, a "decidability gap" remains. It is currently unknown if the NP-complete $T_{FPX}DL-Lite^N_{core}$ fragment remains decidable when temporalised roles are added. Furthermore, while the theoretical foundations are now mapped, practical implementation remains a future goal. The authors suggest that because many of these logics reduce to LTL, existing LTL provers could be adapted to facilitate temporal conceptual modeling in real-world database systems.

Summary updated

BibTeX
@inproceedings{artale2010past,
  author = {Alessandro Artale and Roman Kontchakov and Vladislav Ryzhikov and Michael Zakharyaschev},
  title = {{Past and Future of DL-Lite}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7580},
}
Figure