Databases Reference
In-Depth Information
There are two basic possibilities for representing qualitative preferences. In one ap-
proach, the preference is specified among rules, mirroring the fact that some rules may
be more reliable than others, and striving to use a set of rules that is as preferred as
possible for giving reason to an answer. In the second approach, the preferences are
specified among literals, reflecting information on either the likelihood or the desirabil-
ity of the affirmations represented by the literals.
In the first kind of formalisms, preferences are specified by means of an ordering
among rules. Formally, an
ordered logic program
is a pair (
Π,<
) where
Π
is a logic
program and
<
Π
, the relation
r
1
<r
2
expresses that
r
2
has higher priority than
r
1
. For example, consider the follow-
ing program:
⊆
(
Π
×
Π
) is a strict partial order. Given,
r
1
,r
2
∈
r
1
:
¬
a.
r
2
:b
←¬
a, not c.
r
3
:c
←
not b.
This program has two answer sets, one given by
.
For the first answer set, rules
r
1
and
r
2
are applied; for the second,
r
1
and
r
3
.However,
assume that we have reason to prefer
r
2
to
r
3
, expressed by
r
3
<r
2
. In this case we
would want to obtain just the first answer set. In this case we say that the first is a
preferred answer set
.
In general, defining which answer sets should be the preferred ones in this setting
is not always as obvious as in the example above, and indeed several approaches have
been proposed. A comprehensive comparison of three major semantics, defined by Del-
grande, Schaub, Tompits [78], by Brewka and Eiter [79], and by Wang, Zhou, Lin [80],
has been presented in [81].
In the second representational approach, preferences are represented among atoms,
literals or formulas.
One way of specifying this has been proposed in [82] is the use of
ordered disjunction
in rule heads. In particular, the operator
{¬
a, b
}
and the other given by
{¬
a, c
}
in rule heads acts as a disjunction specifying
also preferences. The meaning of a rule
a
1
×
×
× a
n
← body.
is that if the body is
satisfied then some
a
i
must be in the answer set, most preferably
a
1
, if this is impossible
then
a
2
, and so on. The formal semantics is defined by means of answer sets of split
programs and of rule satisfaction degrees. There are some degrees of freedom when
aggregating the satisfaction degrees of several rules, leading to different semantics, the
main ones being cardinality-based, set-inclusion-based, and Pareto-based.
In the ordered disjunction approach the construction of answer sets is amalgamated
with the expression of preferences.
Optimization programs
[83], on the other hand,
strictly separate these two aspects. An optimization program is a pair (
P
gen
,P
pref
).
Here,
P
gen
is an arbitrary logic program used to generate answer sets. All we require
is that it produces sets of literals as its answer sets.
P
pref
is a preference program.
Preference programs consist of preference rules of the form
c
1
> ... > c
n
←
...
body
,
where the
c
i
are Boolean combinations of literals built from
and not.Asinthe
case of ordered disjunction, the semantics of these programs is based on the degree of
satisfaction of preference rules, and as in the case of ordered disjunctions, there are
several options for aggregating these satisfaction degrees for defining semantics.
∨
,
∧
,
¬
