Cálculo Relacional
Datalog não-recursivo
AULAS 3 e 4
PGC 107 - Sistemas de Banco de Dados
Profa. Sandra de Amo
Pós-graduação em Ciência da Computação – UFU
2012-2
Cálculo Relacional de Domínio

Expressão do tipo
{(x1,...,xn) | F(x1,…,xn)}
onde F é fórmula da Lógica de 1a ordem
x1,...,xn são variáveis livres de F
Observação:
R(x1,...,xn) é o mesmo que a expressão “ (x1,...,xn) ɛ R ”
Exemplo

Seja R = { R(A,B), S(A,C)}
F(x,y) = R(a,x) ˄ S(a,y)
q= { (x) | R(a,x) ˄ S(a,x) }
Resposta de q = ΠBσA=a ( R
S)
Algebra  Cálculo

Para toda consulta E da Algebra Relacional
existe uma consulta E’do Cálculo Relacional
equivalente.
Prova
Por indução na construção da expressão algébrica
Base da indução: E = R onde R(A1,...An) ɛ R
E’ = R(x1,...,xn)
Hipótese de Indução: suponha que para as expressões F e G da AR
existem fórmulas do CR correspondentes.
1) E = F x G
E’ = F ˄ G
2) E = F U G
E’ = F ˅ G
3) E = F – G
E’ = F ˄ ¬ G
Prova (continuação)
4) E = ΠX F onde X = {A1,...,An} atributos aparecendo em F
E’ = x1... xn F’(y1,...,yk) onde
x1,...,xn correspondem aos atributos de X
y1,....,yk correspondem aos atributos de F que não estão
em X
5) E = σA=a F
E’ = F(x1,...,xn) ˄ xi = a
onde x1,...,xn correspondem aos atributos de F e xi corresponde ao atributo A
Repare que não aparecem quantificadores universais, nem negação fora de uma
conjunção – Fórmulas correspondentes à AR são “especiais” quanto ao V e ¬
Exemplo
E = R(A,B)
S(A,B)
E’(y,z) = x (R(x,y) ˄ S(x,z))
Consulta do Cálculo relacional
{ (y,z) | E’(y,z) }
Expressões do C.R.
independentes do domínio
Resposta de uma consulta deve ser uma relação finita.
Todos os cálculos intermediários devem envolver conjuntos
finitos
Problemas com as consultas:
{ (x) | ¬ R(x)}
{ (x,y) | R(x) ˅ S(y) }
{ (x) | y R(x,y) }
Todas estas consultas são dependentes do domínio dos atributos,
isto é, a resposta depende do domínio considerado.
Independência do Domínio

Uma consulta é independente do domínio se e
somente se sua resposta só depende do conteúdo do
banco de dados, e não do domínio dos atributos.

Independência do Domínio = noção semântica

Problema Indecidível = dada uma consulta q, q é
independente do domínio ?
Fórmulas Seguras
O que se deseja:



Expressões seguras devem ser Ind.Dom.
É possível decidir, só analisando a forma
sintática da expressão, se ela é ou não segura.
Todas as fórmulas correspondentes a
expressões da A.R. são seguras.
Fórmulas Seguras (noção sintática)



Não possuem o quantificador universal – não há perda de
expressividade, pois F = ¬ ¬ F
F(x1... xn ) ˅ G(x1... xn)
variáveis livres de F = variáveis livres de G
F = G1 ˄ G2 ˄ .... ˄ Gn conjunção maximal (não há mais ˄ “acima”)
Então todas as variáveis livres de F devem ser limitadas




x é limitada se aparece em algum Gi onde Gi não é uma expressão
aritmética nem é precedida por uma negação.
x é limitada se aparece numa fórmula do tipo x = a ou a = x, onde a é
constante.
x é limitada se aparece numa fórmula x = y ou y = x, onde y é limitada.
Uma negação só pode aparecer numa conjunção
F = G1 ˄ G2 ˄ .... ˄ ¬ H ˄ ... ˄ Gn, onde um dos Gi são positivos
(não negados)
Árvore de uma fórmula segura F
Conectivo ˄*(G1,...,Gk) = G1 ˄ G2 ˄ ... ˄ Gk (k ≥ 1)
Conectivos lógicos
distintos de ˄, ¬
Conectivo ˄*
Árvore de F
¬
Exemplo

R(x,y,z) ˄ ¬ ( P(x,y) ˅ Q(y,z) ) não é segura.

Porém é independente do domínio

R(x,y,z) ˄ ¬ ( P(x,y) ˅ Q(y,z) ) é equivalente a uma
fórmula segura
R(x,y,z) ˄ ¬ P(x,y) ˄ ¬ Q(y,z)
Discussão




Toda variável livre de uma fórmula segura é
limitada
Segura implica Independente do dominio
Independente do domínio não implica segura
Uma fórmula pode ser independente do
domínio e não ser segura.
Exercícios
1) Mostrar que as fórmulas do Cálculo Relacional
correspondentes a expressões da Algebra Relacional são
fórmulas seguras.
Logo : Algebra  Cálculo Seguro
2) Mostrar que toda fórmula do cálculo relacional seguro é
independente do dominio.
3) Mostrar que toda variável livre aparecendo em uma fórmula
segura é limitada.
Datalog
Consulta Datalog = Programa Prolog especial
Conjunto finito de regras do tipo:
p(x) :

