On the scalability of description logic instance retrieval (Q1040773)

This paper addresses two scalability challenges for description logic systems: one requires to deal with large sets of data descriptions (data size), the other with increased expressivity (when for instance negation or disjunction is added to the underlying language). The authors provide a brief overview of the semantics of the description logic \(\mathcal{SHIQ}\) and of the inference services, before describing some of the general, well-known optimization techniques, namely, individual pseudo model merging, definition of individual concept, GCI absorption, and lazy unfolding. A good part of the paper is then dedicated to the more specialized optimization techniques for instance retrieval, including known ones and new ones. These techniques are logically sound but usually logically incomplete, and include, amongst others, transformation of Aboxes, linear instance retrieval, use of precompletion information, binary instance retrieval, and dynamic index-based instance retrieval. The last category of optimization techniques deals with grounded conjunctive queries. The second part of the paper is dedicated to evaluating the performance on run time of the optimization techniques for the inference services of Abox realization of knowledge base specific queries, implemented in the \textsl{RacerPro} (version 1.9.1) description logic system. The authors use ten knowledge bases with large Aboxes developed by the semantic web community, and three knowledge bases with very large Aboxes. The experiments demonstrate that the optimization techniques are effective, but that keeping the balance between creating data structures for faster query answering and relying on memory-conserving algorithms remains a challenge.