PDF de programación - Tesis: Fernando Zacarias - BASES DE DATOS DEDUCTIVAS CON EXTENSION A CONJUNTOS FINITOS

;J;I

1'5:_1t
rc5tr;CJ98

UITI!t Dt I•YESTIU Citl Y ll

U TUIICI S •nNZA its li l

I. P. N .
•
L IO T il OA
'"'l';fl'fff" IA HfCT" IC-

I .

CIN VESTAV

I P N

ADO 'JISI CION
DE
l . ..., ' S
CENTRO DE INVESTIGACI6N Y DE ESTUDIOHÑZXDUs.

1.

DEL INSTITUTO POLITECNICO NACIONAL

DEPARTAMENTO DE INGENIERiA ELECTRICA

SECCI6N DE COMPUTACI6N

BASES DE DATOS DEDUCTIVAS CON EXTENSION A

CONJUNTOS FINITOS

TESIS QUE PARA OBTENER EL GRADO DE:

MAESTRO EN CIENCIAS
EN LA ESPECIALIDAD DE
INGENIERIA ELECTRICA

PRESENT A:

LIC. FERNANDO ZACARIAS FLORES

DIRECTOR DE TESIS: DR. SERGIO V. CHAPA VERGARA

UlfTII II IIYESTIIACIII Y ll

ISTlJIIIS AVUZAUS IH

I. P. N.

B I . LI O T I[OA
INr,fNIERIA ElfCTIIUCI

MARZ0/98

C!-At11P"'-'-~!-~---­
.AD81o111S-.l~l.:_l;j 7.,. "tL._
P"aoHAo., :2,-\ )1. • I C!'l ~
_ __ ,}..f.-.ll.~.:: .. l5S.L

J.__

- -

RESUMEN

En el presente trabajo de tesis presentamos una propuesta que mejora Ia manera
en que lenguajes como PROLOG manejan las Bases de Datos Deductivas y,
concretamente el manejo de nuevas estructuras como lo son los conjuntos. Para
esto, seleccionamos solo aquellas partes de nuestro inten!s del lenguaje SuRE
[JOM95], [OJ96], esto por considerar a SuRE como un lenguaje robusto del cual
partir. El hecho de elegir conjuntos como nuestro tema de interes, se debe a que
este tipo de estructuras de datos permiten que el usuario pueda manipular de
manera clara, transparente y sencilla muchos de los problemas que con estas
estructuras se resuelven de manera directa. Ademas, otro punto relevante tratado
en nuestro trabajo es, que se incorpora el uso de matching para aquellos casos en
los que es suficiente con este algoritmo y no se requiere de Ia unificacion. Esto es
importante mencionar debido a que el algoritmo de unificacion es mas complejo,
aunque no se deja de utilizar para los casos en que si se necesita

El trabajo medular de Ia presente se desarrollo a !raves de ejemplos, con Ia
finalidad de hacer mas clara Ia ejemplificacion de nuestros conceptos e ideas. En
nuestra investigacion tambien se proponen algunas variantes de como atacar los
problemas de Ia semantica de los lenguajes orientados a el manejo de las Bases de
Datos Deductivas, ya que esta es Ia base para poder mejorar en mucho Ia
manipulacion que de estas se hace. Tambien, mejoramos Ia forma en que el
usuario plantea su solucion del problema y, no solo eso, sino que ademas
mejoramos el procesantiento de ejecucion, debido a como resolvemos los
diferentes problemas. Proponemos una extension muy natural que consiste en
generalizar aseveraciones de subconjuntos a aseveraciones parciales y trabajar en
dontinios reticuJados mas generales. Estas ayudan a dar claridad y hacer
forrnulaciones concisas a los problemas, involucrando operaciones de agregacion
y recursion en las consuJtas a Bases de Datos Deductivas.

Palabras Clave: Bases de Datos Deductivas, Programacion

logica, LDL,

CORAL, SuRE, conjuntos, agregacion, matching, unificaci6n, dontinios

reticulados.

CIIITRI I! r•ns TIIA CIU Y ll

IS TUIItS AVU ZAtU DH

I. P . N .

• I . L I O T IItOA
I"J r, ENIE"IA ELECTRic-

Dedicatoria especial

A Ia memoria de mi madre

Filiberta Flores Rojas de Zacarias

Por los afios de felicidad que me diste y por el

cariiio que siempre recibi de ti, TE QUIERO!.

INDICE GENERAL

INTRODUCCION

1. INTRODUCCION A LAS BASES DE DATOS DEDUCTIVAS

1.1 Historia de las bases de datos deductivas

1.1.1 Prototipos y Sistemas

1.2 Caracteristicas de las bases de datos deductivas

. . . . . . . . . . . . . . . . . . . . .

1.2 .1 Bases de datos deductivas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2 <',Que es un hecho?

1.2.3 Sintaxis de las reglas

1.2.4 Recursion

1.2.5 Negacion

1.2.6 Estratificacion (semantica por niveles)

. . . .. . .. .. ... ... .. . .. . ...

1.2.7 Set grouping

. . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . .. .. . ... ... .. . .. . . .. .

1.3 Prolog como lenguaje de consulta de BDD

1.3.1 Caracteristicas extra logicas de Prolog

2. ;.POR QUE ES NECESARIA LA EXTENSION?

2.1 Extension a chiusulas de Hom

2.1.1 Justificacion de interes en Ia extension

2.1.2 Datalog

2.2 Casos de interes

