Research in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic Al formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO There Exists For All, the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit queries-which are useful in practice--that can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning.
Default logic as a query language / Cadoli, Marco; Thomas, Eiter; Georg, Gottlob. - In: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING. - ISSN 1041-4347. - 9:3(1997), pp. 448-463. (Intervento presentato al convegno 4th International Conference on Principles of Knowledge Representation and Reasoning tenutosi a BONN, GERMANY nel MAY 24-27, 1994) [10.1109/69.599933].
Default logic as a query language
CADOLI, Marco;
1997
Abstract
Research in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic Al formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO There Exists For All, the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit queries-which are useful in practice--that can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
