TL;DR
This paper introduces a novel "closed-world semantics" for querying ontologies, specifically addressing the challenge of inferring the absence of information, which is crucial for applications like clinical trial screening. By defining a new minimal canonical model and a rewriting strategy, they enable efficient querying of negated conditions over complex ontologies, achieving polynomial time complexity in data size.
What Problem Does This Paper Address?
Ontology-mediated query answering (OMQA) is a powerful technique for enriching data with background knowledge. However, most existing OMQA systems operate under an "open-world" assumption, meaning if something isn't explicitly stated, it's considered possible. This is problematic when we need to query for the absence of something, such as identifying patients without a specific diagnosis for clinical trials. Current approaches struggle with this, often conflating closed-world and closed-domain assumptions, and failing to handle "anonymous objects" (objects whose identity isn't explicitly named but is implied by the ontology). This paper tackles the challenge of efficiently answering queries that include negated conditions over ontologies, particularly in the biomedical domain where such negative constraints are common.
Methods
The core contribution is a new "closed-world semantics" for conjunctive queries with negation (NCQs) over ELH₁ ontologies. Instead of relying on traditional open-world semantics, they propose:
- Minimal Canonical Model: They construct a special, minimal canonical model of the knowledge base. This model is designed to be as concise as possible, encoding all inferences while carefully managing the introduction of anonymous objects. This is crucial because the precise number and type of anonymous objects can impact the interpretation of negated atoms.
- Rewriting Strategy: Since the minimal canonical model can be infinite, they develop a rewriting technique. This strategy allows them to translate NCQs into equivalent first-order queries that can be evaluated over a finite part of the model (specifically, the part derived directly from the input data, denoted as I_A). This makes the querying process amenable to standard database techniques.
Datasets
The paper uses an example based on:
- MIMIC-III database: A publicly available critical care database, used to extract ABoxes (assertions about individuals) representing patient diagnoses.
- SNOMED CT: A large medical ontology, used as the TBox (background knowledge and definitions).
- ClinicalTrials.gov: Used to illustrate the type of exclusion criteria (negated conditions) relevant for clinical trial recruitment.
No new benchmarks were introduced; rather, existing resources were used to demonstrate the proposed semantics.
Key Insights and Ideas
- The Necessity of Closed-World for Negation: The paper highlights that the open-world assumption, while useful for positive information, fundamentally hinders queries about the absence of facts. A closed-world perspective is essential for these types of queries.
- Careful Handling of Anonymous Objects: The authors emphasize that the way anonymous objects are introduced and managed in the model is critical for correctly interpreting negated atoms. Their minimal canonical model aims to introduce only the necessary anonymous objects, avoiding redundancy.
- Bridging Ontologies and Databases for Negation: The proposed rewriting strategy effectively bridges the gap between complex ontological reasoning and practical database querying, enabling efficient evaluation of negated queries using standard tools.
- Polynomial Time Complexity: A significant result is that checking a tuple as a closed-world answer to an NCQ can be done in polynomial time with respect to the data size (data complexity). This is a crucial step towards practical implementation.
Key Results
The paper demonstrates their approach with an example involving patient diagnoses and clinical trial eligibility criteria. They show that their semantics correctly identifies patients who should be included or excluded based on negated conditions, which standard open-world semantics would fail to do. The primary result is the theoretical framework and the complexity result: checking a tuple as a closed-world answer to an NCQ is achievable in polynomial time in data complexity.
Limitations and Future Work
- Infinite Canonical Model: While the minimal canonical model is a theoretical construct, it can be infinite in general. The paper addresses this with a rewriting strategy, but the practical implications for very large or complex ontologies are an ongoing area of research.
- Implementation and Scalability: The authors mention that they are working on an implementation to deal with large ontologies like SNOMED CT.
- Temporal and Numeric Information: Future work includes extending the approach to handle temporal and numeric information (e.g., duration of illnesses, dosage of medications), which are vital for more sophisticated clinical trial eligibility criteria.
Summary updated