Querying concept-based knowledge bases

Abstract

Much of the research on terminological reasoning aims at characterizing concept languages (also called terminological languages) with respect to both expressive power and computational complexity of computing subsumption. On the other hand, little attention has been paid to studying concept languages as query languages, i.e. as a means for extracting information from a concept-based knowledge base. In this paper we address this problem by exploring the possibility of using two different concept languages, one for asserting facts about individual objects, and the other for querying a set of such assertions. Contrary to many negative results on the complexity of terminological reasoning, our work shows that, provided that a limited language is used for the assertions, it is possible to employ a richer query language while keeping the reasoning process tractable. We also show that, on the other hand, there are constructs that make query answering inherently intractable.