Banco de Dados Dedutivos Banco de Dados Dedutivos Orientados a Objetos e FLORAOrientados a Objetos e FLORA

Sérgio Queirozsrmq@di.ufpe.br

CIn - UFPERecife, dezembro de 1999

RoteiroRoteiro Bancos de dados orientados a

objetos DOOD: bancos de dados

dedutivos orientado a objetos F-Logic, FLORID e FLORA Exemplo introdutório: O banco

de dados acadêmico em F-Logic

Objetos, nomes de objetos, métodos, átomos-F, moléculas-F e BD extensional

Classes, assinaturas, herança e esquemas de BD

Predicados e átomos-P

Regras, consultas e BD intencional

Negação e restrições de segurança na conclusão das regras

Interação herança-dedução Verificação de tipos e Meta-

programação FLORA x SQL FLORA x DataLog FLORA x LIFE

Problemas enfrentados pela área de Problemas enfrentados pela área de banco de dadosbanco de dados

Aplicações não-tradicionais (“non-business type”)• CAD, GIS, AI• Necessidade de manusear grandes quantidades de

dados• Dados complexos• Evolução do esquema

Mudanças significativas na relação de custo memória/disco

Impedance mismatch entre linguagens de programação e linguagens de consultas em banco de dados

Bancos de Dados Orientados a Objetos Bancos de Dados Orientados a Objetos Combina o paradigma OO com a tecnologia de BD Modelo de dados OO Requisitos obrigatórios para ser considerado OO

(manifesto):• Objetos complexos• Identidade de objetos• Encapsulamento• Tipos ou Classes• Herança• Overriding, Overloading e

Late Binding• Completude computacional• Extensibilidade

Características gerais de BDs

Persistência Gerenciamento de

memória secundária Concorrência Recuperação Consultas Ad-hoc

BD Dedutivo Orientado a ObjetosBD Dedutivo Orientado a ObjetosBDOO:identidade de objetosobjetos complexosclassesencapsulamentoherançaoverriding, overloading

e late bindingextensibilidadelinguagem de consulta

declarativaembasamento teórico

Bancos de Dados Dedutivos

fundamentação lógicalinguagem declarativa

poderosa com mecanismo de dedução

tipos abstratos de dadosidentidade de objetosmodelo de dados flat

BDDOO

Estratégias para construção de um Estratégias para construção de um DOODDOOD

Utilização da linguagem declarativa existenteIntegração da linguagem declarativa existente às novas extensões orientadas a objetos

Tempo de adaptação à linguagemFlexibilidade da integração: bidirecional, unidirecional.Impedance Mismatch

Semântica FormalUma única linguagemReconstrução total do sistema

Frame-logic (F-logic)Frame-logic (F-logic) Tentativas de estender BD dedutivo com

funcionalidades OO ou vice-versa tendem a sacrificar características lógicas ou orientadas a objetos importantes

F-Logic (1995)• Lógica completa para representar os conceitos do

paradigma orientado a objetos Objetos complexos; Identidade de objetos (oid); Herança; Polimorfismo; Encapsulamento; etc.

• Apropriada para definir, consultar e manipular esquemas de bancos de dados

FLORID e FLORAFLORID e FLORAFLORID (U. Freiburg, 1997) implementação de F-logic em

C++ com algumas extensões avaliação bottom-up interface web expressões regulares expressões de caminho nenhuma integração com C++ apenas linguagem de consulta

em memória central nenhum outros serviços em

BD sem encapsulamento

FLORA (SUNY, 1999) implementação de F-logic

sob XSB avaliação top-down expressões de caminho integração (quase) completa

e bi-direcional com XSB mais eficiente que Florid com

compilação via “tabling” apenas linguagem de

consulta em memória central nenhum outros serviços em

BD sem encapsulamento

BD Acadêmico em F-Logic: hierarquia “é BD Acadêmico em F-Logic: hierarquia “é um”um”

young midaged

yuppie

30

4020

degree

ms phd

report

article

cacm jacm

codd70 flogic94

person

student emplchild(person)

john

sally faculty manager

phil

mary bob

child(john)

alice

dept

cs1 cs2

datatype

integerstring

"CS""Mary" "Bob"

