Introduction
Temporal logic is a cornerstone of reasoning about dynamic data, yet a persistent trade-off exists between expressivity and computational feasibility. This research identifies a "sweet spot" for interval temporal logic by introducing a Horn fragment of the Halpern-Shoham (HS) logic that is tractable (P-complete). By adopting non-strict semantics—aligning with the SQL:2011 standard—the authors extend this logic to the Description Logic family ($DL-Lite$), creating a framework suitable for efficient ontology-based data access (OBDA) over temporal databases.
The Challenge of Interval Reasoning
The Halpern-Shoham (HS) logic is a powerful framework for reasoning about intervals (e.g., "during a meeting," "after the semester") rather than discrete points in time. However, HS logic is notoriously undecidable, making it difficult to use for reliable automated reasoning. Even previously proposed "Horn fragments" (subsets of the logic that typically simplify computation) remained undecidable over discrete timelines like the integers ($\mathbb{Z}$).
The challenge addressed here is finding a version of interval logic that is expressive enough for real-world applications but simple enough that a computer can solve queries in polynomial time.
Achieving Tractability
The authors achieve tractability through three primary architectural choices:
- Non-Strict Semantics: Traditional HS logic uses "strict" relations (e.g., interval $A$ is "after" $B$ if $A$ starts strictly after $B$ ends). This paper uses non-strict relations (using $\leq$ instead of $<$), which aligns with the SQL:2011 standard. This subtle shift prevents the logic from being able to simulate complex, undecidable machinery like Turing machines.
- The Horn Fragment ($HS_{horn}$): The grammar is restricted to Horn clauses—implications where a conjunction of conditions leads to a single conclusion. Crucially, they allow "box" operators $[R]$ (stating something must hold in all related intervals) but restrict "diamond" operators $\langle R \rangle$ (stating something holds in at least one related interval) to the left side of implications.
- Canonical Models and the "Chase": To check if a set of rules is satisfiable, the authors provide a "chase" procedure. This algorithm builds a minimal (canonical) model of the data by repeatedly applying the rules until a fixed point is reached. Because the number of relevant time intervals is bounded polynomially relative to the input data, the process is guaranteed to finish quickly.
Key Insights and Results
A critical finding is the "Strictness" Penalty: the authors demonstrate that if you switch from non-strict ($\leq$) to strict ($<$) semantics, the logic immediately jumps from P-complete to PSPACE-hard. This identifies the non-strict interpretation as the "secret sauce" for tractability.
Furthermore, the inclusion of a Universal Modality $[G]$ (stating a rule applies to "all intervals") allows for the definition of general domain constraints and "hereditary" properties (e.g., if a condition holds for an hour, it holds for every minute within that hour).
Complexity Results
- Satisfiability: Checking if a formula in $HS_{horn}$ is consistent over the timeline of integers ($\mathbb{Z}$) is P-complete.
- Description Logic Fragments: The authors introduced two tractable fragments of temporalized description logic: $HS-Lite^{H/flat}_{horn}$ and $HS-Lite^{H[G]}_{horn}$.
- Data Complexity: For both fragments, "instance checking" (determining if a specific individual belongs to a concept at a specific time) is P-complete for both combined and data complexity.
Conclusion and Future Work
By integrating $HS_{horn}$ with $DL-Lite$, the authors create a path for Ontology-Based Data Access (OBDA), allowing users to query temporal databases using high-level conceptual terms. While these fragments are not FO-rewritable (meaning they cannot be translated directly into standard SQL), their P-complete nature makes them suitable for engines capable of handling recursive queries like Datalog. Future research will focus on identifying even simpler "core" fragments that might achieve First-Order rewritability for massive datasets.
Summary updated