Introduction
In fields like medicine and biology, ontologies have become gargantuan. Structured frameworks such as SNOMED CT or the National Cancer Institute (NCI) thesaurus contain hundreds of thousands of concepts and complex relationships. For developers building specialized applications—for instance, a tool focused on "Cystic Fibrosis"—reusing these massive knowledge bases is difficult. Current tools often force an all-or-nothing approach: either import the entire multi-gigabyte ontology, which slows reasoning, or manually pick terms and risk losing critical logical dependencies.
The Modularization Problem
The ideal solution is a module: a subset of the ontology that behaves exactly like the whole for a specific set of terms (the "signature"). However, the authors prove that determining if a subset is a perfect minimal module is undecidable for the expressive logic used in the Web Ontology Language (OWL DL). Structural methods, like simple graph traversal, often miss subtle dependencies that can alter the meaning of the data.
Methodology: Syntactic Locality
To bypass the undecidability problem, the authors propose a "sufficient condition" called syntactic locality. Instead of proving logical equivalence, the algorithm examines the structure of axioms to determine relevance.
The Locality Check
An axiom is "local" to a signature if it essentially becomes a tautology when terms outside the signature are ignored. If an axiom is local, it cannot contribute new information to the specific topic of interest and can be safely excluded from the module.
The Extraction Algorithm
The researchers developed an iterative process to build the module:
- Start with the target terms (the signature).
- Scan the ontology for non-local axioms.
- Add these axioms to the module and expand the signature to include any new terms found within them.
- Repeat until no more relevant axioms are found.
This algorithm was implemented in Swoop, a popular ontology editor, allowing users to select a concept and instantly generate its locality-based module.
Experimental Evaluation
The authors evaluated the algorithm on various real-world ontologies, ranging from simple hierarchies (NCI, SNOMED, Gene Ontology) to complex structures with cyclic dependencies (GALEN, NASA’s SWEET).
Key Results
The results demonstrated that locality-based modules are dramatically smaller than those produced by previous state-of-the-art methods like PROMPT-FACTOR:
- SNOMED: For a single concept, the module was, on average, only 0.05% of the original ontology.
- NCI: Modules averaged about 0.08% of the original size.
- Complexity and Cycles: In complex ontologies like GALEN-Full, modules were larger (averaging 3.5%, with some reaching 29.8%) because concepts are more tightly intertwined with logical cycles.
Conclusion
While finding the absolute minimal module remains a theoretical challenge, syntactic locality provides a "reasonably small" module that is mathematically guaranteed to preserve all logical relationships for the chosen terms. This logic-based approach ensures that developers can reuse parts of massive ontologies without sacrificing correctness or performance.
Summary updated