empl :: personstudent :: personfaculty :: emplchild(person) :: personjohn : studentjohn : emplcs1 : dept...yuppie :: young20 : young30 : yuppie40 : midaged"CS" : string"Bob" : stringalice : child(john)...

BD Acadêmico em F-logic: fatosBD Acadêmico em F-logic: fatos Bob is 40 and is the manager of the CS department. His assistants are

John and Sally.bob[name -> "Bob";

age -> 40; affiliation -> cs1[dname -> "CS"; mngr -> bob; assistants ->> {john, sally}]]

Mary's highest degree is an MS. She works at the CS department and is friend to Bob and Sally.

mary[name -> "Mary"; highestDegree -> ms; friends ->> {bob, sally}; affiliation -> cs2[dname -> "CS"]]

...

BD Acadêmico em F-logic: BD Acadêmico em F-logic: informações gerais das classesinformações gerais das classes

Every faculty is a midaged person who writes article, makes in the average $50,000 a year and owns a degree of some kind, typically a PhD. A faculty's boss is both a faculty and a manager.faculty[boss => (faculty, manager); age => midaged;

highestDegree => degree; papers =>> article; highestDegree *-> phd; avgSalary -> 50000] Every employee is affiliated to some department, has a boss who is

also an employee and joint work on reports with other employees.empl[affiliation => dept; boss => empl; jointWorks@empl =>> report]

Every person has a name, friends who must be persons and children who also must be persons.person[name => string; friends =>> person; children =>> child(person)] ...

BD Acadêmico em F-logic: BD Acadêmico em F-logic: regras dedutivasregras dedutivas

A boss is an employee who is the manager of another employee of the same department.

E[boss -> M] <- E:empl D:dept E[affiliation -> D[mngr -> M:empl]]

A joint work is a paper that is written by two faculties.X[jointWorks@Y ->> Z] <- Y:faculty X:faculty

Y[papers ->> Z] X[papers ->> Z]

BD Acadêmico em F-logic: BD Acadêmico em F-logic: consultasconsultas

Who are the midaged employees of the CS department and who are their boss?

?- X:empl X[boss -> Y; age -> Z:midaged; affiliation -> D[dname->"CS"]] Who published jointly with Mary in the Journal of the ACM?

?- mary[jointWorks@Y ->> jacm90] Where did Mary published joint work with Phil?

?- mary[jointWorks@phil ->> Z]

Sintaxe de F-logicSintaxe de F-logicAlfabeto de F-logic: Conjunto de Símbolos de

funções (F) Conjunto Símbolos de

predicados (P) Variáveis (V) Distincao entre P, F e V

seguindo mesmas convencoes de que Prolog

Termos ID Termos de 1ª ordem sobre F e

V Nomes de objetos, métodos e

classesOid (Object Identifier): Termos ID sem variáveis

Fórmulas atômicas átomos de 1ª ordem

• ex, p(X1,...,Xn) O : C

• O instância de C C :: D

• C subclasse de D Hierarquia de classe e objetos

não precisa ser um reticulado

Sintaxe de F-logic: metodos e Sintaxe de F-logic: metodos e assinaturasassinaturas

Fórmulas atômicas (cont.) O[M->R0]

• Método escalar M(O) = R0

O[M->>{R1, ..., Rn}]• Método multivalorado M

O[M@(Arg1, ..., ArgN) -> R0]• Método parametrizado

C[M=>T]• Assinatura. • M aplicado a objetos da classe C deve retornar

objeto de classe T C[M=>>T]

• Assinatura do método M, multivalorado.

F-átomos e F-moléculasF-átomos e F-moléculas F-átomos

• Representam exatamente uma propriedade de um objeto, tal como uma relação de classe ou definição de método

isaac:man. isaac[father->abraham]. isaac[son->>{jacob}]. isaac[son->>{esau}].

F-moléculas• F-átomos podem ser aninhado em F-moléculas

C::D ou O:C, onde C, D e O são termos-id. Uma molécula da forma O[lista de métodos separadas

por ;]. Ex.: isaac:man[father->abraham; son->>{jacob, esau}]

Predicados, Átomos-P e Moléculas-PPredicados, Átomos-P e Moléculas-P Átomo-P: predicado com termos-id como

argumentos.• father(isaac, abraham).• woman(rebekah).• married(isaac, rebekah).

