Maurizio Lenzerini, Andrea Schaerf
We study concept languages (also called terminological languages) as means for both defining a knowledge base and expressing queries. In particular, we investigate on 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.