An expressive and tractable rule-based description language
Linh Anh Nguyen, Ngoc Thanh Nguyên · Enterprise Information Systems · 2019
Horn-DL 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-SROIQ. 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 Horn-DL with PDL-like role constructors to obtain the rule language Horn-DL2. We modify the algorithm given by Nguyen, Nguyen, and Szałas (2015) to obtain another one that checks satisfiability of a knowledge base in Horn-DL2 instead of Horn-DL. The resulting algorithm also has a PTime data complexity and Horn-DL2 is therefore tractable.