Databases Reference
In-Depth Information
In the following, we illustrate the usage of ASP as a tool for knowledge represen-
tation and reasoning by example. In particular, we first deal with a problem motivated
by classical deductive database applications; then we exploit the “Guess&Check” pro-
gramming style to show how a number of well-known harder problems can be encoded
in ASP.
Reachability.
Given a finite directed graph
G
=(
V,A
), we want to compute all pairs of
nodes (
a, b
)
V
such that
b
is reachable from
a
through a nonempty sequence of
arcs in
A
. In different terms, the problem amounts to computing the transitive closure
of the relation
A
.
The input graph is encoded by assuming that
A
is represented by the binary relation
arc
(
X,Y
), where a fact
arc
(
a, b
) means that
G
contains an arc from
a
to
b
, i.e., (
a, b
)
∈
V
×
∈
A
; while, the set of nodes
V
is not explicitly represented, since the nodes appearing in
the transitive closure are implicitly given by these facts.
The following program then defines a relation
reachable
(
X,Y
) containing all facts
reachable
(
a, b
) such that
b
is reachable from
a
through the arcs of the input graph
G
:
r
1
:
reachable
(
X,Y
)
arc
(
X,Y
)
.
r
2
:
reachable
(
X,Y
)
← arc
(
X,U
)
,reachable
(
U,Y
)
.
←
The first rule states that that node
Y
is reachable from node
X
if there is an arc in the
graph from
X
to
Y
, while the second rule represents the transitive closure by stating
that node
Y
is reachable from node
X
if there exists a node
U
such that
U
is directly
reachable from
X
(there is an arc from
X
to
U
)and
Y
is reachable from
U
.
As an example, consider a graph represented by the following facts:
arc
(1
,
2)
.
(2
,
3)
.
(3
,
4)
.
The single answer set of the program reported above together with these three facts
program is
{
reachable
(1
,
2)
,reachable
(2
,
3)
,reachable
(3
,
4)
,reachable
(1
,
3)
,reachable
(2
,
4)
,reachable
(1
,
4)
,arc
(1
,
2)
,arc
(2
,
3)
,arc
(3
,
4)
. The first three reported literals
are justified by the rule
r
1
, while the other literals containing the predicate
reachable
are justified by rule
r
2
.
In the following, we describe the usage of the “Guess&Check” methodology.
}
Hamiltonian Path.
Given a finite directed graph
G
=(
V,A
) and a node
a
V
of this
graph, does there exist a path in
G
starting at
a
and passing through each node in
V
exactly once?
This is a classical NP-complete problem in graph theory. Suppose that the graph
G
is
specified by using facts over predicates
node
(unary) and
arc
(binary), and the starting
node
a
is specified by the predicate
start
(unary). Then, the following program
∈
P
hp
solves the
Hamiltonian Path
problem:
r
1
:
inPath
(
X,Y
)
∨
outPath
(
X,Y
)
←
arc
(
X,Y
)
.
r
2
:
reached
(
X
)
←
start
(
X
)
.