8

9

11

15

15

16

17

17

19

22

24

27

27

31

31

33

34

37

2.3 Conjuntos finitos

2.3.1 Set grouping y el mecanismo Collect-all

2 .3.2 Set grouping via Negaci6n como falla

3. CARACTERISTICAS DEL LENGUAJE AMPLIADO

3 .I Caracteristicas principales en las que se centra esta propuesta

3.2 Programaci6n subconjunto-ecuacional

3.3 Programaci6n subconjunto-relacional

3.4 Matching de Conjuntos (Set matching)

3.5 Programas estratificados Subconjunto-ecuacional

..

3.6 Programas Subconjunto-relacional

3.6.1 Setof

3.6 .2 Set-terms en relaciones

3. 7 lntegraci6n de Subconjuntos, Relaciones y Ecuaciones

3.8 Cerradura Transitiva

3 .9 Programas de Orden Parcial

4. MODELADO DEL LENGUAJE

4.1 Clases de chiusulas dellenguaje modelado

4.2 Definicion de Ia Gramatica Libre de Contexto

4.3 Algoritmo Flattening

CONCLUSIONES

BIBLIOGRAFIA Y REFERENCIAS

39

39

41

42

42

43

44

44
47

50

51

51

53

54

55

58

59

64

69

76

78

Introducci6n

I

INTRODUCCION

Hoy dia, las necesidades de contar con lenguajes mas expresivos y poderosos como

herramientas para el prograrnador, ha motivado el desarrollo de diversos lenguajes. El

objetivo principal es, proporcionar una mayor facilidad en el modelado y desarrollo de

algoritmos de forma eficiente y rapida para el programador. Si a esto agregamos Ia

necesidad de manejar grandes volumenes de datos y un alto grado de interactividad sistema

usuario el problema se complica.

Actualmente, las Bases de Datos Deductivas (BDD) han tenido un fuerte desarrollo

debido a las nuevas tendencias con respecto al disei'io e implantaci6n de estas, las cuales

descansan en el modelo 16gico que muestra ventajas sobre el modelo relacional de datos.

Dentro de las BDD que han surgido destacan: CORAL, LOGRES, LDL, DECLARE,

ECRC, COL, etc. [RU93].

Como se mencion6 anteriormente las BDD se han seguido estudiando en los ultimos
ai'ios, principalmente con el uso del lenguaje de La 16gica como Ia herrarnienta del modelado
de datos. Es esta Ia raz6n que ha dado fuerza a los sistemas de bases de datos como

CORAL, LDLI , etc. En el presente trabajo se presentan las investigaciones y anali.sis

realizados referentes a las BDD. Las nuevas aportaciones de Ia logica aqui expuestas

proporcionan a los sistemas de BDD un mejor manejo de los datos asi como tambien

incrementan su eficiencia y expresividad en el disei\o de prograrnas. El uso de Ia logica es

mostrado utilizando ejemplos que nos permiten analizar las diferentes altemativas de

soluci6n a los diversos problemas con que se enfrenta el desarrollo de sistemas de BDD.

Basados en el anali.sis e investigaci6n de los mismos enftentamos el paradigma de "extension

a conjuntos" en las BDD, que representa un avance de surna importancia debido a que al

incluir estos en Ia programaci6n nos perrnite el manejo de funciones estratificadas, dando a

lenguajes como CORAL y LDL un mayor alcance, mejorando el desarrollo de algoritmos

por parte del "usuario" (programador). Para esto se necesita de una semantica declarativa y

una operacional, las cuales nos indicarian si nuestro prograrna es correcto y si se pueden
obtener respuestas satisfactorias.

lntroducci6n

2

Un sistema de BDD que cuenta con el manejo de conjuntos de manera directa, sin

complicaciones de expresividad nos permite explotar de una mejor manera los datos que

conforman nuestras bases de datos, ya que uno de los principales problemas en el manejo de

grandes volumenes de datos es el acceso a estos. Si nuestro sistema de BOO cuenta con Ia

extension a conjuntos, esto facilita y reduce el tiempo de acceso a los datos de manera

significativa. Permitiendonos incluso, el pensar en un procesarniento paralelo de nuestras

aplicaciones, lo que extiende el poder y alcance de cualquier lenguaje. Este es un punto

relevante surgido de nuestras investigaciones. Nuestra investigacion y analisis parte del

estudio de los sistemas existentes a Ia fecha, resaltando y proponiendo soluciones a los

diversos problemas que se encuentran inmersos en algunos de los sistemas analizados. Todo

esto, sin descuidar que nuestras propuestas nos hagan perder expresividad y funcionalidad

en Ia resolucion de los problemas.

Entre los sistemas relacionados con este trabajo tenemos :

LOL [TZ86), CORAL [RPDS88], SuRE [095) y Col [KdMS90). Cada uno de ellos

muestran ventajas y desventajas de lo que proponemos hacer, en base a una breve discusion

de cada uno de los sistemas, llegamos a Ia justificacion del uso de SuRE (este nombre se

debe a los conceptos que en else introducen, Subconjuntos, Relaciones y Ecuaciones) como

Ia mejor alternativa a nuestro objetivo de implantar un lenguaje ampliado. En LDLI se tiene

Ia proposicion "collect-all" que se expresa via "set-grouping". LDLJ Ia incorpora mediante

el modelo dominante de acuerdo al concepto de limite de Ia nocion de rninirnizacion, el cual

aunque interesa