TITLE: ``Querying Disjunctive Databases with Nonmonotonic Logics''

ABSTRACT:

While the problem of retrieving information from relational databases has been extensively studied for many years, the study of query languages for disjunctive databases is relatively less established. I shall talk about recent work -- jointly developed by Thomas Eiter of the Technical University of Vienna and myself -- that characterizes the expressive power of various nonmonotonic logics, used as query languages over disjunctive databases. Our study shows that different families of nonmonotonic formalisms, which are perfectly equivalent as far as relational databases are concerned, are not equivalent at all when disjunctive databases are considered. Thus, we obtain an objective criterion for preferring certain semantics rather than others (including semantics for logic programs).

We also tackle the classical problem of capturing the set of tractable queries in the framework of disjunctive databases. This problem is relevant also to knowledge representation and automated reasoning, for it concerns the class of inferences that can be efficiently computed from any given knowledge-base. Unfortunately, as one could expect, our results in this case are mostly negative. We prove that none of the logics commonly considered in logic programming and AI captures the set of tractable queries, and that the source of difficulty has nothing to do with those that cause similar problems in the relational case.

Everyone is welcome to attend.

Web Accessibility