Banco de Dados com Regras:
Ativos e Dedutivos
Jacques Robin & Frederico Fernandes
CIn-UFPE
BD ativos: definição e motivação
Modelar declarativamente interação complexa entre
comportamentos e dados em grande quantidades
 Diminuir custo do controle dos dados (ex, restrições)
 Idéia: mover classes de comportamentos ativos comuns a
várias aplicações para o BD
 BD ativo deve oferecer:

• um modelo de conhecimento (uma descrição do mecanismo)
• um modelo de execução (estratégias à nível de execução)

Regras: Eventos, Condição, Ação (ECA)
BD ativos: aplicações práticas

Extensão para sistemas de BD:
• Restrições de integridade, visões materializadas, dados
derivados
• Ex:






on insert into wire
if insert.voltage > any (select max-voltage
from wire-type
where type = insert.type)
do <action>
Implementação no BD de aplicações fechadas:
• Comportamento interno dos dados da aplicação
• Ex:
BD ativos: aplicações práticas
• Ex:








On update to value of Holder
if new.value = 0
do begin
delete from Holder where reg# = update.reg#;
insert into VoidHolder
values (update.reg#, update.name, update.address, today)
end
Implementação no BD de aplicações abertas:
• Respostas para dispositivos ou software fora do BD
• Ex:





on update to pos of aircraft
if exists (select * from aircraft Other
where distance (Other.pos, new.pos) < 5000 and
distance (Other.pos, old.pos) > 5000)
do <envia mensagem ao controlador>
BD ativos: exemplo didático de aplicação
Reg#
Stock#
name
name
Holder
M
Owns
N
Stock
qty
coutry
value
qty
price
on delete to Holder
if delete.value > 0
do instead <informa ao gerenciador do sistema>
BD ativos: dimensões para caracterizar
modelos de conhecimento

Evento
• Fonte  {operação estruturada, invocação do comportamento,
transação, abstrato, exceção, relógio, externo}
• Granularidade  {membro, subconjunto, conjunto}
• Tipo  {primitivo, composto}
• Operadores  {or, and, seq, closure, times, not}
• Modo de Consumo  {recente, crônico, acumulativo, contínuo}
• Papel  {obrigatório, opcional, nenhum}

Condição
• Papel  {obrigatório, opcional, nenhum}
• Contexto  {DBT, BindE, DBE, DBC}

Ação
• Opções  {operação estruturada, invocação do comportamento,
regras de atualização, notificação de aborto, externo, do instead}
• Context  {DBT, BindE, DBE, DBC, DBA}
BD ativos: agendamento
da execução das regras
BindC
BindE
Evento
DBT

DBE
Condição
Ação
DBC
DBA
on update to value of Holder
if new.value = 0
do <delete Holder | send message to manager>
BD ativos: dimensões para caracterizar
modelo de execução
Modo de condição  {imediato, adiado, desligado}
 Modo de ação  {imediato, adiado, desligado}
 Granularidade de Transição  {tupla, conjunto}
 Net-effect policy {sim, não}
 Cycle policy  {interativo, recursivo}
 Prioridades {dinâmico, numérico, relativo, nenhum}
 Agendamento  {paralelo, sequencial, saturação, algum }
 Manipulação do Erro  {abortar, ignorar, backtrack,
contingência}

Fonte do
Evento
Ocorrência
do Evento
Regras
Disparadas
Regras
Avaliadas
Regras
Selecionadas
Execução
BD ativos: dimensões para caracterizar
gerenciamento de regras
Descrição  {linguagem de programação, linguagem de
consulta, objetos}
 Operações  {ativar, desativar, sinalizar}
 Adaptabilidade  {tempo de compilação, tempo de
execução}
 Modelo de Dados  {relacional, relacional extendido,
dedutivo, orientado a objeto}
 Suporte para programador  {consulta, trace}

BD ativos: arquitetura
Conjunto
de Conflito
Base de
Regras
leitura
escrita
leitura
Detector
de Evento
eventos
detectados
Monitora
a Condição
regras
disparadas
Agendamento
Avaliação de condição
leitura
escrita
notificação
História
BD
ação
execução
leitura/escrita
leitura/escrita
Avaliador
da Consulta
BD ativos: análise de regras
para segurança de execução

Terminação
R1
• Posso garantir que uma regra irá terminar ?
• Ex: R1-R3 não, mas R1-R2-R4 sim

Confluência
R2
R3
R4
• A ordem de processamento de duas regras simultâneas interfere
no resultado ?
• Ex:
on insert to Owns or update to reg# of Owns or update to reg# of Holder
if <mudança afetar a quantidade do estoque do Holder h>
do <update NumStocks attribute of h>
on insert to Owns or update to reg# of Owns or update to reg# of Holder
if <quantidade do estoque do Holder h é maior do que o do NumStocks>
do <reduza a faixa de estoque do Holder h>
BD ativos: análise de regras
para segurança de execução (Cont.)

Determinismo observável
• O efeito observável de uma regra por um usuário do sistema, é
independente da ordem em que as regras são disparadas ?
• Ex:
on <evento E1>
on <evento E1>
if <condição C1>
if <condição C1>
do <abort>
do <mande uma mensagem>

Depuração de regras
• Dificuldade em visualizar terminação, confluência e determinismo
observável em grandes bases de regras.
• Necessita ferramentas sofisticadas de análise de interação
entre regras, especialmente temporal
Criação de Regras em Oracle
<oracle-trigger> ::= CREATE TRIGGER <nome-do-trigger>
{ BEFORE | AFTER } <eventos trigger>
ON <nome-da-tabela>
[[ REFERENCING <referências> ]
FOR EACH ROW
[ WHEN (<condition>) ]] <PL / bloco SQL>
<evento trigger> ::= INSERT | DELETE | UPDATE
[ OF <nome-das-colunas> ]
<referência>
::= OLD AS <valor antigo de um atributo>
NEW AS < valor novo de um atributo>
Exemplo de Regra em Oracle
CREATE TRIGGER FazPedido
AFTER UPDATE OF NumItens ON Estoque
WHEN (New.NumItens < New.ValorMinimo)
FOR EACH ROW
DECLARE NUMBER X
BEGIN
SELECT COUNT (*) INTO X
FROM PedidosPendentes
WHERE ItemPedido = New.ItemPedido;
IF X = 0
THEN
INSERT INTO PedidosPendentes
VALUES (New.ItemPedido, New.QuantidadePedida, SYSDATE)
END IF;
END;
Exemplo de Regra em Oracle (Cont.)
#Item
NumItens
ValorMinimo
QuantidadePedida
1
2
3
200
780
450
150
500
400
100
200
120
Tabela1: Estoque
T1: UPDATE Estoque
SET NumItens = NumItens – 70
WHERE Item = 1
FazPedido
#Item
Quant.
Data
1
100
24/04/2000
Tabela2:PedidosPendentes,
PedidosPendentes,antes
apósde
T1T1
Tabela2:
FazPedido #Item
T2: UPDATE Estoque
SET NumItens = NumItens – 60
1
WHERE Item >= 1
3
Quant.
Data
100
120
24/04/2000
24/04/2000
Tabela3:
Tabela3:PedidosPendentes,
PedidosPendentes,antes
apósdeT2T2
Origens dos BD dedutivos:
programação em lógica

Metáfora da programação em lógica:
• Teoria lógica (TL) = especificação formal = programa executável
= Base de conhecimento (BC) de agente inteligente = BD dedutivo
• Unifica: teoria da computação, engenharia de software, BD e IA
Axiomas da TL = fatos iniciais da BC = dados explícitos
de um BD tradicional = parte extensional do BDD
 Regras da TL = regras da BC = parte intencional do BDD
 Teoremas da TL, deduzidos pela aplicações da regras
sobre os axiomas (e teoremas) = fatos derivados da BC
= dados implícitos do BDD
 Programar = especificar = declarar axiomas e regras
 Executar programa = provar teorema = disparar motor
de inferência do agente sobre sua BC = consultar BDD

BD dedutivos: definição de Prolog

Prolog:
• Linguagem de programação de propósito geral (turing-complete)
• Primeira, mais simples e ainda mais usada do paradigma lógico

Programa Prolog:
• conjunto implicitamente conjuntivo de cláusulas de Horn, i.e.,
• formulas da lógica da 1a ordem da forma: P1   Pn  C

Muitas mas nem todas das formulas da 1a ordem tem
conjunto equivalente de cláusulas de Horn, cex:
X, Y animalLover(X)  animal(Y)  kills(X, Y)
Lógica de Horn: LH1  f  L1/h1 , h n claúsulas de Horn, f
 Interpretador/Compilador Prolog:

 h1    h n 
• provador de teorema para lógica de Horn
• com hipótese do mundo fechado e negação por falha
BD dedutivos: unificação de termos Prolog

Substituição de variáveis de um termo (ou formula) f:
•

conjunto de pares Var/termo
Unificação de 2 termos f e g:
• substituição S das variáveis de f e g tal que S(f)=S(g)
• 2 resultados:





S
r=S(f)=S(g)
Exemplos:
?- prof(X,disc(Y,dept(di,ufpe))) = prof(geber,disc(ia,Z)).
X = geber, Y = ia, Z = dept(di,ufpe).
? prof(X,disc(X,dept(di,ufpe))) = prof(geber,disc(ia,Z))
fail
Unificador mais geral: com menor número de variáveis instanciadas
Substituição mínima: com menor número de pares Var/const
BD dedutivos: consulta West é criminoso?
da lógica da 1a ordem para Prolog

Em L1:
 P,W,N american(P)  weapon(W) 
nation(N)  hostile(N) 
sells(P,N,W)  criminal(P)
2.  W owns(nono,W)  missile(W)
3.  W owns(nono,W)  missile(W)
 sells(west,nono,W)
7.  X missile(W)  weapon(W)
8.  X enemy(N,america)
 hostile(N)
4. american(west)
5. nation(nono)
6. enemy(nono,america)
9. nation(america)

Em Prolog:
criminal(P) :- american(P), weapon(W),
nation(N), hostile(N),
sells(P,N,W).
owns(nono,m1).
missile(m1).
sells(west,nono,W) :- owns(nono,W),
missile(W).
weapon(W) :- missile(W).
hostile(N) :- enemy(N,america).
american(west).
nation(nono).
enemy(nono,america).
nation(america).
BD dedutivos: consulta West é criminoso?
processada por Prolog
criminal(P) :- american(P), weapon(W),
nation(N), hostile(N),
sells(P,N,W).
owns(nono,m1).
missile(m1).
sells(west,nono,W) :- owns(nono,W),
missile(W).
weapon(W) :- missile(W).
hostile(N) :- enemy(N,america).
american(west).
nation(america).
enemy(nono,america).
nation(nono).
criminal(west)? <- yes.
•american(west)? -> yes.
•weapon(W)? <- W = m1.
missile(W)? -> W = m1.
•nation(N)? -> N = america.
•hostile(america)? <- no.
enemy(america,america)? -> no.
•backtrack: nation(N),
N \ {america}? -> N = nono.
•hostile(nono)? <- yes.
enemy(nono,america)? -> yes.
•sells(west,nono,m1)? <- yes.
owns(nono,m1)? -> yes.
missile(nono,m1)? -> yes.
BD dedutivos: controle e busca de Prolog

Aplica regra de resolução:
• tupla por tupla
• com estratégia linear (sempre tenta unificar ultimo fato a provar
com a conclusão de uma cláusula do programa),
• na ordem de escritura das cláusulas no programa,
• com encadeamento de regras para trás,
• busca em profundidade e
• da esquerda para direita das premissas das cláusulas,
• e com backtracking sistemático e linear quando a unificação
falha,
• e sem occur-check na unificação.
Limitações de Prolog como SGDB dedutivo

Sem semântica declarativa
para:
•
•
•
•
•

negação por falha
atualizações do BD
manipulação de conjuntos
consulta do esquema do BD
resultado depende da ordem
das cláusulas e das premissas
Não fornece built-in a maioria
dos serviços de BD:
•
•
•
•
persistência
concorrência
transações
operadores de agregação


Pode entrar em loop infinita
com algumas regras recursivas
Devolve respostas a consulta:
• uma por uma
• BD devolvem todas de uma vez

Conseqüêntemente:
• inadequado para otimização de
consultas
• especialmente as envolvendo
quantidade de dados que não
cabe inteiramente na RAM
Datalog
Sub-linguagem de Prolog usado como modelo de dados
padrão em BD dedutivos
 Mais expressivo do que cálculo relacional mas menos
expressivo do que cálculo do predicados da 1a ordem
 Exclui maioria dos predicados built-in de Prolog com
semântica declarativa fora da lógica da 1a ordem
 Datalog básico adicionalmente exclui termos aninhados

• ex, person(name(FirstName,LastName),weight(Value,Unit))
Datalog é apenas uma notação independente de qualquer
estratégia de resolução
 SGBD Datalog usam variedade de tais estratégias

Datalog x SQL: características
Predicado de base Datalog = tabela ou relação SQL
 Predicado derivado Datalog = visão SQL
 Fato Datalog = linha ou tuple SQL
 Argumento de predicado Datalog = coluna ou atributo
SQL
 Regras Datalog permitem definições recursivas de visões
 Interpretadores e compiladores Datalog diferem de
Prolog por tentar:

• garantir independência dos resultados das consultas da ordem
das cláusulas e premissas do BD Datalog
• garantir terminação de qualquer consulta sintaticamente correta
Datalog x SQL: exemplo
firstreq(Name) :student(Name,Major,junior),
took(Name,cs101,Grade1),
took(name,cs143,Grade2).
?- firstreq(Name).
SELECT t.Name
FROM took t, took u, student s
WHERE t.Course = ‘cs101’
AND u.Coruse = `cs143’
AND t.Name = u.Name
AND s.Year = ‘junior’
AND s.Name = t.Name
Semântica de Datalog baseada em modelos
Universo de Herbrand:
U(D) = const(D) U {f(..., c , ...) |
f  func(D)  c  const(D)}.
Base de Herbrand:
B(D) = U(D) U {p(…, g, …) |
p  pred(D)  g  B(D)}.
Modelo de Herbrand:
M(D) = {g  B(D) | D |= g}.
Exemplo:
D = {male(paulo). female(ana). male(joao).
parent(paulo,joao). parent(ana,joao).
father(F,C) :- parent(F,C), male(F).
mother(M,C) :parent(F,C), female(M).}
U(D) = {paulo,ana,joao}
B(D) = {male(paulo). male(ana). male(joao).
female(paulo). female(ana). female(joao).
father(paulo,ana). father(paulo,joao).
father(ana,joao). father(ana,paulo).
father(joao,paulo).father(joao,ana).
mother(paulo,ana). mother(paulo,joao).
mother(ana,joao). mother(ana,paulo).
mother(joao,paulo).mother(joao,ana).
parent(paulo,ana). parent(paulo,joao).
parent(ana,joao). parent(ana,paulo).
parent(joao,paulo).parent(joao,ana).}
M(D) = {male(paulo). female(ana). male(joao).
parent(paulo,joao). parent(ana,joao).
father(paulo,joao).
mother(ana,joao).}
Semântica de Datalog
baseada em operador de ponto fixo
ground(D) = {regras de D instanciadas com elementos de
U(D)}.
 Operador de conseqüências imediatas:

• To(D) = B(D).
• Tn(D) = Tn-1(D) U {c  B(D) |  r: c :- p1, ...pN  ground(D)
 p1, ...,pN  Tn-1(D)}.

Exemplo:
• D = {anc(X,Y) :- parent(X,Y)., anc(X,Z) :- anc(X,Y), parent(Y,Z).,
•
parent(X,Y) :- father(X,Y)., parent(X,Y) :- mother(X,Y).,
•
mother(anne,silvia)., mother(anne,marc).}
• T1(D) = {anc(marc,silvia).,anc(anne,silvia)., mother(anne,silvia).,
•
mother(anne,marc)., mother(anne,silvia).}
Limitações de DataLog básico como
linguagem de consulta em BD
Negação por falha
 Valores complexos: estruturas e conjuntos
 Consulta ao esquema
 Atualizações
 Transações
 Prolog:

• fornece predicados built-in para todas essas funcionalidades,
exceto transações
• porém sem semântica declarativa lógica
 sem segurança sobre terminação e corretude das consultas

Desafios de BDD:
• definir e implementar extensões de DataLog básico
• fornecendo esses serviços com uma semântica declarativa
Prolog: problema da negação por falha

Permite raciocínio não monótono:
ave(piupiu).
papa_leguas(bipbip).
ave(X) :- papa_leguas(X).
voa1(X) :- ave(X), not papa_leguas(X).
voa1(X)? -> X = piupiu ; no.


Sem semântica declarativa em L1
Depende da ordem, ex:
voa2(X) :- not papa_leguas(X), ave(X).
voa2(X)? -> no.

Pode tornas resolução de
Prolog inconsistente
• ex: edge(a,b).
sink(X) :- not edge(X,Y).
sink(a)? -> no.
sink(b)? -> yes.
sink(X)? -> no.
Grafo de dependência e estratificação
partCost(topTube,cinelli,20.00,14).
partCost(topTube,columbus,15.00,6).
Strata 3
howsoon
...
assembly(bike,frame,1).
assembly(bike,wheel,2).
not
larger
time4basic
...
basicSubparts(Bsp,Bsp) :- partCost(Bsp,_,_,_).
basicSubparts(Part,Bsp) :assembly(Part,Sp,_), basicSubparts(Sp,Bsp).
fastest(Part,Time) :- partCost(Part,Sup,Cost,Time),
not faster(Part,Time).
faster(Part,Time) :- partCost(Part,Sup,Cost,Time),
partCost(Part,Sup1,Cost1,Time1), Time1 < Time.
time4basic(AssPart,BasicSub,Time) :basicSubparts(AssPart,BasicSub),
fastest(BasicSub,Time).
howsoon(AssPart,Time) :time4basic(AssPart,BasicSub,Time),
not larger(AssPart,Time).
larger(Part,Time) :- time4basic(Part,_,Time),
time4basic(Part,_,Time1), Time1 > Time.
basicSubpart
fastest
Strata 2
not
Strata 1
assembly
faster
partCost
HiLog

Extensão sintática de Prolog e Datalog permitindo
variáveis em posição de predicados:
• internamente traduzido por expressão da 1a ordem e assim a
semântica de HiLog permanece na lógica da 1a ordem.
• Útil para aplicações requerendo meta-programação, como
consulta de esquema de BDD

Exemplos de expressões HiLog e suas traduções em
termos da 1a ordem:
X(Y, Z, Y(W)) traduzido para apply(X,Y,Z,apply(Y,W))
h(map(P)(A,B))(C) traduzido para apply(apply(h,apply(map(P),A,B)),C)
Consultar esquema de BDD com HiLog





hardware(joe,30,2200).
software(paulo,26,2200).
admin(magaly,29,1500).
...
p1(R) :- R(_,_,_).






?- p1(R).
R = {hardware,software,admin}
?- p2(R).
R = hardware
?- p3(N).
N = {joe,paulo,magaly, ...}
Limitação principal de HiLog: relações de aridade fixa, com
elementos ordenados e acessíveis apenas por posição
BD dedutivos: consultas declarativas
para conjuntos
Datalog básico sem tuplas aninhadas, nem conjuntos
 Prolog tem:

• funtores, ex, computador(dono(nome(Fernandes, Frederico)))
• predicado setof(X,Condição(X),ListaResultado) para conjuntos como
listas, sem semântica declarativa na lógica da 1a ordem

RelationLog: extensão de Datalog com
• definição e acesso a tuplas aninhadas
• definição de conjuntos:


em extensão (semântica de igualdade via enumeração)
parcialmente (semântica de inclusão)
• agrupamento de elementos de conjuntos, mesmo em regras diferentes
e recursivas
• semântica declarativa na lógica da 1a ordem
RelationLog: tuplas aninhadas
e conjuntos enumerados

Operadores:
• [] para tuplas aninhadas,
• {} para definição em extensão de
conjuntos
• <> para agrupamento em conjuntos
especificado apenas por inclusão

Exemplo:
Dept
Name
cpsc
Employee
Areas
bob
joe
Representação:
dept_employees(cpsc,{[bob,{db,ai}],
[joe,{os,pl,db}]})
dept_employees(math,{[sam,{gt,cm,si}],
[tom,{ca}]})
Consulta:
? - dept_employee(cpsc,<[X,<db>]>)
? - dept_employee(_,<[_,<ai>]>)
math
sam
tom
Resposta:X = {bob, joe}
Resposta: yes
db
ai
os
pl
db
gt
cm
si
ca
RelationLog: conjuntos com recursão
BDD RelationalLog sobre família:
fatherof(bob,tom)
motherof(bob,pam)
fatherof(pam,john)
motherof(john,becky)
parentsof(X,<Y>) :- fatherof(X,Y).
parentsof(X,<Y>) :- motherof(X,Y).
ancestorof(X,<Y>) :- parentsof(X,<Y>)
ancestorof(X,<Y>) :- parentsof(X,<Z>),
ancestorsof(Z,<Y>)
Consultas:
? - parentsof(bob,P).
P = {pam, tom}.
? - ancestorsof(bob,A).
A = {becky, john, tom, pam}
RelationLog e predecessores
(LDL, COL, Hilog) não
funcionam com valores nulos.
BD dedutivos: atualizações declarativas
Transaction Logic: atualizações e transações em
linguagem dedutiva com semântica formal declarativa
bem definida
 operadores del:, ins: e conjunção serializada

? - del : employee(joe,toy,10K), ins : employee(joe,shoe,10K)
? - del : employee(joe,toy,Sal)
ins : employee(joe,shoe,Sal)
hire(Name, Dept, Sal) :- ins : employee(Name, Dept, Sal)
avg_sal(Dept, Avg)
Avg <= 50K.
Integração BDA / BDD:
Questões
Como suportar eventos em um processamento de regras
dedutivas ?
 Como suportar transição de estado em um processamento
de regras dedutiva ?
 Como suportar interação com o gerenciamento de
transação em um processamento de regra dedutiva ?
 Como suportar uma visão baseada em lógica de um BD
com processamento de regra ativa ?

Integração BDA / BDD: abordagens
Estender BDA com dedução
 Estender BDD com ações
 Problema: semântica formal e segurança das ações
 “loose-coupling” usando histórias de eventos

• Eventos declarados com regras dedutivas. A detecção do evento
tem uma semântica lógica;
• Estados do BD guardados em relação ao tempo. Em cima deles
podem ser escritas regras dedutivas;
• Os eventos causado pela execução do componente ação em uma
regra ativa precisa apenas ser adicionada no fim;