L1(x1), ...,Ln(xn)
Li são literais do tipo q(x) ou ¬ q(x)
não aparecem símbolos funcionais nas regras
Prolog = linguagem de programação - executa cálculos com os
dados.
Datalog = linguagem de consulta – manipula dados
Predicados extensionais, intensionais e
built-in
Predicados extensionais




Predicados intensionais


aparecem no esquema do banco de dados.
São os dados (fatos) disponíveis no banco de
dados.
Só aparecem no corpo das regras
aparecem no corpo e cabeça das regras
Built-in : >, <, =, ≠≤ , ≥, etc
Exemplo
(1)
(2)
(3)
(4)
(5)
(6)
(7)
irmao(x,y) :- pais(x,z), pais(y,z), x ≠ y
primo(x,y) :- pais(x,x’), pais(y,y’), irmao(x’,y’)
primo(x,y) :- pais(x,x’), paix(y,y’),primo(x’,y’)
parente(x,y) :- irmao(x,y)
parente(x,y) :- primo(x,y)
parente(x,y) :- parente(x,z), pais(y,z)
parente(x,y) :- parente(z,y), pais(x,z)
Extensionais: pais
Intensionais: irmao, primo, parente
Grafo de Dependência e Recursão
Grafo de Dependência associado a uma consulta Datalog =
G(V,E)
 V=predicados extensionais e intencionais
 E =(p,q) se p aparece no corpo de uma regra e q aparece
na cabeça desta regra.
q
q(x):- ...., p(y), ....
p
Predicados recursivos: que aparecem em algum ciclo
Programa recursivo: grafo de dependência contém ao menos um
predicado recursivo
Exemplo
parente
primo
irmão
pais
Predicados recursivos: primo, parente
Predicados não-recursivos: pais, irmão
Predicados extensionais são sempre não- recursivos
Regras Seguras



maior-que(x,y) :- x > y
define uma relação infinita maior-que
ama(x,y) :- ator-de-novela(y)
define uma relação infinita ama (todo mundo ama algum
ator-de-novela)
Impor que as regras sejam seguras vai impedir a geração de
respostas infinitas
Regras Seguras

Variáveis limitadas




aparecem no corpo das regras em predicados
intensionais ou extensionais
aparecem em predicados built-in x=a, a=x, onde a
é constante.
se X = Y ou Y = X aparece no corpo de uma regra
e Y é limitada então X também é limitada.
Definição : Uma regra é segura se todas as
suas variáveis são limitadas
Exemplo
Maior-que(x,y) :- x > y
não é segura
 p(x,y) :- q(x,z), w = a, y = w
w, y são limitadas, x, z são limitadas
Logo a regra é segura
Esta consulta corresponde à expressão da AR
Π1q X {a}

Consulta Datalog sobre um banco de
dados
R = {p1,...,pn} esquema de BD
Uma consulta Datalog sobre R é um par (P, q) onde
 P é programa Datalog seguro,
 Todos os predicados extensionais estão em
{p1,...,pn}
 q é um predicado intensional que aparece em P (é o
predicado correspondente à resposta da consulta)

Como é calculada a resposta a uma
consulta Datalog





R = {p1,...,pn} esquema de BD
I = instância de banco de dados sobre R
P uma consulta Datalog sobre R
Construimos o programa P’
P’ = P unido com as regras básicas (fatos):
p1(a1,...,ak).
p1(a1,...,ak).
...
p2(b1,...,bm)
...
Calcula-se a resposta de P’
Exemplo
R = {pais(Nome1,Nome2)}
I(pais) = {(a,b), (a,c), (b,d), (b,k), (c,f)}

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
irmao(x,y) :- pais(x,z), pais(y,z), x ≠ y
primo(x,y) :- pais(x,x’), pais(y,y’), irmao(x’,y’)
primo(x,y) :- pais(x,x’), paix(y,y’),primo(x’,y’)
parente(x,y) :- irmao(x,y)
parente(x,y) :- primo(x,y)
parente(x,y) :- parente(x,z), pais(y,z)
parente(x,y) :- parente(z,y), pais(x,z)
pais(a,b).
pais(a,c).
pais(b,d).
pais(b,k).
pais(c,f).
Método 1 – Modelo Minimal
R = {r(A)} Instância = {r(1)}
p(x) :- q(x)
q(x) :- r(x)
r(1).
p : predicado resposta


Modelo do programa : conjunto de fatos que tornam as regras
verdadeiras.
Ex: {r(1), q(1), p(1), q(2), p(2)} é um modelo
Modelo minimal = intersecção de todos os modelos
Ex: {r(1), q(1), p(1)}
Resposta à consulta = Modelo minimal do programa
p(1)
Só funciona se o programa não contém negações.
Como calcular o Modelo Minimal
T0 = fatos do BD
T1 = T0 U {A | A :- p1, …, pn e p1, …, pn ɛ T0}
T2 = T1 U {A | A :- p1, …, pn e p1, …, pn ɛ T1}
….
Até atingir um Tn tal que Tn = Tn-1 (não há mais mudanças)
p(x) :- q(x)
q(x) :- r(x)
r(1).
T0 = {r(1)}
T1 = {r(1),q(1)}
T2 = {r(1),q(1),p(1)}
T3 = T2
Método 2: Resolução
:- p(x)
:- q(x)
:- r(x)
x=1
□
Resposta = p(1)
p(x) :- q(x)
q(x) :- r(x)
r(1).