Vervollständigung von beschreibungslogischen Wissensbasen mit Hilfe von Methoden der Formalen Begriffsanalyse auf partiellen Kontexten

• Applicant: Professor Dr.-Ing. Franz Baader
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 55006481

• Final Report Year: 2011

Final Report Abstract

In diesem Projekt wurde die Qualitätsdimension der Vollständigkeit für beschreibungslogische Wissensbasen näher untersucht. Es wurden dazu formal wohlfundierte Methoden entwickelt, die den Ontologieingenieure dabei unterstützen festzustellen, ob die Ontologie alle relevante Information über den Anwendungsbereich enthält oder nicht, und die Ontologie zu erweitern, wenn dies nicht der Fall ist. Dazu wurden Methoden der Formalen Begriffsanalyse geeignet angepasst und erweitert. Auf praktischer Seite ist ein wesentlicher Beitrag des Projektes das Vervollständigungswerkzeug OntoComP, welches als Plugin für den Ontologieeditor Protégé zur Verfügung gestellt und (inklusive Source Code) offen zugänglich gemacht wurde. Bei der Verbesserung der Benutzerschnittstelle von OntoComP war insbesondere die verbesserte Fehlerbehandlung wichtig, welche auf Beschreibungslogikseite durch die Verwendung von Axiom Pinpointing und auf Seite der Formalen Begriffsanalyse durch Verwendung von Hintergrundwissen ermöglicht wurde. Die Effizienz des Systems konnte auf Beschreibungslogikseite durch den Einsatz inkrementeller Schlussfolgerungsverfahren deutlich verbessert werden. Für die ausdrucksschwache Beschreibungslogik EL wurden derartige Verfahren im Rahmen des Projektes entwickelt während für ausdrucksstarke Beschreibungslogiken die in den Systemen FaCT++ und Pellet implementierten inkrementellen Verfahren zum Einsatz kamen. Auf der begriffsanalytischen Seite ist ein wesentlicher Flaschena hals die Aufzählung aller Pseudoinhalte eines Kontexts. Hier konnte im Rahmen des Projektes zum ersten Mal nachgewiesen werden, dass eine Aufzählung der Pseudoinhalte in der üblichen lektischen Ordnung nicht mit polynomieller Verzögerung möglich ist, d.h. dass dieser Flaschenhals im Allgemeinen nicht vermeidbar ist. Der von uns ursprünglich eingeführte Begriff der Vollständigkeit betrachtet nur Subsumtionsbeziehungen zwischen Konjunktionen von Konzeptnamen, welche in der gegebenen Ontologie auftreten. Dieser Begriff wurde in dem Projekt auch auf Subsumtionsbeziehungen zwischen beliebigen EL-Konzeptbeschreibungen über einem endlichen Vokabular ausgeweitet. Wir konnten zeigen, dass es für die Menge aller in einem endlichen Modell geltenden derartigen Subsumtionsbeziehungen stets ein endliches, effektiv berechnenbares Erzeugendensystem gibt. Darauf aufbauend konnte das Vervollständigungsverfahren auf diesen allgemeineren Begriff der Vollständigkeit erweitert werden. Methodisch beruht dieser Ansatz wieder auf der Erweiterung von Methoden der Formalen Begriffsanalyse.

Publications

• Module Extraction and Incremental Classification: A Pragmatic Approach for EL+ Ontologies. In: Sean Bechhofer, Manfred Hauswirth, Joerg Hoffmann, and Manolis Koubarakis, editors, Proceedings of the 5th European Semantic Web Conference (ESWC’08), volume 5021 of Lecture Notes in Computer Science, pages 230– 244. Springer-Verlag, 2008
  Boontawee Suntisrivaraporn
  
• Exploring Finite Models in the Description Logic ELgfp. In: Sébastien Ferré and Sebastian Rudolph, editors, Proceedings of the 7th International Conference on Formal Concept Analysis, (ICFCA 2009), volume 5548 of Lecture Notes in Computer Science, pages 146–161. Springer-Verlag, 2009
  Franz Baader and Felix Distel
  
• OntoComP: A Protege Plugin for Completing OWL Ontologies. In: Proceedings of the 6th European Semantic Web Conference, (ESWC 2009), volume 5554 of Lecture Notes in Computer Science, pages 898–902. Springer Verlag, 2009
  Bariş Sertkaya
  
• Usability Issues in Description Logic Knowledge Base Completion. In: Sébastien Ferré and Sebastian Rudolph, editors, Proceedings of the 7th International Conference on Formal Concept Analysis, (ICFCA 2009), volume 5548 of Lecture Notes in Artificial Intelligence, pages 1–21. Springer Verlag, 2009
  Franz Baader and Bariş Sertkaya
  
• On the Complexity of Axiom Pinpointing in the EL Family of Description Logics. In: Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010). AAAI Press, 2010
  Rafael Peñaloza and Bariş Sertkaya
  
• On the complexity of enumerating pseudo-intents. Discrete Applied Mathematics, 159(6):450–466, 2011
  Felix Distel and Bariş Sertkaya