Kostenbasierte Semantik: Datenkomplexität bei Description Logic‑KB neu beleuchtet

In einer wegweisenden Studie wird die Datenkomplexität von Abfragen in inkonsistenten, gewichteten Description‑Logic‑Wissensbasen unter einer neu eingeführten kostenbasierten Semantik untersucht. Dabei wird jeder möglichen Interpretation ein Kostenwert zugeordnet, der sich aus den Gewichten der verletzten Axiome und Assertions ergibt. Abhängig davon, ob man alle optimalen oder nur einige zulässige Interpretationen betrachtet, lassen sich bestimmte und mögliche Abfrageantworten bestimmen.

Der Beitrag erweitert frühere Arbeiten, die sich auf DL‑Sprachen zwischen EL⊥ und ALCO beschränkten, um Logikformen mit inversen Rollen und Rolleninklusionen. Damit deckt er die wichtigsten Dialekte von DL‑Lite ab und liefert deutlich präzisere Untergrenzen sowie die exakte Komplexität für die optimalkostenbasierte Semantik bestimmter Antworten – ein Ergebnis, das zuvor nicht bekannt war.

Das überraschendste Ergebnis zeigt, dass bei DL‑Lite^H_bool-Ontologien und einer festen Kostenbeschränkung bestimmte Antworten zu Instanzabfragen sowie mögliche Antworten zu konjunktiven Abfragen mittels First‑Order‑Rewriting berechnet werden können. Dadurch erreichen sie die niedrigste mögliche Datenkomplexität, nämlich TC₀, und stellen damit einen bedeutenden Fortschritt in der effizienten Abfrageverarbeitung dar.