An expressive and tractable rule-based description language

ABSTRACT

$\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}$ is a rule language introduced by Nguyen, Nguyen, and Szałas for the Semantic Web. It has a PTime data complexity and is more expressive than Horn-$\mathrm{S}\mathrm{R}\mathrm{O}\mathrm{I}\mathrm{Q}$. These rule languages, however, do not allow PDL-like role constructors (i.e., union, sequential composition, the reflexive-transitive closure and the test operator). Using the transitive closure of a role $r$ is not the same as using a transitive role that is a superrole of $r$. Furthermore, the test operator together with the other PDL-like role constructors would allow users to express sophisticated concepts. In this paper, we extend $\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}$ with PDL-like role constructors to obtain the rule language $\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}2$. We modify the algorithm given by Nguyen, Nguyen, and Szałas (2015) to obtain another one that checks satisfiability of a knowledge base in $\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}2$ instead of $\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}$. The resulting algorithm also has a PTime data complexity and $\mathrm{H}\mathrm{o}\mathrm{r}\mathrm{n}\text{-}\mathrm{D}\mathrm{L}2$ is therefore tractable.

KEYWORDS:

• Description logics
• rule-based languages
• semantic web

Acknowledgments

We would like to thank the anonymous reviewers for helpful comments and suggestions.

Notes

1. NP, PTime (also written as P) and AC${ }^0$ are complexity classes. See https://en.wikipedia.org/wiki/Complexity_class.

2. The universal role stands for the total binary relation between individuals.

3. If $k=0$, then the right-hand side of each of the rules represents the empty word $\epsilon$.

4. The subscripts $l$ and $r$ stand for ‘left’ and ‘right’, respectively.