Preference Queries in Deductive Databases 1 Preference Queries in Deductive Databases

In many applications, it may be natural to express not only mandatory requirements but also preferences on the data to be retrieved. Lacroix and Lavency 10) extended SQL with a notion of preference and showed how the resulting query language could still be translated into the domain relational calculus. We explore the use of preference in databases in the setting of datalog. We introduce the formalism of preference datalog programs (PDPs) as preference logic 2 Surya MANTHA programs without uninterpreted function symbols for this purpose. PDPs extend datalog not only with constructs to specify which predicate is to be optimized and the criterion for optimization but also with constructs to specify which predicate to be relaxed and the criterion to be used for relaxation. We can show that all of the soft requirements in 10) can be directly encoded in PDP. We first develop a naively-pruned bottom-up evaluation procedure that is sound and complete for computing answers to normal and relaxation queries when the PDPs are stratified, we then show how the evaluation scheme can be extended to the case when the programs are not necessarily stratified, and finally we develop an extension of the magic templates method for datalog 14) that constructs an equivalent but more efficient program for bottom-up evaluation. x1 Motivation and Approach The motivation for our work stems from the observation that traditional database query languages allow the user to express only the mandatory requirements on the data to be retrieved from a database. In many applications, it is more natural to express queries in terms of both mandatory, or hard, requirements as well as preferences, or soft requirements. Lacroix and Lavency 10) explore this idea with queries of the for