PDF de programación - DES: un recurso para el aprendizaje de bases de datos deductivas

DES: un recurso para el
DES: un recurso para el

aprendizaje de
aprendizaje de

bases de datos deductivas
bases de datos deductivas

Fernando Sááenz P
Fernando S
. Ingenieríía del Software e Inteligencia Artificial
a del Software e Inteligencia Artificial

enz Péérezrez

DeptDept. Ingenier

[email protected]
[email protected]

Universidad Complutense de Madrid
Universidad Complutense de Madrid

Facultad de Informáática, c/ Profesor Jos
Facultad de Inform
28040 Madrid
28040 Madrid

tica, c/ Profesor Joséé GarcGarcíía a Santesmases

Santesmases, s/n,
, s/n,

JENUI 2007 17/7/2007

1

ÍÍndice de la presentaci
ndice de la presentacióónn

1.1.
Introduccióónn
Introducci
2.2. Caracter
Caracteríísticas
sticas
3.3. Limitaciones
Limitaciones
4.4. Uso del sistema
Uso del sistema
5.5.
Implementacióónn
Implementaci
6.6. Utilidad
Utilidad
7.7. Conclusiones
Conclusiones
8.8. Enlaces
Enlaces

JENUI 2007

2

1.1. Introducci

Introduccióónn

Bases de datos:
Bases de datos:
de las relacionales a las deductivas
de las relacionales a las deductivas
Lenguajes de bases de datos:
Lenguajes de bases de datos:
de SQL a Datalog
Datalog
de SQL a

JENUI 2007

3

1.1. Introducci

Introduccióón: n: Datalog
Datalog

