Introduction
In the real world, data is rarely static or certain. Imagine a smartwatch monitoring a patient's blood pressure: the readings change every second (temporal), and the sensors are often imprecise (probabilistic). While researchers have developed robust methods for Ontology-Based Query Answering (OBQA)—where a computer uses an "ontology" (a set of rules and definitions) to find hidden insights in data—most existing methods focus on either time or probability, but rarely both.
Combining these dimensions is mathematically difficult because the number of "possible worlds" (different ways the data could be true over time) explodes. This paper introduces a formal framework for OBQA that simultaneously handles temporal and probabilistic data, providing a necessary foundation for reasoning over noisy sensor streams in IoT and health monitoring contexts.
Methods: Temporal Probabilistic Queries
The author proposes a new query language, Temporal Probabilistic Queries (TPQ), which bridges Description Logics (DL), Linear Temporal Logic (LTL), and Probabilistic Databases. The framework is built on three pillars:
- Temporal Probabilistic Knowledge Bases (TPKB): Data is represented as a sequence of probabilistic ABoxes, where each fact at a specific time point is assigned a probability of being true.
- Temporal Probabilistic Queries (TPQ): This core contribution extends standard Conjunctive Queries (CQs) with temporal and probabilistic operators, allowing for complex questions like: "Is there a 90% chance the patient had high blood pressure at least twice in the last 10 minutes?"
- Quasi-models: To determine computational complexity, the author uses "quasi-models"—abstractions that represent infinite system states in a finite way.
As a theoretical work, the paper uses a running example of a health monitoring application involving blood pressure sensors and the SNOMED CT medical ontology to demonstrate the language's expressiveness rather than empirical benchmarks.
Complexity Analysis and Key Results
A major contribution of this work is a comprehensive map of the computational complexity involved in answering these queries across different Description Logics. The research reveals several key insights into the "complexity tax" of combining these domains:
- The Role of Rigid Names: A major factor in complexity is the use of "rigid" properties—attributes that remain constant over time, like a patient's ID. The paper shows that allowing rigid relations between objects can quickly make the problem undecidable (impossible for a computer to solve).
- The "Positive" Sweet Spot: The author identifies that if queries are restricted to "positive" TPQs (avoiding negation and "less than" probability bounds) and use the $\mathcal{EL}$ logic common in medical ontologies, the data complexity drops to PP (Probabilistic Polynomial time), making it potentially viable for real-world use.
In the general case, for most standard logics, query answering is EXPSPACE-complete. For more expressive logics like $\mathcal{ALC}$, the complexity is 2-EXPTIME, which matches the complexity of purely temporal queries, suggesting that the probabilistic dimension is "free" in terms of worst-case complexity in these settings.
Limitations and Future Work
The current framework assumes that probabilistic facts are statistically independent. In reality, sensor readings are often correlated (e.g., if blood pressure is high now, it is likely to be high in the next second). Future work will aim to capture these correlations and explore "query rewriting" techniques to translate these complex logic queries into standard SQL for use with existing probabilistic database systems.
Summary updated