QUERYING DISJUNCTIVE DATABASES THROUGH NONMONOTONIC LOGICS

Query languages for retrieving information from disjunctive databases are an interesting open area of research. In this paper we study the e xpressive power of major nonmonotonic formalisms - such as circumscrip tion, default logic, autoepistemic logic and some logic programming la nguages - used as query languages over disjunctive databases. For this aim, we define the semantics of query expressions formulated in diffe rent nonmonotonic logics. The expressive power of the languages that w e consider has been explored in the context of relational databases. H ere, we extend this study to disjunctive databases; as a result, we ob tain a finer-grained characterization of the expressiveness of those l anguages and interesting fragments thereof. For instance, we show that there exist simple queries that cannot be expressed by any preferenti al semantics (including the minimal model semantics and the various fo rms of circumscription), while they can be expressed in default and au toepistemic logic. Secondly, we show that default logic, autoepistemic logic and some of their fragments express the same class of Boolean q ueries, which turns out to be a strict subclass of the Sigma(2)(p)-rec ognizable Boolean queries. The latter result is proved by means of a n ew technique, based on a counting argument. Then we prove that under t he assumption that the database consists of clauses whose length is bo unded by some constant, default logic and autoepistemic logic express all of the Sigma(2)(p)-recognizable Boolean queries, while preference- based logics cannot. These results hold for brave reasoning; we obtain dual results for cautious reasoning. Our results appear to be interes ting both in the area of database theory and in the area of knowledge representation.