A Graph Theoretical Foundation for Integrating RDF Ontologies

Octavian Udrea, Yu Deng, Edna Ruckhaus, V. S. SubrahmanianAAAI 2005

This research provides a robust graph-theoretic framework for a common challenge in the Semantic Web: merging disparate RDF ontologies without compromising their internal logic. The authors introduce the CROW algorithm (Computing RDF Ontology Witness), which treats ontologies as directed graphs and applies logical constraints to produce a consistent, streamlined merged result.

The Integration Problem

As the Resource Description Framework (RDF) became the standard for the Semantic Web, a proliferation of ontologies describing similar domains emerged. To realize the "Web of Data," these ontologies must be integrated. However, merging is more than simple file concatenation; it requires handling:

  1. Semantic Equivalence: Identifying when terms like "Staff" in one ontology and "Employee" in another refer to the same concept.
  2. Complex Logic (Horn Clauses): Managing conditional relationships, such as "If an entity is a Researcher AND a Student, it is a Graduate Student."
  3. Negative Constraints: Enforcing rules that prevent invalid relationships, such as a "Faculty" member being classified as a "Student."

The CROW Algorithm

The CROW approach integrates ontologies through a four-phase graph transformation process:

  1. Pre-processing: Terms are renamed to prevent namespace collisions between source ontologies.
  2. HOG Construction: The algorithm builds a Horn Ontology Graph (HOG), where nodes represent terms (or sets of terms for conditional rules) and edges represent properties or logical implications.
  3. Graph Transformation:
    • Cycle Reduction: For transitive properties like subClassOf, the algorithm identifies Strongly Connected Components (SCCs). If concepts mutually reference each other as subclasses, they are collapsed into a single equivalent node.
  4. Redundancy Elimination: To maintain a "minimal" result, the algorithm prunes redundant "shortcut" edges (e.g., if A $\to$ B and B $\to$ C exist, the direct edge A $\to$ C is removed).
  5. Negative Constraint Validation: The final graph is checked against forbidden relationships. If a path violates a negative constraint, the ontologies are deemed un-integratable under the current rules.
Initial state of two separate RDF ontologies before integration.

Key Insights: The Integration Witness

A central contribution of this work is the concept of the integration witness. Rather than just a merged file, the witness is a formal mathematical proof that a valid, consistent merge exists. By distinguishing between transitive properties (like subClassOf) and non-transitive ones, CROW can safely simplify the graph structure without losing semantic meaning. The focus on producing a minimal witness ensures the resulting ontology is clean and efficient for subsequent querying.

The integrated 'minimal witness' graph produced by CROW, resolving redundancies and merging equivalent nodes.

Evaluation and Performance

The authors evaluated CROW using both real-world ontologies (from DAML and SchemaWeb) and synthetic datasets ranging from 8,000 to 35,000 terms.

  • Efficiency: On real-world data, merges were completed in 22 to 58 milliseconds.
  • Scalability: Synthetic tests demonstrated that running time grows near-linearly with the number of terms.
  • Complexity: The algorithm's polynomial complexity—$O(t \cdot n \cdot e \cdot (n + e))$—makes it suitable for large-scale Semantic Web applications.

Conclusion and Future Directions

While CROW is a powerful tool for integration, it currently assumes that term mappings (e.g., "Person:1 is equivalent to Person:2") are provided as input. Future work may involve automating this mapping process. Additionally, while the framework handles Horn constraints effectively, more expressive logics (like full OWL-DL) may require even more sophisticated graph transformations beyond SCC detection.

Summary updated

BibTeX
@inproceedings{udrea2005graph,
  author = {Octavian Udrea and Yu Deng and Edna Ruckhaus and V. S. Subrahmanian},
  title = {{A Graph Theoretical Foundation for Integrating RDF Ontologies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2005},
}
Figure