Molécula-P: predicado com átomos-F ou moléculas-F aninhado nos seus argumentos.

married(isaac[father->abraham], rebekah:woman). Aninhamento inverso proibido: predicados não

podem ser aninhados em átomos-F ou moléculas-F.Átomos e Moléculas (F e P)

representam os fatosBanco de dados Banco de dados

extensionalextensional

Expressões de CaminhoExpressões de Caminho Facilidade sintática da linguagem, permitindo acesso

elegante a objetos através de métodos de outros objetos.• O.M O[M->Ro]• O..M O[M->>{Ri}]

Presente em outras linguagems• Ex.: cars = john.cars();• Normalmente só é possível uma dimensão

E se quiséssemos or carros vermelhos fabricados em 1998 que John possui?

Expressoes de FLORID e FLORA permiten:• caminhar ao longo de 2 dimensões:• referenciar propriedades dos objetos no caminho, sem

sair dele.

Expressões de CaminhoExpressões de Caminho Exemplo

%% Declaração da hierarquiaperson :: object.company :: object.john:employee.bob:person.employee :: person.manager :: employee.vehicle :: object[color*->black; produced*=>europe].germany : europe.italy : europe.ferrari :: vehicle[color*->red; produced*->italy].bmw :: vehicle[produced*->germany].mercedes :: vehicle[produced*->germany].audi :: vehicle[produced*->germany].porsche :: vehicle[produced*->germany].f50 : ferrari.boxsterS : porsche.a6 : audi.z8 : bmw.c280 : mercedes.

Expressões de CaminhoExpressões de Caminho Exemplo (cont.)

%% Fatoskarl:employee[vehicles->> {c280, a6, f50, boxterS};

worksFor->siemens].jamesbond:person[vehicles->>z8].siemens:company[country -> germany; president -> karl].X[self->X].

%% ConsultaX:employee[worksFor -> _[president ->

X]] ..vehicles[color->black; produced->_:europe; self->Z].

Numa linguagem do tipo SQL:SELECT X, YFROM X in employeeFROM Y in X.vehiclesFROM Z in europe WHERE X.worksFor.president = X

AND Y.color = blackAND Y.produced = Z

Negação em FLORANegação em FLORA Negação através de “well-founded semantics”,

implementada no XSB Especificada através do operador tnot Atualmente, tnot só pode ser aplicado a predicados

Prolog (não pode ser usado com moléculas-F):- table aux/1.aux(X, Y) :- a[m->>X; a->Y].d[f->Z] :- e[w->Z; v->f(X,Y)], tnot(aux(X, Y)).

Restrição devido ao sistema XSB• Todas as variáveis em predicados negados têm que

ser instanciadas antes da chamada a tnot.

HerançaHerança Tipos

• Herança Estrutural Propagação das restrições de tipos de métodos

(assinaturas) de uma superclasse para suas subclasses.student::person.person[name=>string].?- student[name => X]X = string.

• Herança Comportamental Propagação do resultado da aplicação de um método de

uma classe para suas instâncias e subclasses Métodos herdáveis são indicados por *-> e *->> Permite overriding Não monotônica

Herança ComportamentalHerança Comportamental Exemplo de comportamento não-monotônico

elephant[color *-> gray; group *-> mammal].royalElephant :: elephant.clyde : royalElephant.

?- clyde[color->X].X/gray

royalElephant[color *-> white].

?- clyde[color->X].X/white

Herança ComportamentalHerança Comportamental Caso mais complexos envolvem herança múltipla ou

herança junto com dedução Exemplo:

b[m *->> c].a : b.a [m ->> d] :- a[m ->> c].• Podemos deduzir que a[m->{c,d}]• Não podemos deduzir nada• F-logic recomenda a 1ª interpretação; FLORA utiliza a

2ª a 1ª é muito difícil de implementar utilizando-se um

mecanismo de dedução top-down.

MetaprogramaçãoMetaprogramação Sintaxe de F-logic permite metaprogramação

naturalmente%% Todas as classes que John é membro?- john : X.%% Todas as superclasses de student?- student :: X

Metavariável: pode ser instanciada com métodos de qualquer aridade• Sintaxe: @M (M segue a sintaxe de nome de variável)• =.. é usado para transformar Metavariáveis em uma