Prolog) ) –– Relaci
Prolog) ) –– Consulta (

Relacióón (n (Datalog
Datalog))
Datalog))
Consulta (Datalog

Lenguaje de consulta de bases de datos
Lenguaje de consulta de bases de datos
deductivas derivado de Prolog
Prolog
deductivas derivado de
Predicado (Prolog
Predicado (
Objetivo (Prolog
Objetivo (
Significado de un predicado: conjunto de hechos
Significado de un predicado: conjunto de hechos
deducidos:
deducidos:
Intensionalmente
Extensionalmente

Intensionalmente (reglas o cl
(reglas o clááusulas)
usulas)
(hechos)
Extensionalmente (hechos)

JENUI 2007

4

Introduccióón: n:

1.1. Introducci
Datalog
Datalog



tom

grace

jack

amy

tony

carolI

fred

carolII

father(tom,amy).).
father(tom,amy
father(jack,fred).).
father(jack,fred
father(tony,carolII).).
father(tony,carolII
father(fred,carolIII).).
father(fred,carolIII
mother(graceI,amy).).
mother(graceI,amy
mother(amy,fred).).
mother(amy,fred
mother(carolI,carolII).).
mother(carolI,carolII
mother(carolII,carolIII).).
mother(carolII,carolIII
parent(X,Y) :) :-- father(X,Y
parent(X,Y
parent(X,Y) :) :-- mother(X,Y
parent(X,Y
ancestor(X,Y) :) :--
ancestor(X,Y
parent(X,Y).).
parent(X,Y
ancestor(X,Y) :) :--
ancestor(X,Y
parent(X,Z), ),
parent(X,Z
ancestor(Z,Y).).
ancestor(Z,Y

father(X,Y).).
mother(X,Y).).

carolIII

father
father
amyamy
tomtom
jack Fred
Fred
jack
tony carolII
carolII
tony
fred carolIII
carolIII
fred
ancestor(tom,X) =
) =
ancestor(tom,X
{{
ancestor(tom,amy),),
ancestor(tom,amy
ancestor(tom,carolIII),),
ancestor(tom,carolIII
ancestor(tom,fred))
ancestor(tom,fred

}}

ancestor
ancestor

tomtom amyamy
tomtom carolIII
carolIII
tomtom fred
fred

5

JENUI 2007

1.1. Introducci

Introduccióón: sistemas
n: sistemas

Sistemas de bases de datos deductivas:
Sistemas de bases de datos deductivas:
LDL++, XSB, SDS, Declare, ConceptBase
LDL++, XSB, SDS, Declare,
por quéé??
Un nuevo sistema, ¿¿por qu

Un nuevo sistema,

ConceptBase, , ……

JENUI 2007

6

2.2. Caracter

Caracteríísticas de DES
sticas de DES

Uso simple
Uso simple
Instalacióón inmediata
n inmediata
Instalaci
MMíínimos requisitos
nimos requisitos
Multiplataforma
Multiplataforma
Vistas transitorias
Vistas transitorias
Recursióónn no lineal (vs. SQL)
no lineal (vs. SQL)
Recursi
Negacióón estratificada
n estratificada
Negaci
BD en memoria
BD en memoria
Eficiencia (tablas de extensióón)n)
Eficiencia (tablas de extensi

JENUI 2007

7

3.3. Limitaciones de DES
Limitaciones de DES

Agregados (SUM, AVG, ……))

Agregados (SUM, AVG,
AritmAritmééticatica
TTéérminos compuestos (OO)
rminos compuestos (OO)
NonNon--disjunctive
disjunctive
Depuraci
IDE

Depuracióónn
IDE …… ¿¿limitaci

limitacióón?n?

JENUI 2007

8

4.4. Uso del sistema
Uso del sistema

JENUI 2007

9

Consulta

Tabla de extensión

JENUI 2007

10

Vistas transitorias

Consultas

Tabla de extensión

JENUI 2007

11

Depuracióón declarativa
n declarativa
Depuraci

Motivaci

n: dificultad en la depuracióón de
n de

Motivacióón: dificultad en la depuraci
programas
programas
procedimental vs. Declarativa
vs. Declarativa
Depuracióón n procedimental
Depuraci
Program Debugging
([Shaphiro82], Algorithmic
Debugging))
([Shaphiro82],
Orientada al significado, no al procedimiento de
Orientada al significado, no al procedimiento de
ccóómputomputo

Algorithmic Program

JENUI 2007

12

Depuracióón declarativa: ejemplo
n declarativa: ejemplo
Depuraci

between(X,Z):- br(X),br(Y),br(Z),X<Y,Y<Z .

Pairs of non-consecutive elements in the sequence
next(X,Y) :- br(X), br(Y), X<Y, not(between(X,Y)).
next(nil,X) :- br(X), not(has_preceding(X)).

Consecutive elements in a sequence (starting at nil)

has_preceding(X) :- br(X), br(Y), X > Y.

Elements having preceding values in the sequence

even(nil).
even(X) :- odd(Z), next(Z,X).
odd(Y) :- even(Z), next(Z,Y).
br_is_even :- even(X), not(next(X,Y)).
br(a).
br(b).

Base relation (sequence of elements)

Elements in an even position+nil

Elements in an odd position

Succeeds if the cardinality is even

JENUI 2007

13

Depuracióón declarativa: ejemplo
n declarativa: ejemplo
Depuraci

between(X,Z):- br(X),br(Y),br(Z),X<Y,Y<Z .

Pairs of non-consecutive elements in the sequence
next(X,Y) :- br(X), br(Y), X<Y, not(between(X,Y)).
next(nil,X) :- br(X), not(has_preceding(X)).

Consecutive elements in a sequence (starting at nil)

has_preceding(X) :- br(X), br(Y), X < Y.

Elements having preceding values in the sequence

even(nil).
even(X) :- odd(Z), next(Z,X).
odd(Y) :- even(Z), next(Z,Y).
br_is_even :- even(X), not(next(X,Y)).
br(a).
br(b).

Base relation (sequence of elements)

Elements in an even position+nil

Elements in an odd position

Succeeds if the cardinality is even

JENUI 2007

14

Depuracióón declarativa:
n declarativa:
Depuraci
sesióón prn prááctica
ctica
sesi

DES> /debug br_is_even
Debugger started ...
Is br(b) = {br(b)} valid(v)/non-valid(n) [v]? v
Is has_preceding(b) = {} valid(v)/non-valid(n) [v]? n
Is br(X) = {br(b),br(a)} valid(v)/non-valid(n) [v]? v
! Error in relation: has_preceding/1
! Witness query: has_preceding(b) = { }

JENUI 2007

15

Depuracióón declarativa
n declarativa
Depuraci

br_is_even = { }

even(X) = {even(nil)}

odd(X) = {odd(b)}

next(nil, Y) = {next(nil,b)}

br(nil) = { }

next(b, X) = { }

br(Y) = {br(a), br(b)}

br(b) = {br(b)}

has_preceding(a)= {has_preceding(a)}

br(a)= {br(a)}

has_preceding(b)= {}

Non-valid

Unknown

JENUI 2007

16

Instalacióónn
Instalaci

n GPL en Sourceforge
Sourceforge::

Distribucióón GPL en
Distribuci
Fuentes
Fuentes
Ejecutables (Windows, Linux, Solaris)
Ejecutables (Windows, Linux, Solaris)
Instalacióón e inicio
n e inicio
IntIntéérprete
Prolog ((CiaoCiao, GNU,
rprete Prolog
Ejecutable Sicstus
Sicstus
Ejecutable

Instalaci

, GNU, Sicstus

Sicstus, SWI)
, SWI)

JENUI 2007

17

5.5. Implementaci

Implementacióónn

NNúúcleo de DES:

cleo de DES: Prolog
Prolog

lculo de punto fijo con tablas de extensióónn
Saturacióón por estratos en presencia de negaci

CCáálculo de punto fijo con tablas de extensi
Saturaci
Depurador: Prolog
R. Caballero, Y. Garc

n por estratos en presencia de negacióónn
Prolog + Java
+ Java

Depurador:

R. Caballero, Y. Garcííaa--Ruiz Ruiz andand F. SF. Sááenzenz--PPéérez.
rez.
A A newnewproposal
In 16th International
In 16th
((Constraint
Constraint) ) Logic
ACIDE: Java
ACIDE: Java
Proyecto de Sistemas Inform

proposalforfordebugging
International Workshop
Logic Programming

debuggingdatalogdatalogprograms
programs..
Workshop onon Functional
Programming (WFLP?07),

Proyecto de Sistemas Informááticos 2006/2007
ticos 2006/2007

Functional andand
(WFLP?07), June
June. .

JENUI 2007

18

6.6. Utilidad del sistema
Utilidad del sistema

6.000 descargas desde su lanzamiento en 2004

JENUI 2007

19

6.6. Utilidad del sistema
Utilidad del sistema

. (California, Búúfalo,
EE.UU. (California, B
Canadáá (Ottawa)
(Ottawa)
Europa (Alemania, Francia, Béélgica,

Producto de interéés indicado por SIGMOD de la ACM
s indicado por SIGMOD de la ACM
Producto de inter
Universidades:
Universidades:
EE.UU
Canad
Europa (Alemania, Francia, B
Entre los 10 sistemas Prolog
Sourceforge
Sourceforge
““Mirrors
Mirrors””
Usado tambiéén en investigaci
Usado tambi

n en investigacióónn

Entre los 10 sistemas

Prolog mmáás activos de
s activos de

falo, ……))

lgica, ……))

JENUI 2007

20

7.7. Conclusiones y trabajo futuro
Conclusiones y trabajo futuro

Herramienta:
Herramienta:
ÚÚtiltil
Sencilla
Sencilla
Aplicable a la enseññanza de BDD
anza de BDD
Aplicable a la ense
Trabajo futuro:
Trabajo futuro:
AritmAritmééticatica
Agregados
Agregados
Depurador grááficofico
Depurador gr

JENUI 2007

21

8.8. Enlaces
Enlaces

Sistema DES:
Sistema DES:
http