Overview
Description Logic Programs (DLP), introduced by Grosof, Horrocks, Volz and Decker, describes the expressive intersection of description logics and rule-oriented Horn logic programming. The associated Description Horn Logic (DHL) is a fragment of first-order logic. The goal is a bidirectional exchange of ontological and rule-based knowledge, not a claim that all OWL axioms are executable as ordinary Datalog rules.
Horn Formulas and Rules
A universally quantified Horn rule has at most one positive head atom:
\forall\bar x\,(A_1\land\cdots\land A_n\to B),
where A_i and B are atomic formulas (and B may be absent for a constraint). In database-oriented Datalog, rules are normally function-free and safe: every head variable also appears in a positive body atom. The least Herbrand-model / least-fixpoint reading characterises the positive Datalog fragment; DLP's DL-oriented model-theoretic setting uses open-world semantics.
Translating DL Inclusions into Horn Rules
Simple correspondences include:
A\sqsubseteq B\quad\leadsto\quad A(x)\to B(x),
A\sqcap B\sqsubseteq C\quad\leadsto\quad A(x)\land B(x)\to C(x),
A\sqsubseteq\forall r.B\quad\leadsto\quad A(x)\land r(x,y)\to B(y),
\exists r.A\sqsubseteq B\quad\leadsto\quad r(x,y)\land A(y)\to B(x).
These translations preserve the intended first-order implications. In contrast, A\sqsubseteq\exists r.B yields
\forall x\,(A(x)\to\exists y\,(r(x,y)\land B(y))),
which cannot in general be expressed as an ordinary function-free universal Horn/Datalog rule without introducing additional witness machinery, a different rule class, or restricting the axiom.
Example
An ontology may assert \mathit{Employee}\sqsubseteq\mathit{Person}, while a rule records
\mathit{Employee}(x)\land\mathit{reportsTo}(x,y) \to\mathit{HasManager}(x).
The ontology supplies class membership information usable by rules, and the rule derives a new predicate. The interpretation of negation, closed-world assumptions, equality and unique names must be fixed for any hybrid implementation; combining engines does not automatically preserve the semantics of arbitrary rule features.
Complexity and Implementations
DLP is designed for more rule-oriented inference than arbitrary expressive DLs, but there is no single complexity bound for everything described as DLP: it depends on the exact sublanguage, grounding and query problem. Fixed-program function-free Datalog evaluation has polynomial-time data complexity, while combined complexity can be EXPTIME-complete. These facts alone do not establish the same bound for unrestricted DL/rule combinations.
The Horn perspective is related to OWL 2 RL and Horn fragments of SROIQ, but the notions are not identical. OWL 2 RL is a specifically standardised, rule-friendly profile, whereas original DLP is an expressivity-intersection analysis.
Relationships
FOL is the common first-order semantics. ALC and SROIQ provide DL context; 3DL introduces nonmonotonic normative rankings rather than plain positive Horn rules.
References
- Benjamin N. Grosof, Ian Horrocks, Raphael Volz, and Stefan Decker (2003). Description Logic Programs: Combining Logic Programs with Description Logic. WWW 2003, 48–57. DOI.
- M. Krötzsch, S. Rudolph, and P. Hitzler (2013). Complexities of Horn Description Logics. ACM TOCL. DOI.
- W3C (2012). OWL 2 Web Ontology Language Profiles (Second Edition). Recommendation.