=Paper=
{{Paper
|id=Vol-2157/paper2
|storemode=property
|title=A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems
|pdfUrl=https://ceur-ws.org/Vol-2157/paper2.pdf
|volume=Vol-2157
|authors=Alireza Ensan,Eugenia Ternovska,Heng Liu
|dblpUrl=https://dblp.org/rec/conf/cade/EnsanTL18
}}
==A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems==
https://ceur-ws.org/Vol-2157/paper2.pdf
A Model-Theoretic View on Preferences in Declarative
Specifications of Search Problems
Alireza Ensan1 , Eugenia Ternovska2 , and Heng Liu3
1
Simon Fraser University, Canada
aensan@sfu.ca
2
Simon Fraser University, Canada
ter@sfu.ca
3
Simon Fraser University, Canada
liuhengl@sfu.ca
Abstract. Automated decision making often requires solving difficult and pri-
marily NP-hard problems. In many AI applications (e.g., planning, robotics, rec-
ommender systems), users can assist decision making by specifying their prefer-
ences over some domain of interest. To take preferences into account, we take a
model-theoretic approach to both computations and preferences. Computational
problems are characterized as model expansion, that is the logical task of expand-
ing an input structure to satisfy a specification. The uniformity of the model-
theoretic approach allows us to link preferences and computations by introducing
a framework of a prioritized model expansion. The main technical contribution
is an analysis of the impact of preferences on the computational complexity of
model expansion. We also discuss how prioritized model expansion can be re-
lated to other preference-based declarative programming paradigms. Finally, we
study an application of our framework for the case where some information about
preferences is missing.
Keywords: Preference Modeling, Model Expansion, Model Theory, Descriptive
Complexity
1 Introduction
Solving computationally hard problems (e.g., NP-hard) is in the core of many AI tasks.
Due to the significant progress in performance of modern solvers, finding solutions of
such problems (e.g., planning, travelling salesman, graph colouring, etc.) has become
feasible in many applications. Automated reasoning in intelligent systems often gen-
erates a multitude of acceptable results. For example, in the context of resource man-
agement, consider the prominent problem of Airport Gate Scheduling [14] that, in a
nutshell, is the task of assigning flight arrivals and departures to different gates of an
airport. The problem can be formalized as a Constraint Satisfaction Problem (CSP).
Some variations of the problem are NP-hard and have been encoded as scheduling or
clique partitioning that itself can be transformed to graph colouring problem [4].
Model expansion [27] is the logical task of expanding a mathematical structure (a prob-
lem instance) to a solution structure that satisfies a formula (problem specification). The
2 A. Ensan et al.
formula can be written in any specification language with a model-theoretic semantics.
The authors showed that other declarative frameworks such as satisfiability problem
(SAT), CSP, and answer set programming (ASP) can be encoded as model expansion.
By distinguishing between problem instances and problem specifications, model expan-
sion provides a robust modelling framework and establishes a connection to Descriptive
Complexity [22].
In many industrial applications, a decision maker may be inclined toward a subset of
results. The preferred alternatives can be chosen in automated decision making. For
instance, in the Airport Gate Scheduling problem, there could be some preferences for
scheduling gates. A certain gate may be preferred to be assigned domestic flights rather
than international flights. For language-independent solving, it is crucial to connect
model expansion to a preference framework.
Since preferences play a key role in AI, a large number of frameworks for handling
preferences have been proposed during the last two decades such as [8, 23, 7, 21, 5,
28, 26]. These proposals are often language-dependent because they are added to a host
formal language such as ASP [8, 13] or default logic [12].
In this paper, we propose a model-theoretic approach to handle preferences associated
to a model expansion. The main motivation of our work is to connect model theory,
descriptive complexity, and preference modelling to study computationally hard opti-
mization problems. To the best our knowledge this is the first proposal of this kind in
the literature. We aim to construct a language-independent preference framework that
can be added to any declarative language (e.g., SAT, CSP, and ASP) which can be en-
coded as a model expansion. Toward this goal, we introduce the notion of a prioritized
model expansion that extends model expansion by adding a set of preferences of a de-
cision maker. Preferences can be expressed as priorities over ground atoms and then
generalized to structures.
Using a model-theoretic approach has promising advantages from both modelling and
application viewpoints. For the modelling purposes, properties of model theory [10] can
be used to identify certain syntactic fragments of a logic for answering tractable queries
with preferences. Moreover, given that model expansion underlines all predominant
declarative frameworks such as ASP, SAT, and CSP, prioritized model expansion can
model the main preference-based declarative frameworks such as [8], [33], etc. From a
practical perspective, by viewing preferences as first order structures, we can use model
theory to study properties of preferences and deal with practical cases in declarative
programs such as when some information is missing (similar to null values in database
systems). We do it by introducing the notion of an incomplete preference term that pri-
oritizes some domain elements when some values are unknown. For example, in Airport
Gate Scheduling, a decision maker states that gate number 2 is not the worst option for
domestic flights, while it is not known what the best option is. We address the problem
of finding preferred solutions of search problems in the presence of incomplete prefer-
ences. We argue that this problem can be viewed as query answering over incomplete
databases. It was demonstrated in [20] that, under some conditions, computing certain
answers can equivalently be done using a naive evaluation, that is by evaluating queries
directly on incomplete relational databases, by considering unknown values as domain
elements. The equivalence is due to the preservation theorems [31]. The main advan-
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 3
tage is that naive evaluations drop the computational complexity of computing certain
answers dramatically.
A model-theoretic view on modular systems with preferences was presented in [17].
The authors argued that their proposal can express preference statements in other for-
malisms such as CP-nets [7]. They used Codd’s relational algebra [11] to combine mod-
ules with preferences. The combination was static – the authors did not focus on the
model expansion and its computational complexity.
Our main contributions are as follows. First, we propose the notion of prioritized model
expansion that is a declarative framework for specifying computational problems with
preferences. Second, we discuss that adding preference even in the simplest formulation
leads to the rise of computational complexity of ΣkP -complete (k th level in the polyno-
mial hierarchy) model expansions. Third, we study the relations of some preference-
based frameworks with prioritized model expansion. We apply the computational com-
plexity result of the task to obtain similar results for those frameworks. Fourth, a method
to deal with incomplete information about preferences is proposed. Finally, we show
that preservation theorems can be used for finding preferred solutions of problems with
incomplete preferences.
2 Background
A τ -structure A = (A, R1A , ..., RnA ) is a tuple where τ = {R1 , ..., Rn } is a relational
vocabulary that is a set of non-logical relation symbols Ri with associated arity ki , A is
a domain, and for any Ri ∈ τ , RiA is called the interpretation of Ri and RiA ⊆ Aki . For
a formula ψ in any logic L, vocab(ψ) denotes the set of vocabulary symbols that appear
in ψ. A boolean query Q over τ -structures is defined as a mapping from the set of all
τ -structures to {0,1}. A boolean query Q can be related to a model checking task such
that for a formula ϕ in logic L and vocab(ϕ) = τ , Qϕ (A) = 1 if and only if A |= ϕ
where A is a τ -structure.
Model expansion (MX) is the task of expanding a structure to satisfy a formula in any
logic L [27]. Let us fix a finite relational vocabulary τ and a domain Dom.
Definition 1 (Model Expansion MXIσ ,ψ )
Input: formula ψ in logic L, input vocabulary σ ⊆ vocab(ψ), and a σ-structure I over
domain Dom,
Find a structure A where A |= ψ and expands I. (The decision version: is there a
structure A such that A |= ψ and A expands I?)
We call A an expansion structure of MXIσ ,ψ . Any expansion structure A is a τ -
structure with domain Dom.
For any logic L, the data complexity of (the decision version of) model expansion (MX)
is always in-between model checking (MC) and satisfiability (SAT). For example, for
first-order logic, MC is AC0 , MX is NP-complete, SAT is undecidable. The combined
complexity of model expansion for first-order logic is NEXPTIME. A complexity anal-
ysis of the three tasks (MC, MX, SAT) for several logics of interest was performed in
[24]. Note that, when the input vocabulary is empty, MX is often called model genera-
tion, and if the input vocabulary is equal to the vocabulary of formula ψ, it is equivalent
to model checking.
4 A. Ensan et al.
A variety of problems in AI such as the Airport Gate Scheduling problem can be re-
duced to graph colouring that is a widely discussed NP-hard problem. Graph colouring
can be characterized as a first-order model expansion ( i.e, the problem specification is
in first-order logic) as follows.
Example 1 Let binary relation E denotes edges relation between vertices and unary
relation symbols R, G, and B denote red, green, and blue colours respectively. The
formula ψ specifies three-graph colouring
ψ = ∀x [(R(x) ∨ B(x) ∨ G(x))
∧¬((R(x) ∧ B(x)) ∨ (R(x) ∧ G(x)) ∨ (B(x) ∧ G(x)))]
∧ ∀x∀y [E(x, y) ⊃ (¬(R(x) ∧ R(y))
∧¬(B(x) ∧ B(y)) ∧ ¬(G(x) ∧ G(y)))].
A graph G = (V, E) is an instance structure with vocabulary σ = {E} and domain
V that is the set of vertices. The model expansion MXGE ,ψ finds expansion structure A
(i.e., three-colouring of G) that interprets symbols R, B, and G satisfying ψ. Note that
R, B, and G are implicitly second-order-∃ quantified.
G
z }| {
(V ; E G , RA , B A , GA ) |= ψ.
| {z }
A
In order to study the computational aspect of prioritized model expansion, we employ
the notion of a Turing machine as the model of computation.
Definition 2 Oracle ML is a Turing machine M augmented by an oracle tape that can
decide whether some input string x in the oracle tape belongs to a language L.
Let X be a complexity class.
Notation 1 P X is the class of languages (complexity class) that can be computed by a
deterministic Turing machine with an oracle in X.
Notation 2 co-X is the complexity class of decision problems whose complements are
in X.
The polynomial hierarchy (PH) that is a hierarchy of complexity classes is defined as
ΣkP ∆P ΣkP
P = Σ0P = Π0P = ∆P P
0 , Σk+1 = NP , ∆P
k+1 = P
k , and Π P
k+1 = coNP for
k > 0.
3 Prioritized Model Expansion
In this section, we introduce the notion of prioritized model expansion which is model
expansion with a collection of preferences of a decision maker. To model preferences,
we define preference expression as an order over a set of ground atoms. We study the
computational complexity of solving problems related to prioritized model expansions
including Dominant Structure (i.e., given two structures, whether one is preferred to
another), Optimal Expansion (i.e., given a structure, if it is an optimal expansion of a
model expansion task), and Goal-Oriented Optimal Expansion (i.e., deciding if there
is an optimal expansion satisfying a certain goal). At the end of this section, we define
preference term as a generalization of preference expressions.
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 5
3.1 Preference Expression
Let us fix a domain Dom. Consider k first order variables x1 , ..., xk over Dom, vocab-
ulary τ , and k-ary R ∈ τ . A k-ary tuple a = (a1 , ..., ak ) is an assignment to an ordered
set of variables x = (x1 , ..., xk ) such that for 1 ≤ i ≤ k, ai ∈ Dom. We use the symbol
a[xi ] to denote value ai . R(a) is called a ground atom where a ∈ Domk . A preference
expression P is an order on a set of ground atoms.
Definition 3 (Preference Expression) A preference expression P is a pair P = (Sτ , wP
) where Sτ is the set of all ground atoms of vocabulary τ over domain Dom and wP is
a preorder on Sτ .
For ground atoms R(a) and T (b) where R, T ∈ τ , k-ary tuple a ∈ Domk , and k 0 -ary
0
tuple b ∈ Domk , R(a) wP T (b) is read as R(a) is preferred to T (b). Also, R(a)
is called strictly preferred to T (b) with notation R(a) AP T (b) if R(a) wP T (b) is
true and T (b) wP R(a) does not hold. Also, R(a) ≈P T (b) if R(a) wP T (b) and
T (b) wP R(a).
Example 2 Consider a graph G = (V, E) and three colours R, B, and G as in Exam-
ple 1. Suppose P = (Sτ , wP ) where domain V = {v1 , v2 , ...vn } is a finite set of nodes,
τ = {E, R, G, B}, and R(v1 ) ≈P R(v2 ) AP R(v3 ) states that it is equally preferred
to have v1 and v2 with red colour and either of which is strictly preferred to v3 with red
colour. Also, G(v2 ) A B(v3 ) denotes that having v2 with green colour is favoured to
blue v3 .
The relation between ground atoms can be lifted to a preference order among structures.
The idea of comparing two sets based on the preference on their members has been
widely discussed in different domains such as in database systems [35] and even beyond
the realm of theoretical computer science such as in economic studies and decision
theories [9]. Inspired by [35, 1], here, we introduce three different methods to construct
a relation ≥P from wP among τ -structures with domain Dom as follows.
Definition 4 (Preference Relation on Structures)
Given a preference expression P = (Sτ , wP ), let A and B be two τ -structures with
domain Dom,
– Weak Pareto (WP). A ≥wp P B iff for all R, S ∈ τ and for all a ∈ R
A
and all
B
b ∈ S , R(a) wP S(b).
B
– Upper Bound Dominance (UBD). A ≥ubd P B iff for all S ∈ τ and for all b ∈ S ,
A
for some R ∈ τ , there is a such that a ∈ R and R(a) wP S(b).
B
– Element Dominance (ED) A ≥ed P B iff for some R, S ∈ τ , there is b ∈ S and
A
there is a ∈ R such that R(a) wP S(b) and there is not c for some T ∈ τ such
that c ∈ T B and T (c) AP R(a).
To build a one-to-one correspondence between our preference model and other pref-
erence frameworks in the literature, e.g., [35], [34], [8], etc, we use one of preference
semantics Weak Pareto, Upper Bound Dominance, or Element Dominance. Defining
these different semantics contributes to the flexibility and generality of our proposal in
6 A. Ensan et al.
which a variety of optimization problems can be encoded. We discuss this generality in
more details in section 4.
The strict version of ≥yP where y ∈ {wp, ubd, ed} is defined as A >yP B if A ≥yP B
and B ≥yP A does not hold. A is dominant to B based on semantics y where y ∈ {wp,
ubd, ed} when A >yP B. Also, we say A is dominant to B with notation A >P B when
there is y ∈ { wp, ubd, ed} such that A >yP B.
The problem of deciding if A is dominant is called Dominant Structure problem that is
characterized as follows.
Definition 5 (Dominant Structure)
Input: a preference expression P = (Sτ , wP ) and τ -structures A and B with domain
Dom, Question: is A >P B?
Proposition 1 Solving Dominant Structure problem is polynomial in the size of Dom.
Proof. As stated by Definition 4, at most, we compare all tuples in RA and RB for all
R ∈ τ . The total possible number of k-ary tuples is |Dom|k where k is the maximum
arity of predicate symbols in τ . Therefore, O(|Dom|2k ) comparisons are required for
each R ∈ τ . Thus, deciding if A >P B is in m · O(|Dom|2k ) (polynomial in the size
of Dom) where m is the number of elements in τ .
We remark that the vocabulary τ is fixed and our discussion on computational complex-
ity is focused on data complexity.
3.2 Prioritized Model Expansion
A prioritized model expansion (PMX) is the problem of finding the most preferred
expansion structures with respect to preferences.
Definition 6 (Prioritized Model Expansion)
Input: a formula ψ, input vocabulary σ ⊆ vocab(ψ), a σ-structure I, and a preference
expression P = (Sτ , wP ), Find structure A such that A is an expansion structure of
MXIσ ,ψ and there is not an expansion structure B such that B >P A.
Notation 3 The problem of prioritized model expansion is denoted by ΠIσ ,ψ = (MXIσ ,ψ , P )
where MXIσ ,ψ is a model expansion and P = (Sτ , wP ) is a preference expression.
Definition 7 Any solution to a problem of prioritized model expansion ΠIσ ,ψ is called
an optimal expansion of ΠIσ ,ψ .
In the rest of this subsection, we study some decision problems that can be associated to
a prioritized model expansion. The Optimal Expansion problem asks whether a given
structure is an optimal expansion of a prioritized model expansion.
Definition 8 (Optimal Expansion)
Input: a τ -structure A and a prioritized model expansion ΠIσ ,ψ = (MXIσ ,ψ , P ) where
τ = vocab(ψ) and P = (Sτ , wP ) is a preference expression.
Question: Is A an optimal expansion of ΠIσ ,ψ ?
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 7
Proposition 2 Let model checking of ψ (given a structure A, decide if A |= ψ) in
MXIσ ,ψ be in the complexity class Y . Solving the problem of Optimal Expansion is in
co-NPY .
Proof. The complementary problem is deciding if there is an expansion structure B
such that B >P A. The complementary problem can be solved by a non-deterministic
polynomial Turing machine guessing B with access to an oracle in Y that decides if B is
an expansion of MXIσ ,ψ (that includes checking if B expands I in polynomial time and
if B |= ψ in the complexity Y ) and based on Proposition 1, in polynomial time checks
if B >P A. Thus, the complementary problem is in NPY and the original problem is in
co-NPY .
One of the common tasks in many AI applications is to determine if a certain goal is
achieved by solutions of a problem, e.g., in planning [3]. In the context of prioritized
model expansion, it can be translated into whether there is an optimal expansion that
satisfies a formula. The problem is formulated as follows.
Definition 9 (Goal-Oriented Optimal Expansion)
Input: a prioritized model expansion ΠIσ ,ψ = (MXIσ ,ψ , P ) where τ = vocab(ψ) and
P = (Sτ , wP ) is a preference expression, and a formula φ such that φ is of the form
R1 (a1 ) ∧ ... ∧ Rl (al ) where Ri ∈ τ and Ri (ai ) is a ground atom for 1 ≤ i ≤ l.
Question: Is there an optimal expansion A of ΠIσ ,ψ such that A |= φ?
Proposition 3 Let solving the Optimal Expansion problem of ΠIσ ,ψ = (MXIσ ,ψ , P )
be in the complexity class X. Solving the problem of Goal-Oriented Optimal Expansion
is in NPX .
Proof. First, we non-deterministically guess a τ -structure A and in polynomial time
check if ai ∈ RiA , for 1 ≤ i ≤ l, that can be done by means of a non-deterministic
polynomial Turing machine. Second, we check whether our guess is an optimal expan-
sion that is in the complexity class X by the assumption. Thus, the problem can be
solved by a non-deterministic polynomial Turing machine using an oracle in X. Hence,
the problem is in NPX .
Goal-Oriented Optimal Expansion problem can be generalized to finding an optimal
expansion that satisfies a formula φ in a logic L∗ . In this case, the complexity of model
checking in logic L∗ (i.e., given a structure A if A |= φ?) taken into account. However,
for the sake of simplicity, in this paper, we consider the goal φ as a conjunction of
ground atoms and it can be verified in polynomial time if a structure A satisfies φ.
It was discussed in [27] that any boolean query computable in NP can be expressed as a
first order model expansion MXIσ ,ψ where ψ is a first order formula. Based on Fagin’s
theorem [18], NP is the class of boolean queries expressible in existential second order
logic (∃SO). This shows that a first order MX and existential second order logic have the
same expressive power. Similarly, the polynomial hierarchy is the set of boolean queries
expressible in second order logic and any query computable in ΣkP can be encoded as
MXIσ ,ψ where ψ is a formula of the form Q1 , ..., Qk−1 ψ ∗ such that for 1 ≤ i ≤ k,
Qi is a second order quantifier where Qi = ∀ for k is odd and Q = ∃ otherwise, and
8 A. Ensan et al.
ψ ∗ is a first order formula. Therefore, when a decision version of a model expansion
MXIσ ,ψ is in ΣkP , model checking of ψ is in Πk−1
P
and based on Proposition 2, solving
P
Optimal Expansion (MXIσ ,ψ , P ) is in Σk . The following result shows the impact of
introducing preferences on Goal-Oriented Optimal Expansion for ΣkP -complete model
expansions.
Theorem 1 Let the decision version of a model expansion be ΣkP -complete. The prob-
P
lem of Goal-Oriented Expansion Structure is Σk+1 -complete.
P
Proof. The membership to Σk+1 follows from the results of Proposition 2, Proposi-
tion 3, and properties of model expansion. Since the model expansion is in ΣkP , the
P
complexity of model checking of ψ is in Πk−1 . Therefore, based on proposition 2,
P
the complexity of Optimal Expansion problem is in co-NPΣk−1 that is equal to ΠkP .
P
Also, based on Proposition 3, Goal-Oriented Optimal Expansion problem is in NPΠk
P
or NPΣk that is equal to Σk+1P
. For the proof of hardness, we consider the following
steps.
First, we show that the problem of deciding the existence of minimal solutions of an
abductive logic program [15] satisfying a goal can be reduced to Goal-Oriented Opti-
mal Expansion similar to preferred logic programs [33]. An abductive logic program is
defined as ALP = hH, M, Pi over a set A of propositional atoms where P is a logic
program, H ⊆ A is called the hypothesis and M ⊆ A ∪ {¬a|a ∈ A} is the manifesta-
tion. A solution to ALP is a set N ⊆ H such that there is a stable model S of P ∪ N
and M ⊆ S. A solution N is called (H) minimal if there is not a solution N 0 such that
N 0 ⊂ N . For a given hypothesis h ∈ H, deciding if there is a minimal solution N such
that h ∈ N is Σ2P -complete.
Second, consider an abductive logic program ALP = hH, M, Pi. Let us define a logic
program P 0 as a set of rules of the form r : R(a) ← ¬S(b) for any R(a) wP S(b) such
that S(b) ∈ H. Rule r indicates the less preferred ground atom (i.e., S(b)) belongs to
the set of hypothesis atoms H. Define P ∗ = P ∪ P 0 . The existence of a stable model
of a logic program is NP-complete and it can be translated into the decision version
of a model expansion as it was shown in [27]. The problem of finding if there is a
H minimal solution of ALP can be reduced to deciding whether there is an optimal
expansion in (MXI,ψ , P ) where P ∗ is translated into MXI,ψ based on [27]. Assume
X1 and X2 are two stable models of P ∗ . If X1 is preferred to X2 with respect to one
of preference semantics in Definition 4, there is R(a) ∈ X1 and S(b) ∈ X2 such that
R(a) wP S(b). So, we have X1 ∩ H ⊆ X2 ∩ H and therefore, any preferred answer set
is H minimal. Hence, finding a minimal solution of hH, M, Pi is equivalent to finding
an optimal expansion of ΠIσ ,ψ that satisfies a goal M . Thus, Goal-Oriented Optimal
Expansion for a NP-complete MX is Σ2P -complete.
Third, for model expansions in the higher levels of the polynomial hierarchy, consider
the following. ΣkP -complete problems can be encoded as a combined logic program [6].
Π = (Pg , Pt ) is called a combined logic program where Pg and Pt are logic programs
over a set of propositional variables G and T respectively. M is a model of Π if it is a
stable model of Pg and there is not a stable model N of Pt such that M ∩ G = N ∩ T .
The decision version of this problem is Σ2P -complete. Recursively, the existence of a
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 9
model of a combined program in depth 2 defined as Π2 = (Pg2 , (Pg1 , Pt )) is Σ3P -
complete and similarly, in depth k, the existence of a model of (Pgk−1 , Πk−2 ) is ΣkP -
complete. We introduce abductive combined program as C = hH, M, Πi where Π =
(Pg , Pt ) is a combined logic program. W is a solution of C if there is a model S of
(Pg ∪ W, Pt ) such that M ⊆ S. W is minimal if there is not a solution W 0 such that
W0 ⊂ W.
Lemma 1 The problem of deciding if C = hH, M, Πk i for a given h ∈ H has a
P
minimal solution containing h is Σk+1 -complete.
Proof: The proof includes a translation from a quantified boolean formula (QBF) to C
for k = 2 and then by induction on k for k > 2, the result follows. Let ϕ be a boolean
formula in CNF and X = {x1 , ..., xm }, W = {w1 , ..., wm }, X 0 = {x01 , ..., x0m },
Y = {y1 , ..., yn }, and Z = {z1 , ..., zl } be a set of boolean variables in ϕ. Let t, h, and f
be also boolean variables. Consider Pg as a set of rules of the form {t ← xi , x0i }, {wi ←
xi }, {wi ← x0i }, {t ← y1 , ...yn , h}, and{f ← l1 , ..., lr } where ¬(l1 ∧, ..., ∧lr ) ∈ ϕ
similar to [15]. For X ∪ X 0 ⊆ H, a H-minimal solution of hH, {t} ∪ W, Pg i does
not contain f and it has either xi or x0i . On the other hand, similar to [6], assume Pt
determines the truth value of a set of boolean variables Z. Also, for each clause C ∈ ϕ,
suppose that Pt includes a set of rules of the form t ← ¬C and f ← ¬f, t that means
t must not be in any stable model of Pt . This implies that the validity of ∃X∀Y ∃Zϕ is
equivalent to the existence of a H-minimal solution of C that contains h. So, for k = 2,
the existence of a minimal solution to an abductive combined logic program containing
an atom h is Σ3P -complete.
Finally, according to the previous steps and Lemma 1, finding a minimal solution of
an abductive combined logic program in level k can be translated into a Goal-Oriented
Optimal Expansion where the model expansion is ΣkP -complete and hence the result
follows.
Theorem 1 presents an important consequence of adding preferences to a ΣkP -complete
model expansion. For the problem of deciding if there is an expansion that satisfies a
goal φ, adding preferences leads to a jump in the polynomial hierarchy. So, the pref-
erence relation between expansion structures derived from a preference expression can
not be translated into axiomatization ψ in polynomial time unless P=NP or the polyno-
mial hierarchy collapses.
Example 3 Consider the problem of graph colouring that was described as model ex-
pansion in Example 1. Let G = (V, E) be the input graph where V = {v1 , v2 , v3 , v4 , v5 }
and E G = {(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v2 , v4 ), (v4 , v5 ), (v3 , v5 )}. Assume that we pre-
fer red colour for v1 . Also, v4 with red colour is favoured to v5 with red colour and blue
v2 is preferred to green v2 . These preference statements can be encoded by a preference
expression P such that R(v1 ) AP B(v1 ) and R(v1 ) AP G(v1 ). Also, R(v4 ) AP R(v5 )
and B(v2 ) AP G(v2 ). The prioritized model expansion ΠG,ψ = (MXG,ψ , P ) where
MXG,ψ is the characterization of three-colouring for input graph G and P is the pref-
erence expression. The input graph G has 18 possible three-colourings. Among these
solutions, A is an optimal expansion of G (based on Element Dominance semantics)
where RA = {v1 , v4 }, B A = {v2 , v5 }, and GA = {v3 }.
10 A. Ensan et al.
3.3 Preference Term
In this subsection, we extend the notion of a preference expression by introducing pref-
erence term that is an order on the domain of a first order variable. Preference terms
can be related to the concept of preferences in relational database systems. However,
unlike databases [23], where the goal is to find the most preferred records in a table,
here we aim to find preferred expansion structures. A preference relation among tu-
ples (and therefore among ground atoms that is specified as a preference expression)
is derived from a set of preference terms. The usefulness of defining preferences over
domains of variables is to deal with incomplete information about preferences that will
be discussed in details in Section 5. A preference term p is defined as follows.
Definition 10 (Preference Term)
A preference term p is a pair p = (A, ) where A is a set and is a preorder over A.
For a, b ∈ A, a b means that a is preferred to b. Also, a ∼ b if a b and b a.
Moreover, a b (a is strictly preferred to b) when a b and b a does not hold.
Consider first order variables x1 , ..., xk . The symbol dom(x) denotes the domain of x.
Assume we are given k preference terms px1 = (dom(x1 ), 1 ), ..., pxk = (dom(xk ), k
). A preference relation over k-ary tuples a and b is constructed from px1 , ..., pxk as
follows.
Definition 11 (Preference Relation on Tuples)
Given a set of preference terms P = {px1 , ..., pxk } and two k-ary tuples a and b, we
say that a is preferred to b with respect to P, notation a P b, iff for all pi ∈ P,
a[xi ] i b[xi ].
A preference expression P can be constructed from a set of preference terms P such
that for a predicate symbol R, R(a) wP R(b) if and only if a P b. Prioritized model
expansion then is extended to ΠIσ , ψ = (MXIσ ,ψ , P) where ≥P is derived from a set
of preference terms and the semantics of optimal expansion is exactly as before.
4 Prioritized Model Expansion and Declarative Specifications of
Optimization Problems
In this section we study some examples of declarative specification of optimization
problems that can be encoded as a prioritized model expansion and the associated com-
putational complexity can be determined by the result of Theorem 1.
First, consider a prioritized logic program (PLP) [33] as one of the first examples of
logic programming with preferences. A PLP is a pair (P r, Φ) where P r is a standard
logic program with stable model semantics and Φ is a set of preference relations among
atoms of the form of a b that means a is preferred to b. The transitive closure of Φ
is denoted by Φc . The reflexive transitive binary relation w among answer sets of P r is
defined as: X1 w X2 if there exist a ∈ X1 − X2 and b ∈ X2 − X1 where (a b) ∈ Φc
and there is not d ∈ X1 − X2 such that (b d) ∈ Φc . X is called a preferred answer
set if there is not an answer set Y such that Y A X. The following result states that any
PLP can be encoded as a prioritized model expansion and presents the computational
complexity of corresponding prioritized model expansion.
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 11
Theorem 2 A PLP Γ = (P r, Φ) can be expressed by a prioritized model expansion
ΠI,ψ = (MXI,ψ , P ) where I represents P r, ψ characterizes the stable model se-
mantics, and P is a preference expression representing Φc such that A is an optimal
expansion of ΠI,ψ if and only if there is a preferred answer set M in Γ that can be
constructed in polynomial time from A. Deciding the existence of an optimal expan-
sion of ΠI,ψ that satisfies a goal φ and a preferred answer set of PLP satisfying φ are
Σ2P -complete.
Proof. Φ can be viewed as a preference expression in PMX and a program P r as a first
order model expansion. According to [27], there is a correspondence between expan-
sion structures of MXI , ψ and stable models of P r such that any stable model of P r
can be one-to-one mapped in polynomial time to an answer set of P r and vice versa.
Optimal expansions of ΠI,ψ are computed based on Element Dominance semantics
that is the same as the notion of preferred answer sets in PLP. Also, since the compu-
tational complexity of brave reasoning (i.e., the existence of an answer set that satisfies
a conjunction of atoms) is NP-complete, based on Theorem 1, deciding if there is a
preferred answer sets of Γ that satisfies φ is Σ2P -complete.
Second, an ASO program [8] is a pair (Pg , R) where Pg is a generating logic program
and R is a set of rules of the form r : C1 > ... > Ck ← a1 , ..., an , not b1 , ..., not bm .
In each rule, ai and bi are literals. Also, Ci is a combination of atoms integrated through
conjunction, disjunction, default negation (not) and strong negation (¬) that must ap-
pear only before atoms. Ci > Cj ← body means that if body is satisfied, Ci is preferred
to Cj . Given a set of l rules r1 , ..., rl , each answer set M of Pg is associated with a sat-
isfaction vector d(M ) = hd1 (M ), ..., dl (M )i where di (M ) is called satisfaction degree
of M in ri . Satisfaction degree denotes the minimum j of Cj s in ri that are satisfied
by M . Preorder preference relation ≤ is defined over satisfaction degrees of a rule rk
and two answer sets M1 and M2 as dk (M1 ) ≥ dk (M2 ) when q is the minimum i for
all Ci s in M1 and s is the minimum j for all Cj s in M2 and q < s. Let M1 and M2 be
two answer sets of Pg . M1 is preferred to M2 with respect to R (notation M1 M2 )
if for all i ≤ l, di (M1 ) ≥ di (M2 ). The relation between ASO and prioritized model
expansion is formulated as follows.
Theorem 3 Let ASO = (Pg , R) be an ASO program where Pg is disjunctive program
and R is a set of preference rules. There is a prioritized model expansion ΠI,ψ =
(MXI,ψ , P ) where ψ specifies the stable model semantics and I represents Pg such that
each optimal expansion A of ΠI,ψ can be mapped in polynomial time to a preferred
answer set of ASO. The problem of deciding if there is an optimal expansion of ΠI,ψ
that satisfies a goal φ or there is a solution of ASO satisfying φ is Σ3P -complete.
Proof. An ASO program can be translated into a PLP (P r∗ , Φ) where P r∗ is the union
of Pg and a set of rules r1∗ and r2∗ where for each rule r ∈ R of the form C1 > C2 ←
body(r), we have r1∗ : n1 ← C1 , body(r) and r2∗ : n2 ← C2 , body(r) and n2 n1 is
in Φ. Therefore, based on Theorem 3, ASO can be converted into a prioritized model
expansion. Since the existence of a an answer set that satisfies a set of ground atoms
is Σ2P -complete ( i.e., brave reasoning in disjunctive logic programs with stable model
semantics), deciding the existence of a solution of ASO that satisfies a goal formula φ
is Σ3P -complete.
12 A. Ensan et al.
Finally, our proposal can be also connected to a variety of other preference frameworks
such as CP-nets [7] that model conditional preferences. A CP-net can be translated into
an ASO (see [8]) and hence based on Theorem 4 can be encoded as a prioritized model
expansion. Also, in the context of planning, preferences about temporal properties of
plans can be converted into a logic program with preferences [34] and thus to a priori-
tized model expansion (based on the result of Theorem 3).
5 Incomplete Preferences
In this section, we focus on handling incomplete preference statements associated to
search problems that are common in many practical cases. For example, assume that
for buying a car, the customer believes that the red colour is not the best option and it
is not the last choice either. In this example, some information is not known, that is to
determine what colour is better or worse than red. Dealing with missing information
is a broad field of study in database systems and declarative programming frameworks
[19, 29]. The information incompleteness might be caused by updating databases [16],
exchanging information [25], incomplete knowledge of the user about entire domain of
interest, etc. The notion of an incomplete preference term is defined as follows.
Definition 12 (Incomplete Preference Term)
An incomplete preference term pinc inc
x is a pair px = (dom(x) ∪ ⊥, ) where is a
preorder on dom(x) ∪ ⊥ and ⊥= {⊥1 , ..., ⊥m } is a set of nulls.
An element ⊥j ∈⊥ represents a missing (or unknown) domain element in pinc x and e i
⊥j means that value e assigned to xi is preferred to something that is unknown or e is
not the worst option to choose for xi . Likewise, ⊥j i e means that e is not the best
value of xi .
We define valuation v(pincx ) as a function v : dom(x) ∪ ⊥→ dom(x) that assigns
elements in dom(x) to members of ⊥ appearing in pinc x such that v(e) = e for any
e ∈ dom(x) and v(⊥i ) ∈ dom(x) for any ⊥i ∈⊥.
A preference term px = (dom(x), ) can be viewed as a first order structure with
vocabulary and domain dom(x). An incomplete preference term corresponds to the
well known notion of incomplete databases in which some fields value are null [29]. The
completion of an incomplete preference term under closed world semantics is the set of
all possible preference terms that are constructed by assignment of domain elements to
nulls.
Definition 13 The completion of an incomplete preference term pinc x under closed world
inc
semantics, notation
inc Jpx K , is defined as a set of preference terms as follows:
Jpinc
x K = v(px )|v is a valuation .
Example 4 Assume vocabulary {car} with variables model, colour, and fuel that spec-
ifies properties of a car. A car dealership has a set of cars that is equivalent to an inter-
pretation of car. Let {Ford, Toyota, Honda} be the domain of model and {red, black,
white, gray} be the domain of colour. Also, fuel can be gas, diesel, or electric. A set
of preference terms are defined as follows. pm = (dom(m), m ) where m denotes
the model and Honda m Toyota m Ford, and pc = (dom(c), c ) is an incomplete
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 13
preference term over possible colours of a car where ⊥1 c red that means that red is
not the best colour. Also, pf = (dom(f ), f ) where gas f diesel and gas f electric
indicating the favorite cars are those using gas instead of electric power or diesel. For a
valuation v where v(⊥1 )=black, a black Honda with gas fuel is favoured to an electric
red Ford.
Model expansion task can be coupled with incomplete preference terms as follows.
Definition 14 Incomplete prioritized model expansion is denoted by a pair ΠIincσ ,ψ =
(MXIσ ,ψ , Pinc ) where MXIσ ,ψ is a model expansion and Pinc = {pinc inc
x1 , ..., pxk } is a set
of incomplete preference terms.
The completion of an incomplete prioritized model expansion is defined as follows.
Definition 15 The completion of ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) under closed world seman-
tics (denoted by JΠIincσ ,ψ K) is a set of prioritized model expansions defined as JΠIincσ ,ψ K =
(MXIσ ,ψ , JPinc K) where JPinc K = {Jpinc inc
x1 K, ..., Jpxk K}.
Structure A is called an optimal expansion of ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) if A is an
optimal expansion of all Π 0 ∈ JΠIincσ ,ψ K. Determining if a given structure is an optimal
expansion of an incomplete prioritized model expansion is defined as follows.
Definition 16 ( Optimal Expansion of Incomplete PMX) Input: a τ -structure A with
domain Dom and an incomplete prioritized model expansion ΠIincσ ,ψ = (MXIσ ,ψ , Pinc )
where τ = vocab(ψ) and Pinc = {pinc inc
x1 , ..., pxk } is a set of incomplete preference terms,
inc
Question: Is A an optimal expansion of ΠIσ ,ψ ?
Recall that one of the advantages of using model-theoretic semantics is to utilize model
theory [10]. Here we employ some results of model theory including preservation theo-
rems to study the computational complexity of Optimal Expansion of incomplete priori-
tized model expansion. Preservation theorems show the relations between syntactic and
semantic restrictions of first order formulas [30]. Results are not limited to first order
logic and have been extended to first order logic with fixed point [2], Datalog [32], etc.
We aim to show that the problem of dominant structure in the presence of incomplete
preferences can be reduced to naive evaluation of a formula over an incomplete struc-
ture and by using preservation properties of first order sentences and results in [20] to
solve the problem of dominant structure with incomplete preferences in polynomial in
the size of Dom. Before proceeding, we remind the formal definition of homomorphism
and preservation of a formula. Assume A and B are two τ -structures. Let dom(A) and
dom(B) be the domain of A and B. A function h : dom(A) → dom(B) such that for
each R ∈ τ and for all (a1 , ...an ) (ai ∈ dom(A) for 1 ≤ i ≤ n), if (a1 , ...an ) ∈ RA ,
then (h(a1 ), ..., h(an ) ∈ RB ), is called a homomorphism from A to B. Let φ be a first-
order sentence (all variables are bounded by a quantifier). We say that φ is preserved
under homomorphism if for any structure A such that A |= φ, then for all structures B
that there is a homomorphism h from A to B, B |= φ.
Let ⊥= {⊥1 , ..., ⊥n } be a set of constants (nulls) and α be a vocabulary of symbols. An
α-structure C with domain Dom ∪ ⊥ is called an incomplete structure. Each element of
⊥ is a null value that represents a missing domain value. Given a first order sentence φ
14 A. Ensan et al.
and a structure C, the model checking task (query evaluation) is to decide whether C |=
φ. Naive model checking, according to [29], treats null values as domain elements. It
was discussed in [20] that evaluating queries directly on incomplete relational databases
is equivalent to standard evaluation of queries if some syntactic restrictions are imposed
to the query language.
Theorem 4 Let model checking of ψ in MXIσ ,ψ be in the complexity class C. Solving
the problem of Optimal Expansion of Incomplete prioritized model expansion is in co-
NPC .
Proof. In order to prove Theorem 4, it suffices to show that for two τ -structures A
and B with domain Dom, A ≥Pinc B can be decided in polynomial time in the size
of Dom and the rest is only to follow the steps taken in the proof of Proposition 2.
To this end, we take the following steps. First, we construct an incomplete structure
called preference structure as follows. Let pinc x1 = (dom(x1 ) ∪ ⊥, 1 ) be an incom-
plete preference term. We construct the following incomplete α-structure C with do-
main Dom0 = Dom ∪ ⊥ as follows. Consider vocabulary α = {p1 , SA , SB } and
pC1 = {(a1 , a2 )|a1 , a2 ∈ Dom0 and a1 1 a2 }. Also, SA = RA . Define SB1 = RB and
SB2 = {a|∃b ∈ SB1 ; a[x2 , ..., xn ] = b[x2 , ..., xn ]∧a[x1 ] ∈⊥}. Let define SB = SB1 ∪SB2 .
Predicate p1 represents incomplete preferences among values of variable x1 , SA is the
set of all tuples in RA , and S B is the set of all tuples in RB plus all tuples in B whose
value of x1 is replaced by a null.
Second, by slightly abuse of notation, valuation v(C) means valuation of any null value
in C similar to the valuation of a preference term. Valuation v is a strong onto homo-
morphism ( v is a surjective function) from C to C 0 where dom(C) = Dom ∪ ⊥ and
dom(C 0 ) = Dom. The symbol JCK denotes the set of all C 0 where there is a valuation v
(strong onto homomorphism) such that v(C) = C 0 . Any C 0 ∈ JCK is called a completion
of C under closed world semantics.
Third, according to Definition 4, Definition 10, and Definition 11, the task of deciding if
B is preferred to A can be reduced to evaluation of whether C |= ∀x1 ∀x(SA (x1 , x)) →
∃y1 y(SB )(y1 , y) ∧ p1 (y1 , x1 )) where x = (x2 , ...xn ) and y = (y2 , ..., yn ). It was
discussed in [20] that a positive first order formula ϕ (with no negation) with a guard
of the form of ∀x(R(x) → ϕ), where R is a relation, is preserved under strong onto
homomorphism. φ is a positive formula with a guard and completion of C under closed
world semantics is equivalent to a set of structures to which there is a strong onto
homomorphism from C. Thus, instead of evaluating all completions of C, we can naively
evaluate φ. Since naive evaluation is in polynomial time in the size of Dom, evaluation
of φ over all completions of C is polynomial in the size of Dom. Hence, deciding if
B ≥pinc
x1
A is polynomial in the size of Dom.
For a set of incomplete preference terms Pinc = {pinc inc
x1 , ..., pxk }, by induction on the
number of incomplete preference terms, deciding B ≥Pinc A is polynomial in the size
of Dom. The immediate result similar to Proposition 1 is that for a model expansion
MXI,ψ with model checking of ψ in the complexity C, deciding if a given structure is
a preferred expansion based on a set of incomplete preference terms is in co-NPC . The
following result immediately follows from Theorem 4.
Corollary 1 Let solving the decision version of model expansion MXIσ ,ψ be Σkp -complete.
Solving the problem of Goal-Oriented Optimal Expansion with incomplete prioritized
p
model expansion is Σk+1 -complete.
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 15
6 Conclusion
We proposed a novel language-independent preference framework and connected it
to model expansion for characterizing preference-based computational decision and
search problems. We demonstrated that adding preferences raises the computational
complexity of deciding the existence of an expansion structure satisfying a goal. Addi-
tionally, we introduced a new method to model incomplete preferences and used model
theory results, namely preservation theorems, to find preferred expansions more effi-
ciently. In future work, we will devise an algorithm that solves prioritized model ex-
pansion using generic solvers empowered by propagators. The solver would provide
symbolic explanations for rejecting and accepting models, and would follow a preferred
computation path to prune the search space.
References
[1] Amgoud, L., Vesic, S.: Repairing preference-based argumentation frameworks.
In: IJCAI. pp. 665–670. Citeseer (2009)
[2] Atserias, A., Dawar, A., Kolaitis, P.G.: On preservation under homomorphisms
and unions of conjunctive queries. Journal of the ACM (JACM) 53(2), 208–237
(2006)
[3] Baier, J.A., McIlraith, S.A.: Planning with preferences. AI Magazine 29(4), 25–37
(2008)
[4] Bhasker, J., Samad, T.: The clique-partitioning problem. Computers & Mathemat-
ics with Applications 22(6), 1–11 (1991)
[5] Bienvenu, M., Fritz, C., McIlraith, S.A.: Specifying and computing preferred
plans. Artificial Intelligence 175(7-8), 1308–1345 (2011)
[6] Bogaerts, B., Janhunen, T., Tasharrofi, S.: Stable-unstable semantics: beyond np
with normal logic programs. Theory and Practice of Logic Programming 16(5-6),
570–586 (2016)
[7] Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: A
tool for representing and reasoning with conditional ceteris paribus preference
statements. J. Artif. Intell. Res.(JAIR) 21, 135–191 (2004)
[8] Brewka, G., Niemelä, I., Truszczynski, M.: Answer set optimization. In: IJCAI.
vol. 3, pp. 867–872 (2003)
[9] Censor, Y.: Pareto optimality in multiobjective problems. Applied Mathematics
and Optimization 4(1), 41–59 (1977)
[10] Chang, C.C., Keisler, H.J.: Model theory, vol. 73. Elsevier (1990)
[11] Codd, E.F.: Extending the database relational model to capture more meaning.
ACM Transactions on Database Systems (TODS) 4(4), 397–434 (1979)
[12] Delgrande, J., Schaub, T.: Expressing preferences in default logic. Artificial Intel-
ligence 123(1), 41–87 (2000)
[13] Delgrande, J., Schaub, T., Tompits, H.: Logic programs with compiled prefer-
ences. arXiv preprint cs/0003028 (2000)
[14] Dorndorf, U., Drexl, A., Nikulin, Y., Pesch, E.: Flight gate scheduling: State-of-
the-art and recent developments. Omega 35(3), 326–334 (2007)
[15] Eiter, T., Gottlob, G., Leone, N.: Abduction from logic programs: Semantics and
complexity. Theoretical computer science 189(1-2), 129–177 (1997)
16 A. Ensan et al.
[16] Elmasri, R., Navathe, S.: Fundamentals of database systems. Pearson (2015)
[17] Ensan, A., Ternovska, E.: Modular systems with preferences. In: IJCAI. pp. 2940–
2947 (2015)
[18] Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets
(1974)
[19] Gelfond, M.: Logic programming and reasoning with incomplete information. An-
nals of mathematics and artificial intelligence 12(1), 89–116 (1994)
[20] Gheerbrant, A., Libkin, L., Sirangelo, C.: Naive evaluation of queries over in-
complete databases. ACM Transactions on Database Systems (TODS) 39(4), 31
(2014)
[21] Gonzales, C., Perny, P., Dubus, J.P.: Decision making with multiple objectives
using gai networks. Artificial Intelligence 175(7-8), 1153–1179 (2011)
[22] Immerman, N.: Descriptive complexity. Graduate texts in computer sci-
ence, Springer (1999). https://doi.org/10.1007/978-1-4612-0539-5, http://
dx.doi.org/10.1007/978-1-4612-0539-5
[23] Kießling, W.: Foundations of preferences in database systems. In: Proceedings of
the 28th international conference on Very Large Data Bases. pp. 311–322. VLDB
Endowment (2002)
[24] Kolokolova, A., Liu, Y., Mitchell, D., Ternovska, E.: On the complexity of model
expansion. In: Proc., 17th Int’l Conf. LPAR. pp. 447–458 (2010)
[25] Libkin, L.: Data exchange and incomplete information. In: Proceedings of
the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of
database systems. pp. 60–69. ACM (2006)
[26] Mindolin, D., Chomicki, J.: Contracting preference relations for database applica-
tions. Artificial Intelligence 175(7-8), 1092–1121 (2011)
[27] Mitchell, D.G., Ternovska, E.: A framework for representing and solving np
search problems. In: AAAI. pp. 430–435 (2005)
[28] Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Incompleteness and incomparabil-
ity in preference aggregation: Complexity results. Artificial Intelligence 175(7-8),
1272–1289 (2011)
[29] Reiter, R.: Towards a logical reconstruction of relational database theory. In: On
conceptual modelling, pp. 191–238. Springer (1984)
[30] Rosen, E., Weinstein, S.: Preservation theorems in finite model theory. In: Logic
and computational complexity. pp. 480–502. Springer (1995)
[31] Rossman, B.: Existential positive types and preservation under homomorphisms.
In: Logic in Computer Science, 2005. LICS 2005. Proceedings. 20th Annual IEEE
Symposium on. pp. 467–476. IEEE (2005)
[32] Rudolph, S., Thomazo, M.: Expressivity of datalog variants–completing the pic-
ture. In: 25th IICAI (2016)
[33] Sakama, C., Inoue, K.: Prioritized logic programming and its application to com-
monsense reasoning. Artificial Intelligence 123(1), 185–222 (2000)
[34] Son, T.C., Pontelli, E.: Planning with preferences using logic programming. In:
Logic Programming and Nonmonotonic Reasoning, pp. 247–260. Springer (2004)
[35] Staworko, S., Chomicki, J., Marcinkowski, J.: Prioritized repairing and consistent
query answering in relational databases. Annals of Mathematics and Artificial In-
telligence 64(2-3), 209–246 (2012)