# Query-Driven Procedures For Hybrid Mknf Knowledge Bases

JOSE J ´ ULIO ALFERES ´
and MATTHIAS KNORR and TERRANCE SWIFT
CENTRIA, FCT, Universidade Nova de Lisboa Hybrid MKNF knowledge bases are one of the most prominent tightly integrated combinations of open-world ontology languages with closed-world (non-monotonic) rule paradigms. The definition of Hybrid MKNF is parametric on the description logic (DL) underlying the ontology language, in the sense that non-monotonic rules can extend any decidable **DL language. Two related semantics** have been defined for Hybrid MKNF: one that is based on the Stable Model Semantics for logic programs and one on the Well-Founded Semantics (WFS). Under **WFS, the definition of Hybrid** MKNF relies on a bottom-up computation that has polynomial data complexity whenever the DL
language is tractable. Here we define a general query-driven **procedure for Hybrid MKNF that is**
sound with respect to the stable model-based semantics, and **sound and complete with respect to** its WFS variant. This procedure is able to answer a slightly restricted form of conjunctive queries, and is based on tabled rule evaluation extended with an external oracle that captures reasoning within the ontology. Such an (abstract) oracle receives as input a query along with knowledge already derived, and replies with a (possibly empty) set of atoms, defined in the rules, whose truth would suffice to prove the initial query. With appropriate assumptions on the complexity of the abstract oracle, the general procedure maintains the data complexity of the WFS for Hybrid MKNF knowledge bases.

To illustrate this approach, we provide a concrete oracle for EL+**, a fragment of the light-weight**
DL EL++. Such an oracle has practical use, as EL++ **is the language underlying OWL 2 EL,**
which is part of the W3C recommendations for the Semantic Web, and is tractable for reasoning tasks such as subsumption. We show that query-driven Hybrid **MKNF preserves polynomial data**
complexity when using the EL+ **oracle and WFS.**
Categories and Subject Descriptors: I.2.4 [**Knowledge Representation Formalisms and**
Methods]: Representation languages; Modal logic; I.2.3 [Deduction and Theorem Proving**]: Logic programming; Nonmonotonic reasoning and believe revision; Inference engines; F.4.1**
[Mathematical Logic**]: Computational logic**
General Terms: Theory, Languages Additional Key Words and Phrases: hybrid knowledge bases, ontologies, rules, tabling, wellfounded semantics, description logics, tractable fragments arXiv:1007.3515v2 [cs.AI] 9 Dec 2011