Banco de Dados DedutivosEduardo J Marcondes

Marcelo Brischke

Banco de Dados Dedutivos • Área de intersecção entre banco de dados,

lógica e inteligência artificial.• Capacidade de definir (deduzir) regras a

partir de fatos armazenados em sua base de dados.

BD Dedutivo X BD inteligente• Inteligentes

– Geralmente assumem que os dados requeridos estão na memória principal.

– Os dados geralmente são extraídos por aplicações inteligentes.

• Dedutivos– Preparados para trabalhar com memória

secundária.– Conhecimento é inerente aos dados.

BDs Dedutivos• Linguagem Declarativa;• Mecanismo de inferência;• Regras e fatos;• Prolog e Datalog;• DOOD´s (Dedutive Oriented Object Database).

Notação Prolog / Datalog• Baseada em predicados com argumentos;

– Ex.: supervise(franklin,john)

Exemplo• Facts• supervise(franklin,john).• supervise(franklin,ramesh).• supervise(franklin,joyce).• supervise(franklin,alicia). • supervise(jennifer,ahmad).• supervise(jennifer,franklin).• supervise(jennifer,jennifer).• ... • Rules• superior(X,Y):-supervise(X,Y).• superior(X,Y):-supervise(X,Y),superior(Z,Y).• subordinate(X,Y):-superior(Y,X).• Queries• superior(james,Y)?• superior(james,joyce)?

james

franklin jennifer

john ramesh joyce alicia ahmad

Regra• superior(X,Y):-supervise(X,Z),superior(Z,Y)

Notação Datalog• atomic formulas;• literais da forma p(a1,a2,a3,...,an);• Aridade;• Predicados embutidos:

– Predicados de comparação binária: • <(less), <=(less_or_equal), >(greater), >=

(greater_or_equal) ;– Predicados de comparação:

• =(equal), /=(not_equal).

Interpretação de Regras• Prova - teórica;• Modelo-teórico;• Implementações um modelo intermediário.

Prova - teórica1. superior(x,y):- supervise(x,y) (regra 1)

2. superior(x,y):- supervise(x,z),superior(z,y) (regra 2)

3. supervise (Jennifer,ahmad) (axioma fundamental)

4. supervise(james,jennifer) (axioma fundamental)

5. superior(jennifer,ahmad) (aplicando a regra 1 em 3)

6. superior(james,ahmad) (aplicando a regra 2 em 4 e 5)

Modelo - teórico• Regras:

– Superior(x,y):-supervise(x,y)– Superior(x,y):-supervise(x,z),superior(z,y)

• Interpretação:• Fatos Conhecidos:

– Supervise(franklin,john) é verdadeiro– Supervise(franklin,ramesh) é verdadeiro– Supervise(franklin,joyce) é verdadeiro– Supervise(jennifer,alicia) é verdadeiro– Supervise(jennifer,ahmad) é verdadeiro– Supervise(james,franklin) é verdadeiro– Supervise(james,jennifer) é verdadeiro– Supervise(x,y) é falso para todas as outras possíveis combinações (x,y)

• Fatos Derivados:– Superior(franklin,john) é verdadeiro– Superior(franklin,ramesh) é verdadeiro– Superior(franklin,joyce) é verdadeiro– Superior(jennifer,alicia) é verdadeiro– Superior(jennifer,ahmad) é verdadeiro– Superior(james,franklin) é verdadeiro– Superior(james,jennifer) é verdadeiro– Superior(james,john) é verdadeiro– Superior(james,ramesh) é verdadeiro– Superior(james,joyce) é verdadeiro– Superior(james,alicia) é verdadeiro– Superior(james,ahmad) é verdadeiro– Superior(x,y) é falso para todas as outras possíveis combinações (x,y)

Mecanismos de Inferência Básicos para programas lógicos

• Button – up (forward chaining)– O motor de inferência inicia com os fatos e

aplica as regras para gerar novos fatos.• Top – Down (backward chaining)

– Inicia com o objetivo do predicado da query e busca os fatos coincidentes com as variáveis no banco de dados.

Programas Datalog e suas avaliações

• Fato-definidos (ou relações);• Regras-definidas (ou visões).

Segurança dos programas• Um programa ou uma regra é seguro se gerar

um grupo finito de fatos.

• Big_salary(Y) :- Y>60000

• Big_salary(Y) :- employee(X), salary(X,Y), Y>60000

• Big_salary(Y) :- Y>60000, employee(X), salary(X,Y)

Uso das Operações Relacionais• Baseado no modelo relacional;• Assume que os predicados( relações de

fatos e resultados de query) especificam grupos de tuplas;

• O poder adicional está nas queries recursivas e visões baseadas em queries recursivas.

Avaliação de Queries Não-Recursivas Datalog

• É realizada uma tradução da consulta Query para uma expressão relacional.

• Algoritmo de avaliação.

Conceitos de Queries Recursivas em Datalog

• Técnica da avaliação pura: Criando um plano de avaliação de query para produzir a resposta para a query.

• Técnica da regra reescrita: Otimiza o plano para uma estratégia mais eficiente.

Conceitos de Queries Recursivas em Datalog

