Answering Queries Using Views over Description Logics Knowledge Bases

Abstract

Answering queries using views amounts to computing the answer to a query having information only on the extension of a set of precomputed queries (views). This problem is relevant in several fields, such as information integration, query optimization, and data warehousing, and has been studied recently in different settings. In this paper we address answering queries using views in a setting where intensional knowledge about the domain is represented using a very expressive Description Logic equipped with n-ary relations, and queries are nonrecursive datalog queries whose predicates are the concepts and relations that appear in the Description Logic knowledge base. We study the problem under different assumptions, namely, closed and open domain, and sound, complete, and exact information on view extensions. We show that under the closed domain assumption, in which the set of all objects in the knowledge base coincides with the set of objects stored in the views, answering queries using views is already intractable. We show also that under the open domain assumption the problem is decidable in double exponential time.