Banco de Dados Dedutivos
Rodrigo Pereira
Rodrigo Athaíde
Marcos Antonio
Banco de Dados Dedutivos
1. Introdução
2. Datalog
1. Predicados
2. Regras
3. Consultas
3. Interpretação das Regras
4. Datalog e sua Segurança
Banco de Dados Dedutivos
• Um sistema de banco de dados dedutivo é um
sistema de banco de dados que pode fazer deduções
(ou seja, concluir fatos adicionais) baseando-se em
regras e fatos armazenados no banco de dados.
• Um banco de dados dedutivo usa dois tipos
principais de especificações: fatos e regras.
– Fatos descrevem o mundo real
– Regras são similares as visões relacionais
• Podem ser recursivas.
Datalog
• Linguagem de consulta não procedural baseada na linguagem de
programação lógica Prolog.
• Baseada na lógica relacional.
• Datalog fundamenta-se em cláusulas de Horn como linguagem de consulta
a bases de dados relacionais.
not (P1) OR not (P2) OR ... OR not (Pn) OR Q
…
P1 AND P2 AND ... AND Pn => Q
Datalog
• Predicado p(a1, a2, ..., an) tem número de
argumentos fixo.
– Argumentos têm interpretação posicional.
– Predicado é ground se todos seus argumentos
forem constantes.
supervisiona(X,Y)
‘X supervisiona Y’
supervisiona(franklin,john).
supervisiona(franklin,ramesh).
supervisiona(franklin,joyce).
– Tuplas da relação SUPERVISIONA(Supervisor, Subordinado) determina
fatos que definem o predicado supervisiona.
Datalog
• Uma regra é da forma P  Q
– P é um predicado relacional chamado cabeça
– Q é uma conjunção de predicados chamada corpo
-------cabeça---- ------ corpo ------superior(X,Y) :- supervisiona(X,Y)
EXPClimbers(N) :- Climbers(_,N,exp,_)
(variável anônima)
• Uma regra especifica que, se uma atribuição em particular às
variáveis no corpo tornar todos os predicados verdadeiros,
também tornará a cabeça verdadeira usando a mesma
atribuição de valores constantes às variáveis.
Datalog
•
Uma regra proporciona um modo de gerar novos fatos, que são instanciações da
cabeça da regra.
superior(X,Y) :- supervisiona(X,Y).
Superior(X,Y) :- supervisiona(X,Z), superior(Z,Y).
Subordinado(X,Y) :- superior(Y,X).
->
regra recursiva
supervisiona(james,franklin).
superior(franklin,john).
Superior(james,john).
SUPERVISIONA (Supervisor, Subordinado)
– A aplicação da regra Superior(X,Y) irá gerar novos fatos incluindo os
subordinados indiretos em todos os níveis.
Predicados Intensionais X Extencionais
• Predicados extensionais são aqueles cujas
relações estão guardadas na bd
• Predicados intencionais são aqueles que são
calculados aplicando uma ou mais regras.
Predicados Intensionais X Extencionais
Student (123,j.smith,compsci)
Student(456,k.tappet,french)
Offers(cookery,baking)
Offers(compsci,compilers)
Enroll(123,baking)
Enroll(012,compilers)
InterestedIn(X,S) ¬Student(X,Y,S)
InterestedIn(X,S) ¬ Enroll(X,Z) AND Offers(S,Z)
Datalog
•
Uma consulta em Datalog envolve um símbolo de predicado, com alguns
argumentos variáveis, e seu significado é deduzir todas as possíveis combinações
constantes que, quando carregadas nas variáveis, possam fazer o predicado
verdadeiro.
Consultas:
superior(james, Y)
SUPERVISIONA(Supervisor, Subordinado)
todos os subordinados
superior(james,joyce)
true
Interpretação de Regras
• Duas formas de análise:
– Prova-teórica
• Certifica-se se certo fato se comprova
• Regras são axiomas dedutivos
• Fatos são axiomas fundamentais
– Modelo-teórico
• A partir de fatos conhecidos como verdadeiros ou
falsos, gera novos fatos
Interpretação de Regras
• Prova-teórica
1. superior(X,Y):- supervisiona(X.Y). (regra 1)
2. superior(X,Y):- supervisiona(X.Z), superior(Z,Y). (regra 2)
3. supervisiona(jennifer,ahmad). (axioma fundamenta, dado)
4. supervisiona(james,jennifer). (axioma fundamenta, dado)
5. superior(jennifer,ahmad). (aplicar a regra 1 em 3)
6. superior(james,ahmad). (aplicar a regra 2 em 4 e 5)
Interpretação de Regras
• Modelo-teórico
Regras
superior(X.Y) : - supervisiona(X,Y).
superior(X.Y) : - supervisiona(X,Z), superior(Z.Y).
Fato conhecido:
supervisiona(franklin,john) é verdadeiro.
Fato derivado:
superior(franklin,john) é verdadeiro.
Segurança
Condições para regras seguras:
-Cada variável que aparece no cabeçalho da
regra também aparece em uma literal
positiva não aritmética, no corpo da regra
- Cada variável aparecendo em uma literal
negativa no corpo da regra também aparece
em alguma literal positiva no corpo da regra
Segurança
• Algumas regras inseguras:
Likes(X,Y) :- Starved(X)
Lazy(X) :- NOT Climbers(_,X,_,_)
• Algumas regras seguras:
Likes(X,Y) :- Starved(X) AND Food(Y)
Lazy(X) :- Person(X) AND NOT Climbers(_,X,_,_)
Segurança
Mais exemplos:
As regras abaixo são seguras?
NOT superior(X.Y) : - NOT supervisiona(X,Z), superior(Z.Y)
supervisor(X,Z) :- empregado(X), supervisiona(X,Y)
Obrigado.