Databases Reference
In-Depth Information
Aggregates are especially useful when real-world problems have to be dealt with.
Consider the following example application:
4
A project team has to be built from a set
of employees according to the following specifications:
1. At least a given number of different skills must be present in the team.
2. The sum of the salaries of the employees working in the team must not exceed the
given budget.
Suppose that our employees are provided by a number of facts of the form
emp
(
EmpId,
Skill, Salary
); the minimum number of different skills and the budget are specified
by the facts
nSkill
(
N
) and
budget
(
B
). We then encode each property stated above by
an aggregate atom, and enforce it by an integrity constraint:
r
1
:
in
(
I
)
∨
out
(
I
)
←
emp
(
I,Sk,Sa
)
.
r
3
:
←
nSkill
(
M
)
,
not #
count
{
Sk
:
emp
(
I,Sk,Sa
)
,in
(
I
)
}
>
=
M.
r
4
:
←
budget
(
B
)
,
not #
sum
{
Sa,I
:
emp
(
I,Sk,Sa
)
,in
(
I
)
}
<
=
B.
Intuitively, the disjunctive rule “guesses” whether an employee is included in the team
or not, while the two constraints correspond one-to-one to the requirements. Indeed, the
function #
count
counts the number of employees in the team, while #
sum
sums the
salaries of the employees which are part of the team.
Note that thanks to the aggregates the translation of the specifications is straightfor-
ward.
Function Symbols and Existential Quantifiers.
Since ASP evolved from Datalog, tra-
ditional ASP languages do not allow for function symbols or existential quantification.
However, often it is convenient to use function symbols for simple reasons like group-
ing arguments together; they are also needed for creating and managing more complex
data structures like lists, as available in standard logic programming languages like Pro-
log. Also in applications concerning ontologies or the Semantic Web, often existential
quantifications in rule heads would be required in order to model unknown entities. Of
course, the two approaches are related, as usually it is possible to eliminate existential
quantifiers by introducing Skolem functions.
A major difficulty is that extensions either by function symbols or existential quan-
tifiers immediately lead to undecidability of the respective computational problems. A
major quest is therefore the identification of significant decidable subclasses of the lan-
guage.
Concerning extensions with (uninterpreted) function symbols, there are essentially
two groups of proposals:
Syntactically restricted fragments
,suchas
ω
-restricted programs
[51],
λ
-restricted
programs
[52],
finite-domain programs
[53],
argument
-
restricted programs
[54],
FDNC
programs
[55],
bidirectional programs
[56], and the proposal of [57]; these approaches
introduce syntactic constraints (which can be easily checked at small computational
4
In the example, we adopted the syntax of the DLV system, the same aggregate functions can
be specified also by exploiting other ASP dialects.
