Banco de Dados Dedutivos
Orientados a Objetos e FLORA
Sérgio Queiroz
[email protected]
CIn - UFPE
Recife, dezembro de 1999
Roteiro







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éculasF 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 Metaprogramação
FLORA x SQL
FLORA x DataLog
FLORA x LIFE
Problemas enfrentados pela área de banco
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



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 Objetos
BDOO:
identidade de objetos
objetos complexos
classes
encapsulamento
herança
overriding, overloading e
late binding
extensibilidade
linguagem de consulta
declarativa
embasamento teórico
Bancos de Dados Dedutivos
fundamentação lógica
linguagem declarativa
poderosa com mecanismo de
dedução
tipos abstratos de dados
identidade de objetos
modelo de dados flat
BDDOO
Estratégias para construção de um DOOD
Utilização
da
linguagem declarativa
existente
Integração da
linguagem declarativa
existente às novas
extensões orientadas a
objetos
Tempo
de adaptação
à linguagem
Flexibilidade da
integração:
bidirecional,
unidirecional.
Impedance Mismatch
Semântica
Uma
Formal
única
linguagem
Reconstrução
total do sistema
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 FLORA
FLORID (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 “é um”
person
degree
ms
child(person)
phd
empl
john
child(john)
dept
phil
sally
cs2
cs1
student
faculty
manager
alice
mary
bob
...
report
young
midaged
article
datatype
40
cacm
jacm
20
yuppie
string
codd70
flogic94
30
integer
"CS"
"Mary"
empl :: person
student :: person
faculty :: empl
child(person) ::
person
john : student
john : empl
cs1 : dept
"Bob"
yuppie :: young
20 : young
30 : yuppie
40 : midaged
"CS" : string
"Bob" : string
alice : child(john)
...
BD 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:
informaçõ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:
regras 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:
consultas

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-logic
Alfabeto 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
classes
Oid (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 assinaturas
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é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-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 fatos
Banco de dados extensional
Expressõ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 Caminho

Exemplo
%% Declaração da hierarquia
person :: 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 Caminho

Exemplo (cont.)
Numa linguagem do tipo SQL:
SELECT X, Y
%% Fatos
FROM X in{c280,
employee
karl:employee[vehicles->>
a6, f50, boxterS};
worksFor->siemens].
FROM Y in X.vehicles
jamesbond:person[vehicles->>z8].
FROM Z in europe
siemens:company[country
WHERE X.worksFor.president
-> germany;
= X
president
AND Y.color
-> karl].
= black
X[self->X].
AND Y.produced = Z
%% Consulta
X:employee[worksFor -> _[president -> X]]
..vehicles[color->black;
produced->_:europe;
self->Z].
Negaçã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ç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 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 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çã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: 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 = r2
Yes.

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 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 regras
scalarTypeIncorrect(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
estudantes/cursos

Tabelas
Name
Joe Doe
Jim Jones
Jim Black

student
Major
cs
cs
ee
Year
senior
junior
junior
Name
Joe Doe
Jim Jones
Jim Jones
Jim Black
Jim Black
took
Course
cs123
cs101
cs143
cs143
cs101
Grade
2.7
3.0
3.3
3.3
2.7
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
FLORA
 Definição
joedoe: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.

DATALOG
 Definição
student(‘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).
 Consultas
student(Name, _, junior), took(Name, cs101, _),
took(Name, cs143, _).
took(Name, cs131, Grade), Grade > 3.0,
student(Name, _, junior).
SQL

Definição
• Criação das tabelas
CREATE 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 valores
INSERT INTO student
VALUES <tuplas>;
INSERT INTO took VALUES
<tuplas>;

Consultas
SELECT t.Name
FROM took t, took u, student
s
WHERE 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.Grade
FROM took t, student s
WHERE t.Course = ‘cs131’ AND
s.Year = ‘junior’ AND
s.Name = t.Name
AND
s.Grade > 3.0
FLORA 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