Axiom Dependency Hypergraphs for fast Atomic Decomposition of Ontologies

ABSTRACT. In this paper we use directed hypergraphs to represent the locality-based dependencies between the axioms of an OWL ontology. We define a notion of a axiom dependency hypergraph, where axioms are represented as nodes and dependencies between axioms as hyperedges connecting possibly several nodes with one node. We show that a locality-based module of an ontology corresponds to a set of connected nodes in the hypergraph, and atoms of an ontology to strongly connected components. Collapsing the strongly connected components into single nodes yields a condensed axiom dependency hypergraph, which contains the atomic decomposition of the ontology. To condense the axiom dependency hypergraph we exploit linear time graph algorithms on its graph fragment. This approach can significantly reduce the time needed to compute the atomic decomposition of an ontology. We provide an experimental evaluation for computing the atomic decomposition of large biomedical ontologies.