• linearmente recursiva;– Sg(X,Y) :-parent(X,XP), parent(Y,YP), sg(XP,YP)

• linearmente recursiva à direita.• linearmente recursiva à esquerda.

– Direita: ancestor(X,Y):- parent(Z,Y), ancestor(X,Z)– Esquerda: ancestor(X,Y):- ancestor(X,Z),parent(Z,Y)

Conceitos de Queries Recursivas em Datalog

• Estratégia ingênua– É um método iterativo, onde para cada iteração

todas as regras são aplicadas para todo o grupo de tuplas, gerando assim todas as implícitas tuplas.

• Estratégia Semi-Ingênua– Em cada iteração ao invés de gerar todas as

possíveis tuplas, são geradas apenas as que ainda não existem.

Estratégia Maravilhosa• Não usa a relação inteira correspondente ao

predicado intencional mas sim um pequeno grupo desta relação.

• Ex.:– sg(X,Y) :- flat(X,Y).– sg(X,Y) :- up(X,U), sg(U,V), down(V,Y).

Query: sg(jonh, Z)

Estratégia Maravilhosa• top-down

– Não pesquisa caminhos irrelevantes.– Difícil de implementar (looping infinito)

• bottom-up– Pesquisa caminhos irrelevantes.

• A estratégia maravilhosa une o melhor dos dois métodos.

Técnica Maravilhosa• A técnica foca o objetivo inerente ao método top-down sem

os problemas de looping infinito, fácil término do teste e avaliação eficiente do bottom-up.

Sg(X,Y) :- magic - sg(X,Y), flat(X,Y).Sg(X,Y) :- magic- sg(X,Y), up(X,Y), sg(X,Y), down(X,Y).Magic-sg(U) :- magic-sg(X), up(X,U).Magic-sg(john).

Negação Estratificada • modelo mínimo• Ex.:

– p(a) :- not p(b)– tem dois mínimos modelos: {p(a)} e {p(b)}

• Um programa é estratificado se não houver recursão junto com a negação.

Negação Estratificadar1 : ancestor(X,Y) :- parent(X,Y).r2 : ancestor(X,Y) :- parente(X,Z), ancestor(Z,Y).r3 : nocyc(X,Y) :- ancestor(X,Y), not (ancestor(Y,X)).

Negação Estratificada• Negação localmente estratificada:

– Um programa P é localmente estratificado se para um determinado banco de dados, quando forem substituídas suas variáveis em todos os possíveis caminhos, o resultado não contenha recursão junto com negação.

Sistemas de Banco de Dados Dedutivos

• Sistema LDL• NAIL!• Coral

O Sistema LDL• Logic Data Language (LDL) é um projeto da

Microelectronics and Computer Technolology Corporation (MCC)

• Objetivos:– Desenvolver um sistema que estende o modelo

relacional mas explora algumas características do RDBMS;

– Aumentar a funcionalidade de um DBMS para que além de sua funcionalidade dedutiva ele suporte também aplicações de propósito gerais.

• Tenta combinar a capacidade do Prolog com a funcionalidade dos DBMS de uso geral.

NAIL!• NAIL! (Not Another Implementation of Logic!) é um projeto

iniciado pela Universidade de Stanford em 1985 ;• Objetivo inicial era o estudo de otimizações da lógica usada

em sistemas orientados a banco de dados, para suportar otimizações de execução do Datalog sobre RDBMS;

• Em colaboração com o grupo MCC foi responsável por:– Grupos maravilhosos;– Primeiro trabalho em recursão regular;– Lida com negação e agregação em regras lógicas;– Negação bem fundamentadas e negações estratificadas modulares.

Coral• Desenvolvido pela Universidade de Wisconsin at Madison;• Baseado no LDL;• Pode ser visto como uma linguagem de programação para

banco de dados que combina importantes características de SQL e Prolog;

• Coral implementa um grande número de otimizações:– Templates maravilhosos para queries recursivas;– Ativações de projeções;– Ativações especiais para programas lineares;– Boa interface com C++;– Extremamente extensível.

• Uma característica interessante é o pacote de extensão, que permite ao usuário examinar graficamente como um fato é gerado.

Aplicações de Banco de Dados Dedutivos Comerciais

• Alguns exemplos de domínios de aplicações comerciais / industriais baseadas no banco de dados dedutivo LDL:– Modelagem empresarial: sistema que modela estrutura, processos e

restrições organizacionais que gera como resultado um modelo ER. Utilizado para o Design de novas aplicações.

– Teste de hipóteses e mineração de dados: este domínio envolve a formulação de hipóteses traduzidas em regras LDL. Esse sistema foi aplicado na análise de dados do genoma.

– Reuso de software: Obtém dados de códigos de módulos em C usados em sistemas e utiliza regras que podem exportar e importar funções para reaproveitamento de software.

Referências Bibliográficas• ELMASR, Ramez; NAVATHE, Shamkant B.;

1996. Fundamentals of Database Systems. 3. Ed. Reading : Addison Wesley.

• MELO, Rubens Nascimento; 1988. Bancos de Dados não convencionais: a tecnologia de BD e suas novas áreas de aplicação. Campinas - SP : UNICAMP, IMEC.

FIM!