lista contendo o nome do métodos e seus argumentos (bidirecional)

• @M representa um método (não um objeto) não pode ser passada diretamente como argumento para predicados e métodos

Metaprogramação: exemplosMetaprogramação: exemplos Exemplo1: Copia os métodos

de aridade 2 de o1 para o2:- import length/2 from basics.o1[m1@(a1) -> r1].o1[m2@(b1, b2) -> r2].o1[m3 -> r3].o1[m4@(c1, c2, c3) -> r4].

o2[@M -> R] :- o1[@M -> R], @M =..[Mth|Args], length(Args, 2).

Execução?- o2[@M -> R].@M = m2@(b1, b2)R = r2Yes.

Exemplo2: Usando =.. para passar Metavariáveis como argumentos?- mary[@Met -> V], @Meth =.. Param, foo(Param).

foo(P) :- @M =.. P, abc[@M ->> 123].

Verificação de tiposVerificação de tipos FLORA não automaticamente verifica conformidade

das instâncias e sub-classes com as assinaturas de classes.

Metaprogramação permite implementar essa verificação em poucas regrasscalarTypeIncorrect(O, M, R) :- O[X -> R], O:C, C[X=>D], tnot(R:D).

?- scalarTypeIncorrect(obj, method, Result). Útil para checar dados semi-estruturados.

Comparações: exemplo dos Comparações: exemplo dos estudantes/cursosestudantes/cursos

Consultas• Nome dos estudantes junior que fizeram os cursos

cs101 e cs143• Nome e nota dos estudantes junior que fizeram o

curso cs131 nota maior que 3.0

Tabelas

FLORAFLORA Definiçãojoedoe:student[name->”Joe Doe”;

major->cs; year->senior; took->>{[cs123, 2.7]}].jimjones:student[name->”Jim Jones”; major->cs;

year->junior; took->>{[cs101, 3.0], [cs143, 3.3]}].jimblack:student[name->”Jim Black”; major->ee;

year->junior; took->>{[cs143, 3.3], [cs101, 2.7])]. Consultas_:student[name->X; took->>{[cs143, _], [cs101, _]}]._:student[name->X; year->junior;

took->>[cs131, Y]], Y > 3.0.

DATALOGDATALOG Definiçãostudent(‘Joe Doe’, cs, senior).student(‘Jim Jones’, cs, junior).student(‘Jim Black’, ee, junior).took(‘Joe Doe’, cs123, 2.7).took(‘Jim Jones’, cs101, 3.0).took(‘Jim Jones’, cs143, 3.3).took(‘Jim Black’, cs143, 3.3).took(‘Jim Black’, cs101, 2.7). Consultasstudent(Name, _, junior), took(Name, cs101, _),

took(Name, cs143, _).took(Name, cs131, Grade), Grade > 3.0,

student(Name, _, junior).

SQLSQL Definição

• Criação das tabelasCREATE TABLE student(Name char(20),Major char(2),Year int);

CREAT TABLE took(Name char(20),Course char(5),Grade decimal(2,1));

• Adição dos valoresINSERT INTO student VALUES <tuplas>;

INSERT INTO took VALUES <tuplas>;

ConsultasSELECT t.Name

FROM took t, took u, student sWHERE t.Course = ‘cs101’ AND u.Course = ‘cs143’ AND t.Name = u.Name AND s.Year = ‘junior’ AND s.Name = t.Name

SELECT t.Name, t.GradeFROM took t, student sWHERE t.Course = ‘cs131’ AND s.Year = ‘junior’ AND s.Name = t.Name AND s.Grade > 3.0

FLORA x LIFEFLORA x LIFE Vantagens de FLORA sobre

LIFE• distinção classe/objeto• herança (método

herdável/não-herdável• atributo de classe• regra mólecula-F :-

mólecula-F; em life não há regra do tipo -term :- -term, só pred(-term) :- pred(-term)

• Metaprogramação• Integração quase completa

com o XSB e seus módulos

Vantagens de LIFE sobre FLORA• interface x-windows built-

in• paradigma funcional

(conhecimento inerentemente procedimental)

• sem limitação sobre regras recursivas e ocorrência de variáveis livres (fatos universais)

• programação por restrições

• poderosa DCG integrada