Beschreibungslogiken mit existentiellen Quantoren und polynominellen Subsumtionsproblem und ihre Anwendung im Bereich biomedizinischer Ontologien

• Antragsteller: Professor Dr.-Ing. Franz Baader
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2006 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 24881586

• Erstellungsjahr: 2012

Zusammenfassung der Projektergebnisse

In dem Projekt sollten Beschreibungslogiken mit existentiellen Quantoren sowohl aus theoretischer als auch aus praktischer Sicht genauer untersucht werden. Dies beinhaltete zum einen die genaue Erforschung der Grenze zwischen Logiken mit polynomiellem und nicht-polynomiellem Subsumtionsproblem. Zum anderen sollten Optimierungsansätze für die polynomiellen Subsumtionsalgorithmen entwickelt und an großen biomedizinischen Ontologien evaluiert werden. Außerdem beabsichtigten wir auch andere Schlußfolgerungsprobleme (wie das Instanz- und das Anfrageproblem) zu untersuchen sowie Beschreibungslogiken mit existentiellen Quantoren zu lokalisieren, die zwar nicht mehr polynomiell sind, aber doch Algorithmen zulassen, die sich besser verhalten als die bekannten Algorithmen für ausdrucksstarke Logiken. Durch die Arbeiten in dem Projekt wurden diese Ziele vollständig erreicht. Aus theoretischer Sicht verfügen wir nun für Beschreibungslogiken mit existentiellen Quantoren über ein umfassendes Bild über die Grenze zwischen Logiken mit polynomiellen und nicht-polynomiellen Inferenzproblemen, auch für den Fall dass nur zyklische oder azyklische TBoxen verwendet werden und für andere Inferenzprobleme als Subsumtion. Aus praktischer Sicht wurden, aufbauend auf unseren Arbeiten, mehrere hocheffiziente Systeme entwickelt, die diese Inferenzprobleme lösen. Insbesondere hat sich dadurch die Laufzeit für die Klassifikation der großen Medizinontologie SNOMED CT von 45 Minuten vor Beginn des Projekts (für das kommerzielle System ONTYLOG) auf wenige Sekunden (für das System CB) verbessert. Der neue Web Ontology Standard des W3C, OWL 2, enthält ein Profile namens OWL 2 EL, für das die zugrundeliegende Beschreibungslogik im Rahmen dieses Projektes entwickelt wurde.

Projektbezogene Publikationen (Auswahl)

• CEL—A Polynomial-time Reasoner for Life Science Ontologies. In: Ulrich Furbach and Natarajan Shankar, editors, Proceedings of the 3rd International Joint Conference on Automated Reasoning (IJ-CAR’06), volume 4130 of Lecture Notes in Artificial Intelligence, pages 287–291. Springer- Verlag, 2006
  Franz Baader, Carsten Lutz, and Boontawee Suntisrivaraporn
  
• Data Complexity in the EL family of Description Logics. In: Nachum Dershowitz and Andrei Voronkov, editors, Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR’07), volume 4790 of Lecture Notes in Artificial Intelligence, pages 333–347. Springer-Verlag, 2007
  Adila Krisnadhi and Carsten Lutz
  
• Replacing SEP-Triplets in SNOMED CT using Tractable Description Logic Operators. In: Jim Hunter Riccardo Bellazzi, Ameen Abu-Hanna, editor, Proceedings of the 11th Conference on Artificial Intelligence in Medicine (AIME’07), volume 4594 of Lecture Notes in Computer Science, pages 287–291. Springer-Verlag, 2007
  Boontawee Suntisrivaraporn, Franz Baader, Stefan Schulz, and Kent Spackman
  
• Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes. In: Malik Ghallab, Constantine D. Spyropoulos, Nikos Fakotakis, and Nikos Avouris, editors, Proceedings of the 18th European Conference on Artificial Intelligence (ECAI’08), pages 25–29. IOS Press, 2008
  Christoph Haase and Carsten Lutz
  
• 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
  
• Conjunctive Query Answering in the Description Logic EL using a Relational Database System. In: Craig Boutilier, editor, Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09), pages 2070–2075. AAAI Press, 2009
  Carsten Lutz, David Toman, and Frank Wolter
  
• SNOMED reaching its adolescence: Ontologists’ and logicians’ health check. International Journal of Medical Informatics, 78(Supplement 1):S86–S94, 2009
  Stefan Schulz, Boontawee Suntisrivaraporn, Franz Baader, and Martin Boeker
  
• Deciding inseparability and conservative extensions in the description logic EL. Journal of Symbolic Computation, 45(2):194–228, 2010
  Carsten Lutz and Frank Wolter
  
• Query and Predicate Emptiness in Description Logics. In: Fangzhen Lin and Ulrike Sattler, editors, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR’10), pages 192–202. AAAI Press, 2010
  Franz Baader, Meghyn Bienvenu, Carsten Lutz, and Frank Wolter