P-Datalog - Universidade Federal de Uberlândia

Transcrição

Mônica Sakuray Pais
P-Datalog¬: uma linguagem dedutiva para consultas a banco de
dados com inconsistências
Faculdade de Computação
Universidade Federal de Uberlândia
2004
Ficha Catalográfica
1. Folha de rosto:
Autor:
Orientador:
Nome do curso:
Local e ano de publicação:
Sandra Aparecida de Amo
Pós-Graduação da Faculdade de Computação - UFU
Uberlândia-MG 2004
2. Introdução:
Uma abordagem paraconsistente na integração de banco de dados permite que dados inconsistentes sejam identificados e mantidos, e ainda assim seja possı́vel deduzir informações consistentes. Isto é, a presença de inconsistência não invalida
todo o banco de dados como no enfoque clássico, mas somente uma parte dele: a
que contém a inconsistência. Além disto, partimos do pressuposto que a presença
de uma informação identificada como inconsistente é mais significativa do que a
sua ausência por completo do banco de dados. Nesta dissertação é proposta uma
linguagem dedutiva de consultas a banco de dados contendo inconsistências denominada P-Datalog¬ . A semântica declarativa de P-Datalog¬ é uma extensão da
semântica bem-fundada de Datalog¬ . A lógica base para a semântica de P-Datalog¬
é a lógica paraconsistente 3-valorada LFI1. Um método de avaliação bottom-up para
programas P-Datalog¬ baseado em um operador de ponto fixo alternante, e a sua
implementação, são apresentados nesta dissertação.
3. Sumário:
1. Introdução; 2. Fundamentos Teóricos; 3. Trabalhos Relacionados; 4. PDatalog¬ ; 5. Método de avaliação bottom-up; 6. Conclusão e trabalhos futuros;
Apêndice A: Listagem da implementação.
4. Palavras chaves:
Linguagem de consultas a banco de dados; Banco de dados dedutivos; Programação
em lógica; Informação inconsistente; Paraconsistência.
5. Número total de páginas:
140 páginas.
6. email:
[email protected].
7. Telefone fixo para contato:
(64) 461-2483.
i
P-Datalog¬: uma linguagem dedutiva para consultas a banco de
dados com inconsistências
Dissertação apresentada à Universidade Federal
de Uberlândia, Minas Gerais, como parte dos
requisitos exigidos para obtenção do tı́tulo de
Mestre em Ciência da Computação.
c
°Todos
os direitos resevados
ii
UNIVERSIDADE FEDERAL DE UBERLÂNDIA
FACULDADE DE COMPUTAÇÃO
Os abaixo assinados, por meio deste, certificam que leram e recomendam para a Faculdade de Computação a aceitação da dissertação intitulada
“P-Datalog¬ : uma linguagem dedutiva para consultas a banco de
dados com inconsistências” por Mônica Sakuray Pais como parte dos
requisitos exigidos para a obtenção do tı́tulo de Mestre em Ciência da
Computação.
Uberlândia, 11 de Agosto de 2004
Orientador:
Profa . Dra . Sandra de Amo
Universidade Federal de Uberlândia UFU/MG
Banca Examinadora:
Prof. Dr. Sergio Lifschitz
Pontifı́cia Universidade Católica do Rio de Janeiro/RJ
Prof. Dr. João Nunes de Souza
Universidade Federal de Uberlândia UFU/MG
iii
UNIVERSIDADE FEDERAL DE UBERLÂNDIA
Data: 11 de Agosto de 2004
Autor:
Tı́tulo:
P-Datalog¬ : uma linguagem dedutiva para
consultas a banco de dados com inconsistências
Faculdade: Faculdade de Computação
Grau: Mestre
Convocação: Agosto
Ano: 2004
A Universidade Federal de Uberlândia possui permissão para distribuir e ter cópias
desse documento para propósitos exclusivamente acadêmicos, desde que a autoria seja
devidamente divulgada.
Autor
O AUTOR RESERVA OS DIREITOS DE PUBLICAÇÃO, E ESSE DOCUMENTO
NÃO PODE SER IMPRESSO OU REPRODUZIDO DE OUTRA FORMA, SEJA NA
TOTALIDADE OU EM PARTES SEM A PERMISSÃO ESCRITA DO AUTOR.
iv
Ao meu marido, José Carlos, que sempre me
incentivou e me apoiou em todos os sentidos, e
aos nossos filhos, João e Carlos, que cresceram
junto com o desenvolvimento deste trabalho.
v
Agradecimentos
Agradeço à minha orientadora Sandra, pela paciência, compreensão e incentivo.
Ao meu marido, José Carlos, que sempre fez tudo o que fosse possı́vel para suprir
a minha ausência junto aos meus filhos, e nos momentos mais difı́ceis nunca me deixou
desistir.
Ao João e Carlos, nossos filhos, que sempre estiveram em primeiro lugar, apesar dos
perı́odos em que eu estive ausente, e me motivaram a me desdobrar para conseguir finalizar
este trabalho.
A toda a minha familia que sempre me incentivou, me apoiou e compreendeu a minha
ausência.
À Simone, Decina e Simone, que me ajudaram a manter a minha casa funcionando e
a cuidar da minha famı́lia.
À coordenação do programa de Pós-graduação da FACOM-UFU e aos meus colegas
de mestrado. Em especial ao Daniel, que sempre respondeu prontamente a todo pedido
de ajuda, e pela sua contribuição na implementação de P-Datalog¬ . À Reane e Michel,
meus consultores informais. Ao Paulo e Lacordaire, companheiros de inúmeras viagens a
Uberlândia. À Marcela pela ajuda na revisão do texto.
Aos meus colegas de trabalho e da direção da CEFET-Urutaı́-Go, em especial ao
Eliézer que foi o primeiro a acreditar que esse mestrado seria possı́vel, e ao prof. Campos
viabilizou a minha entrada no programa de mestrado inter-institucional da CAPES.
Ao programa de mestrado inter-institucional da CAPES que financiou o desenvolvimento deste trabalho.
vi
Resumo
Possibilidades de ocorrência de inconsistências no banco de dados surgem ao integrarmos dados provenientes de diferentes fontes. Uma abordagem paraconsistente na
integração de banco de dados permite que dados inconsistentes sejam identificados e mantidos, e ainda assim seja possı́vel deduzir informações consistentes. Isto é, a presença de
inconsistência não invalida todo o banco de dados como no enfoque clássico, mas somente
uma parte dele: a que contém a inconsistência. Além disto, partimos do pressuposto
que a presença de uma informação identificada como inconsistente é mais significativa
do que a sua ausência por completo do banco de dados. Nesta dissertação é proposta
uma linguagem dedutiva de consultas a banco de dados contendo inconsistências denominada P-Datalog¬ . A semântica declarativa de P-Datalog¬ é uma extensão da semântica
bem-fundada de Datalog¬ . A lógica base para a semântica de P-Datalog¬ é também uma
extensão da lógica paraconsistente 3-valorada LFI1. Um método de avaliação bottom-up
para programas P-Datalog¬ baseado em um operador de ponto fixo alternante, e a sua
implementação, são apresentados nesta dissertação.
vii
Abstract
We are faced with the possibility of inconsistency in databases when integrating data
coming from multiple different sources. A paraconsistent approach for database integration allows keeping inconsistent information and reasoning in its presence. In this paper,
we use an extension of a paraconsistent logic (LFI1) as the underlying logic for the specification of P-Datalog¬ , a deductive query language for databases containing inconsistent
information. We present a declarative semantics which captures the desired meaning of
a recursive query executed over a database containing inconsistent facts and whose rules
allow infering information from inconsistent premises. This semantics is a natural extension of the well-founded semantics of Datalog¬ . We also present a bottom-up evaluation
method for P-Datalog¬ programs based on an alternating fixpoint operator and discussion
on implementation issues.
Sumário
1 Introdução
2
2 Fundamentos Teóricos
2.1 Conceitos algébricos . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Ordem Parcial . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Reticulados . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 Operadores . . . . . . . . . . . . . . . . . . . . . . .
2.1.4 Ponto Fixo . . . . . . . . . . . . . . . . . . . . . . .
2.2 Classificação de programas na programação em lógica . . . .
2.3 Lógica LFI1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Datalog sem negação . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Teoria da prova . . . . . . . . . . . . . . . . . . . . .
2.4.2 Teoria de modelos . . . . . . . . . . . . . . . . . . . .
2.4.3 Teoria do Ponto Fixo . . . . . . . . . . . . . . . . . .
2.4.4 Métodos de avaliação de Datalog . . . . . . . . . . .
2.5 Datalog¬ - Datalog com negação . . . . . . . . . . . . . . . .
2.5.1 A negação e suas implicações semânticas . . . . . . .
2.5.2 Semântica de modelo estável . . . . . . . . . . . . . .
2.5.3 Semântica bem-fundada . . . . . . . . . . . . . . . .
2.5.4 Ponto fixo Reincidente para Semântica bem-fundada
2.5.5 Ponto fixo Alternante para Semântica bem-fundada .
2.6 Conclusão do capı́tulo . . . . . . . . . . . . . . . . . . . . .
3 Trabalhos Relacionados
3.1 Inconsistência na programação em lógica . . . . . . .
3.1.1 Semântica 4-valorada de programa lógico geral
3.2 Inconsistência na integração de fontes de dados . . .
3.2.1 Abordagem da revisão de crença na integração
3.2.2 Abordagem paraconsistente na integração . .
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
6
8
8
11
12
13
15
18
19
22
25
26
27
29
32
39
41
46
.
.
.
.
.
47
47
48
55
55
60
SUMÁRIO
ix
4 P-Datalog¬
4.1 Sintaxe P-Datalog¬ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Modelos de programas P-Datalog¬ . . . . . . . . . . . . . . . . . . . .
4.2.1 Lógica 4-valorada 4-LFI1: a lógica base de P-Datalog¬ . . . . .
4.2.2 Modelos 4-valorados . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Programas P-Datalog¬ Estendidos . . . . . . . . . . . . . . . . . . . . .
4.3.1 Operador de consequência imediata 4-TP . . . . . . . . . . . . .
4.3.2 Semântica do ponto fixo para programas P-Datalog¬ estendidos
4.4 Modelos 4-estáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Semântica bem-fundada de P-Datalog¬ . . . . . . . . . . . . . . . . . .
5 Método de avaliação bottom-up
5.1 Algoritmo do ponto fixo alternante . . . . . . . . . . . .
5.1.1 Sequência alternante . . . . . . . . . . . . . . . .
5.1.2 Instâncias I∗ , I∗ e I∗∗ . . . . . . . . . . . . . . . .
5.1.3 Cálculo da semântica bem-fundada de P-Datalog¬
5.2 Resultados Comparativos . . . . . . . . . . . . . . . . . .
5.3 Implementação do provador P-Datalog¬ . . . . . . . . . .
5.3.1 A linguagem de programação OCaml . . . . . . .
5.3.2 Provador P-Datalog¬ . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
69
70
70
71
75
76
78
81
83
.
.
.
.
.
.
.
.
85
85
85
90
92
100
102
102
103
6 Conclusão e trabalhos futuros
106
A Listagem da implementação do provador P-Datalog¬
112
Lista de Figuras
1.1
Evolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
Matrizes dos conectivos de LFI1 . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1
Lógica 4-valorada FOUR . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1
4.2
4.3
Lógica 4-valorada 4-LFI1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Sı́mbolos associados a um átomo A em P-Datalog¬ . . . . . . . . . . . . . 72
Matrizes dos conectivos de 4-LFI1 . . . . . . . . . . . . . . . . . . . . . . . 73
6.1
Matriz dos valores-verdade associados aos literais •A e ◦A . . . . . . . . . 106
1
3
Capı́tulo 1
Introdução
Informações contraditórias em um sistema de banco de dados tradicional normalmente
não são permitidas, e nem armazenadas, devido a um controle preventivo executado pelo
gerenciador do banco de dados. Com o desenvolvimento das tecnologias de rede, surgiram
os bancos de dados distribuı́dos, onde as informações são acessadas e atualizadas por
diversas fontes. Banco de dados locais possuem suas próprias restrições de integridade,
e são livres de contradições. Porém, dois bancos de dados locais podem ser mutamente
contraditórios, o que acarreta em procedimentos complexos e de alto custo para restaurar
e manter a consistência do banco de dados no nı́vel global.
Entretanto, existem situações em que a presença de uma informação inconsistente é
mais significativa do que sua ausência por completo do banco de dados. Ou seja, um banco
de dados onde é possı́vel armazenar informações seguras e também informações controversas, é uma representação mais próxima do mundo real onde os conflitos e incertezas
estão presentes. Segundo Gabbay [GH91], as inconsistências não são necessariamente algo
“ruim”. Elas fazem parte do mundo real e podem direcionar para uma ação mais correta
do que simplesmente a sua eliminação. Uma inconsistência pode ser um indicador da
necessidade de que uma ação externa ao banco de dados seja tomada, como por exemplo,
que o usuário seja consultado, ou que as restrições de integridade sejam revistas.
As instâncias de um banco de dados consistente podem ser representadas através da
lógica clássica 2-valorada. Uma tupla instanciada de uma dada relação é um fato positivo.
Um fato negativo representa uma tupla instanciada que não está armazenada. A lógica
clássica 2-valorada verifica o “princı́pio da explosão” onde temos que {A, ¬A} ` B, para
toda fórmula B. Assim a presença de fatos inconsistentes (A e ¬A) numa teoria torna-a
trivial, ou seja, é possı́vel deduzir qualquer coisa desta teoria, inutilizando-a em termos
de informação.
Quando consideramos que o banco de dados pode conter informações armazenadas
como controversas, a lógica 2-valorada já não é suficiente para representar uma instância
deste banco de dados. É necessário um terceiro valor-verdade, o valor inconsistente, para
2
CAPÍTULO 1. INTRODUÇÃO
3
P-Datalog¬
Datalog¬
Datalog
Figura 1.1: Evolução
ser associado aos fatos controversos, ou seja, uma lógica 3-valorada.
Em [dACM00, dACM02] foi introduzida a lógica paraconsistente 3-valorada LFI1 como
base de um modelo de integração de banco de dados. Lógicas paraconsistentes são aquelas
em que o princı́pio da explosão não é verificado, isto é, a presença de fatos inconsistentes
não acarreta que qualquer coisa possa ser inferida. No artigo [dACM00] são discutidas algumas questões inerentes à paraconsistência através da proposta de um modelo de
banco de dados baseado em um tratamento axiomático das propriedades básicas da informação inconsistente. A partir de propriedades semânticas que seriam desejáveis para
um tratamento bem-fundado dos dados inconsistentes, chegou-se à lógica LFI1- Logic
of Formal Inconsistency, onde as inconsistências são localizadas e indicadas ao invés de
serem descartadas. Em [dACM02] é apresentado um método baseado na lógica LFI1 que
executa a integração de fontes de dados heterogêneas e resulta em um banco de dados
paraconsistente, onde as informações inconsistentes são identificadas e mantidas no banco
de dados.
Dentre as linguagens de consultas a banco de dados temos Datalog, uma linguagem
declarativa capaz de expressar a recursividade, mas incapaz de expressar a diferença
relacional. A sua extensão, a linguagem Datalog¬ , completou a expressividade de Datalog
com a inclusão de literais negativos somente no corpo de suas regras, onde a negação
utilizada é a negação por default. Porém o Datalog¬ é uma linguagem de consultas a
banco de dados consistentes. É necessário então, definir uma linguagem de consultas
a banco de dados com inconsistências, uma linguagem com grande poder de expressão
como Datalog¬ , e que seja capaz de raciocinar na presença da inconsistência, ou seja,
um Datalog¬ paraconsistente. Denotamos esta linguagem de P-Datalog¬ . A Figura 1.1
mostra que P-Datalog¬ captura Datalog¬ e Datalog. É importante ressaltar que apesar da
linguagem P-Datalog¬ , não permitir literais negativos na cabeça das regras, as instâncias
do banco de dados contém inconsistências, e portanto a semântica de P-Datalog¬ também
deve ser capaz de raciocinar na presença da inconsistência.
Os conceitos de contradição e inconsistência não são necessariamente iguais. Porém,
ao longo deste texto, identificaremos inconsistência com contradição; ou seja, um fato A
é inconsistente quando existe evidência a favor de A e também existe evidência contrária
4
a A.
Exemplo 1.0.1 (Motivação) Suponha que existe a seguinte regra em um concurso
público fictı́cio para contratação de servidores: “se o candidato não possui dı́vidas com
o imposto de renda, e existe evidência de que o candidato é indicado por uma pessoa
influente que não é funcionário público, então o candidato pode conseguir o cargo”.
Podemos traduzir esta regra em um programa P-Datalog¬ Pcargo :
cargo(x) ← ∼devedor(x), indicadoPor(x,y), ∼cargo(y)
O sı́mbolo ∼ representa a negação por default, e os literais ∼ devedor(x) e ∼ cargo(y)
representam informação negativa segura: o fato que x não possui registro de dı́vidas na
Receita Federal e que y não é um funcionário público. Por outro lado, o literal indicadoPor(x,y) representa uma informação que não é totalmente segura. Ele apenas garante que
existe registro de que x é indicado por y, porém essa informação pode ser controversa.
Suponha que temos os seguintes fatos armazenados no banco de dados:
I
= {◦ indicadoPor(charles,joseph), ◦ indicadoPor(joseph,charles),
◦ indicadoPor(paul,james), • indicadoPor(john,kevin),
◦ indicadoPor(james,kevin), ◦ devedor(james)}
Os sı́mbolos ◦ e • que acompanham cada fato significam que o fato é seguro e controverso, respectivamente. Seja o seguinte modelo 4-valorado J de Pcargo que inclui os fatos
de I, ou seja, J concorda com I sobre os valores dos átomos devedor e indicadoPor. Como
veremos mais tarde, J é de fato a semântica bem-fundada do programa Pcargo e instância
inicial I. Os valores dos átomos cargo na instância J são descritos a seguir:
verdadeiro
falso
cargo(paul)
cargo(kevin), cargo(james)
inconsistente
indefinido
cargo(john)
cargo(charles), cargo(joseph)
Este modelo afirma que James certamente não obtém o cargo. James possui dı́vidas
com a Receita Federal, e este resultado favorece Paul a vencer o concurso. Paul não deve
imposto de renda e é indicado por James, que não é funcionário público.
Já no caso de John, ele está em dia com a Receita Federal mas é contraditório que
ele seja indicado por Kevin, que também não é funcionário público. Kevin também não
passa no concurso porque ele não é indicado por ninguém. Desta forma, é controverso
que John consiga o cargo.
Por outro lado, é indefinido se Charles e Joseph vão conseguir o cargo. Eles preenchem
quase todos os requisitos: eles não devem imposto de renda, eles possuem a indicação de
uma pessoa influente mas para obter o cargo eles dependem um do outro: Charles indica
Joseph e Joseph indica Charles. Logo Charles consegue o cargo se Joseph não conseguir
e vice-versa.
5
Contribuição da dissertação. Esta dissertação apresenta a definição da linguagem
dedutiva P-Datalog¬ para consultas a banco de dados em que podem existir fatos identificados como inconsistentes armazenados. P-Datalog¬ é uma extensão natural da linguagem
Datalog¬ . O diferencial encontra-se na instância do banco de dados: para P-Datalog¬
as instâncias do banco de dados podem conter fatos verdadeiros, falsos e inconsistentes,
e o resultado de programas P-Datalog¬ pode conter além de fatos verdadeiros, falsos e
inconsistentes, fatos indefinidos cuja veracidade ou falsidade não pode ser comprovada.
A partir da semântica bem-fundada [Prz90] do Datalog¬ , é definida uma extensão
desta semântica para programas P-Datalog¬ , a qual é denominada semântica bem-fundada
P-Datalog¬ .
Uma vez definida a semântica bem-fundada P-Datalog¬ , um método de avaliação
bottom-up, baseado no algoritmo do ponto fixo alternante [Van89], é descrito. A implementação do algoritmo para a obtenção da semântica bem-fundada P-Datalog¬ foi feita
com o uso da linguagem de programação Objective Caml, e resultou em um provador
P-Datalog¬ .
A dissertação é concluı́da com propostas de melhorias e possı́veis trabalhos a serem
futuramente desenvolvidos.
Organização. Algumas definições teóricas são fundamentais para o desenvolvimento e
bom entendimento de nosso trabalho, e no capı́tulo 2 elas são descritas. Neste capı́tulo
são introduzidos conceitos algébricos importantes referentes aos fundamentos teóricos de
Datalog¬ e sua semântica bem-fundada. Também são descritas a sintaxe e semântica
da lógica paraconsistente LFI1. No capı́tulo 3 são apresentados alguns trabalhos onde
são propostos enfoques que permitem o tratamento de informação inconsistente, tanto no
contexto de programação em lógica quanto no contexto de integração de dados.
A descrição do trabalho desenvolvido nessa dissertação se inicia no capı́tulo 4 com a
definição da linguagem lógica de consultas P-Datalog¬ e a sua semântica bem-fundada
4-valorada. A seguir, no capı́tulo 5, é descrito o método de avaliação bottom-up com a
apresentação de um algoritmo baseado no algoritmo do ponto fixo alternante e a implementação do algoritmo que resultou em um provador P-Datalog¬ . Resultados comparativos são mostrados e analisados. No anexo encontra-se a listagem da implementação.
No capı́tulo 6 é apresentada a conclusão da dissertação e a apresentação de propostas
para a extensão de P-Datalog¬ como trabalhos a serem realizados futuramente.
Capı́tulo 2
Fundamentos Teóricos
A definição da linguagem de consulta P-Datalog¬ faz uso de conceitos teóricos relacionados
com a programação em lógica e a sua semântica. A programação em lógica baseiase em fundamentos algébricos que são descritos sucintamente na primeira seção deste
capı́tulo. Na seção seguinte, seção 2.2, são classificados os programas dentro do contexto
da programação em lógica.
Na seção 2.3 é descrita a lógica paraconsistente LFI1, que será utilizada na definição
de P-Datalog¬ no capı́tulo 4.
A linguagem de consultas Datalog, sua sintaxe e suas diferentes abordagens semânticas
são descritas na seção 2.4. Em seguida, na seção 2.5, é introduzida uma extensão da
linguagem Datalog, o Datalog¬ e sua semântica bem-fundada, juntamente com métodos
construtivos para obtenção desta semântica bem-fundada.
Os fundamentos da lógica clássica utilizados neste texto, podem ser encontrados em
[Fit96] e em [NS97]. Um texto introdutório e mais acessı́vel, é apresentado em [Sou02].
2.1
Conceitos algébricos
Nesta seção apresentamos alguns conceitos algébricos importantes na fundamentação
teórica da programação em lógica. Maiores detalhes podem ser encontrados em [Llo93].
2.1.1
Ordem Parcial
Seja S um conjunto. Uma relação R sobre S é um subconjunto de S ×S. Isto é, R ⊆ S ×S.
Se (x, y) ∈ R, denotamos como xRy.
Definição 2.1.1 (Ordem Parcial) Uma relação R sobre S é uma ordem parcial se:
1. xRx, para todo x ∈ S (reflexiva).
2. Se xRy e yRx então x = y, para todo x, y ∈ S (anti-simétrica).
6
CAPÍTULO 2. FUNDAMENTOS TEÓRICOS
7
3. Se xRy e yRz então xRz, para todo x, y, z ∈ S (transitiva).
Exemplo 2.1.1 A relação de ordem 6 definida no conjunto dos números reais é uma
ordem parcial. Porém a relação < não é uma ordem parcial, pois não é reflexiva.
Exemplo 2.1.2 Seja S =P(U ) conjunto das partes de um conjunto U com a relação de
ordem A ⊆ B. É fácil verificar que é uma ordem parcial.
Vamos adotar uma notação padrão e utilizar 6 para denotar uma ordem parcial.
Um conjunto S munido de uma ordem parcial 6 é chamado de conjunto parcialmente
ordenado, e é denotado por (S, 6).
Definição 2.1.2 (Limitante inferior e superior) Seja (S, 6) um conjunto parcialmente
ordenado e X um subconjunto de S:
• a ∈ S é chamado de limitante superior de X se x 6 a para todo x ∈ X;
• b ∈ S é chamado de limitante inferior de X se b 6 x para todo x ∈ X;
Entre os limitantes superiores de um dado subconjunto X, existe o menor entre todos
os limitantes superiores. E, entre os limitantes inferiores existe o maior entre eles. A
seguir temos a definição destes elementos:
Definição 2.1.3 (Supremo e ı́nfimo) Seja (S, 6), um conjunto parcialmente ordenado,
e X um subconjunto de S:
1. Dizemos que a ∈ S é um supremo de X, se:
(a) a > x, para todo x ∈ X; e
(b) se b > x, para todo x ∈ X então a 6 b.
Denotamos a por sup(X), o menor limitante superior de X.
2. Dizemos que a ∈ S é um ı́nfimo de X, se:
(a) a 6 x, para todo x ∈ X; e
(b) se b 6 x, para todo x ∈ X então a > b.
Denotamos a por inf(X), o maior limitante inferior de X.
Exemplo 2.1.3 Seja S = P(U ), como no exemplo 2.1.2. Dado X ⊆ S, X = {xi |i ∈ I},
[
\
I ⊆ N, então sup(X) = xi e inf (X) = xi .
i∈I
i∈I
8
Proposição 2.1.1 ([Llo93]) Se existe sup(X), então ele é único. De modo similar, se
existe inf (X), então ele é único.
Observe que sup(X) e inf (X) podem não existir para todo subconjunto X de um
conjunto parcialmente ordenado S.
Exemplo 2.1.4 Seja S = (R, 6) e X = N. Não existe a ∈ R tal que a é sup(N), pois N
não é limitado superiormente.
2.1.2
Reticulados
Um conjunto parcialmente ordenado L é dito um reticulado se exitem sup e inf do
conjunto {x, y} para todo x, y ∈ L. É fácil mostrar que esta propriedade se estende aos
subconjuntos finitos {x1 , . . . , xn } quaisquer, isto é, num reticulado existem o sup e inf
de qualquer subconjunto finito {x1 , . . . , xn }.
O reticulado é dito completo, se existem sup e inf para todo subconjunto X (inclusive
os infinitos). O sup do reticulado completo L é denotado por >, e o inf por ⊥.
Exemplo 2.1.5 Seja S = P(U ), como no exemplo 2.1.2, S é um reticulado completo.
[
\
De fato, dado X ⊆ S, X = {xi |i ∈ I}, definimos sup(X) = xi e inf (X) = xi .
i∈I
i∈I
Exemplo 2.1.6 Seja S = R − N. Dados x, y ∈ S, temos que sup{x, y} = max{x, y} e
inf {x, y} = min{x, y}. Portanto, S é um reticulado.
Seja X ⊆ S e X = {x ∈ S|0 < x < 1}. O subconjunto X não possui sup nem inf . Logo,
S não é um reticulado completo.
2.1.3
Operadores
Definição 2.1.4 (Operador monotônico) Seja L um reticulado completo, e T : L →
L um operador. T é dito monotônico se sempre que x 6 y, então T (x) 6 T (y).
Exemplo 2.1.7 Seja Pf in (N) o conjunto das partes finitas de N. Dado X ⊆ Pf in (N),
[
\
onde X = {xi |i ∈ I}, definimos sup(X) =
xi e inf (X) =
xi , o que caracteriza o
i∈I
i∈I
conjunto Pf in (N) como um reticulado completo.
O operador T : Pf in (N) −→ Pf in (N) é definido da seguinte forma: T (x) = x ∪ x0 ,
onde x0 = {0}.
T é um operador monotônico. De fato, se x1 ⊆ x2 , então como T (x1 ) = x1 ∪ {0} e
T (x2 ) = x2 ∪ {0} temos T (x1 ) ⊆ T (x2 ).
9
Exemplo 2.1.8 Seja o seguinte operador T : Pf in (N) −→ Pf in (N) definido da seguinte
forma: T (x) = Pf in (N) − x.
T não é um operador monotônico. De fato, se x1 ⊂ x2 então como T (x1 ) = Pf in (N)−x1
e T (x2 ) = Pf in (N) − x2 , temos T (x1 ) 6⊂ T (x2 ).
Definição 2.1.5 (Subconjunto Direto) Seja L um reticulado completo, e X ⊆ L. X
é direto se todo subconjunto finito de X possui um limitante superior em X.
Exemplo 2.1.9 Seja o seguinte conjunto L = [0, 1]. O subconjunto X = [0, 1) é direto,
pois para todo X 0 ⊆ X, consideramos o elemento a, onde a é maior que todos os elementos
de X 0 . Como a ∈ X 0 então a ∈ X.
Exemplo 2.1.10 Seja o seguinte conjunto L = P(N), e X ⊆ L onde X = {{1}, {2}, {3}, ...}.
Seja X 0 ⊆ X, X 0 = {{1}, {2}}. Note que o limitante superior de X 0 é dado pelo conjunto
{1, 2} que não pertence a X. Portanto, X não é direto.
Exemplo 2.1.11 Seja o seguinte conjunto L = P(N), e X ⊆ L onde
X = {{1}, {3}, ..., {1, 3}, ..., {1, 3, 5}, ...}. Note que todo subconjunto finito de X possui
limitante superior em X. Portanto, X é direto.
Definição 2.1.6 (Operador contı́nuo) Seja L um reticulado completo e T : L → L
um operador. Se X ⊆ L e X = {x1 , x2 , ...}, denotamos por T (X) = {T (x1 ), T (x2 ), ...}. T
é dito contı́nuo se para todo X ⊆ L, X direto, temos T (sup(X)) = sup(T (X)).
Exemplo 2.1.12 Seja o conjunto L = P(N), e o operador T : L → L, onde T (x) =
x ∪ {0}. Suponha X ⊆ L, X = {xi |x ∈ I},onde X é direto.
X
x1
x2
...
xn
...
T (X)
x1 ∪ {0}
x2 ∪ {0}
...
xn ∪ {0}
...
S
S
Temos que sup(X) = xi e sup(T (X)) = xi ∪ {0}.
S
Aplicando-se T a sup(X) , temos T (sup(X)) = sup(X) ∪ {0} = xi ∪ {0}. Portanto,
sup(T (X)) = T (sup(X)).
Proposição 2.1.2 ([Llo93]) Se o operador T é contı́nuo, então T é monotônico.
10
Exemplo 2.1.13 Seja o operador contı́nuo T : L → L. Vamos mostrar que T é monotônico.
Sejam x, y ∈ L, e x 6 y. Vamos mostrar que T (x) 6 T (y).
Seja X = {x, y}. Os possı́veis subconjuntos finitos de X e seu respectivos limitantes
superiores são descritos a seguir:
X0 ⊆ X
X0 = ∅
X 0 = {x}
X 0 = {y}
X 0 = {x, y}
Limitante superior de X 0
x, y
x, y
y
y
Observe que x ∈ X é limitante superior de X 0 = ∅, pois a seguinte asserção é verdadeira: ∀a ∈ ∅, a 6 x.
Todos os subconjuntos finitos de X possuem limitante superior em X. Portanto, X é
direto. Temos que T (X) = {T (x), T (y)}. Como o operador T é contı́nuo e X é direto,
então T (sup(X)) = sup(T (X)). Sabemos que sup(X) = y, logo sup(T (X)) = T (y).
Logo T (x) 6 T (y), o que nos permite concluir que T é monotônico.
A recı́proca desta proposição não é verdadeira. Se o operador T é monotônico não
implica que T é contı́nuo, como comprova o seguinte exemplo:
Exemplo 2.1.14 Seja o conjunto L = [0, 1] e o operador T : L → L definido a seguir:
(
0 se x < 1
T (x) =
1 se x = 1
É fácil verificar que para todo x, y ∈ L, se x > y então T (x) > T (y). A seguir temos
todas as possibilidades de valores para x e y tal que x 6 y:
x
x<1
x<1
x=1
y
y<1
y=1
y=1
T (x) e T (y)
T (x) = T (y)
T (x) 6 T (y)
T (x) = T (y)
Portanto, o operador T é monotônico.
Vamos verificar se T também é contı́nuo. Seja o seguinte conjunto X ⊆ L, X =
{0, 12 , 34 , . . .}. X é um conjunto direto, pois todos subconjuntos finitos de X possuem
limitante superior em X. Note que o sup(X) = 1 e T (1) = 1 Aplicando-se o operador T
a cada um dos elementos de X, obtemos T (X) = {0, 0, 0, ...}, onde o sup(T (X)) = 0.
Concluı́mos que a propriedade T (sup(X)) = sup(T (X)) não é válida, pois 1 6= 0, e
portanto o operador T é monotônico e não é contı́nuo.
2.1.4
11
Ponto Fixo
A seguir são introduzidos conceitos e definições relativas à teoria do ponto fixo.
Definição 2.1.7 (Ponto fixo) Seja L um reticulado completo e T : L → L um operador. Dizemos que a ∈ L é um ponto fixo de T se T (a) = a.
Definição 2.1.8 (Menor ponto fixo) Seja L um reticulado completo e T : L → L um
operador. Dizemos que a ∈ L é o menor ponto fixo de T se:
1. a é um ponto fixo; e
2. para todo ponto fixo b de T , temos a 6 b.
Denotamos o menor ponto fixo de T por lf p(T ).
Exemplo 2.1.15 Seja Pf in (N) o conjunto das partes finitas de N.
O operador T : Pf in (N) −→ Pf in (N) é definido da seguinte forma: T (x) = x ∪ x0 ,
onde x0 = {0}.
Temos que T (x0 ) = x0 ∪ x0 = {0} = x0 . Logo x0 é ponto fixo de T e também o menor
ponto fixo de T .
Proposição 2.1.3 ([Llo93]) Seja L um reticulado completo e T : L → L um operador.
O menor ponto fixo de T , se existir, é único e lf p(T ) = inf {x ∈ L : T (x) = x}.
Proposição 2.1.4 ([Llo93]) Seja L um reticulado completo e T : L → L um operador
monotônico. Então o menor ponto fixo de T existe e lf p(T ) = inf {x ∈ L : T (x) 6 x}.
A seguir é descrito um método iterativo para o cálculo do menor ponto fixo.
Definição 2.1.9 Seja L um reticulado completo e T : L → L um operador monotônico.
Então, definimos a sequência T0 , T1 , . . . como sendo:
T0 = ⊥
T1 = T (T0 )
T2 = T (T1 )
...
Tn = T (Tn−1 )
...
onde ⊥ representa o conjunto vazio, e T ↑= sup{T0 , T1 , . . .}.
Repare que pelo fato de T ser monotônico, a sequência T0 , T1 . . . é crescente, isto é,
T0 ⊆ T1 ⊆ . . ..
De fato:
12
T0 ⊆ T1 , pois ⊥ ⊆ T1
T1 ⊆ T2 , pois T (⊥) ⊆ T (T1 )
T2 ⊆ T3 , pois T (T1 ) ⊆ T (T2 )
...
Temos que T ↑ é justamente o ponto fixo do operador T , no caso de T ser contı́nuo,
conforme é indicado pela proposição a seguir.
Proposição 2.1.5 ([Llo93]) Seja L um reticulado completo e T : L → L um operador
contı́nuo. Então, lf p(T ) = T ↑.
2.2
Classificação de programas na programação em
lógica
A programação em lógica possui diferentes tipos de programas que podem ser classificados
baseando-se na presença ou não dos sı́mbolos de negação no corpo e/ou na cabeça das regras; e no tipo de negação utilizada. A classificação apresentada a seguir, foi apresentada
em [Ari02], e ela não é seguida de maneira uniforme nos vários trabalhos pesquisados durante o desenvolvimento desta dissertação. Os programas aqui definidos como “programa
lógico padrão (standard)”, em alguns trabalhos aparecem definidos como “programa lógico
normal ”, apesar da negação utilizada ser a negação por default.
Nas definições serão utilizadas as seguintes notações:
1) p, q, r, p1 , p2 , . . . são fórmulas atômicas.
2) L, L1 , L2 , . . . são ¬literais, isto é, são átomos A ou átomos negados ¬A com a
negação explı́cita.
Definição 2.2.1 (Programa lógico definido(definite)) Um programa lógico definido
é um conjunto finito de regras do tipo: p ← p1 , . . . , pn . Os programas lógicos definidos
são positivos, ou seja, não possuem o sı́mbolo de negação nas suas regras.
Exemplo 2.2.1 (Programa lógico definido) O programa seguinte é um programa lógico
definido:
p ← q, r
q ← p, s
Definição 2.2.2 (Programa lógico padrão) Um programa lógico padrão é um conjunto finito de regras do tipo: p ← p1 , . . . , pm , ∼ pm+1 , . . . , ∼ pn .
Exemplo 2.2.2 (Programa lógico padrão) O programa seguinte é um programa lógico
padrão:
p ← q, ∼ r
q ←∼ p, s
13
Os programas P-Datalog¬ , como será definido no capı́tulo 4, são programas lógicos
padrões: a negação é a negação por default, e esta somente aparece no corpo das regras.
Definição 2.2.3 (Programa lógico normal) Um programa lógico normal é um conjunto finito de regras do tipo: p ← L1 , . . . , Ln .
Exemplo 2.2.3 (Programa lógico normal) O programa seguinte é um programa lógico
normal :
p ← q, ¬r
q ← ¬p, s
Note que a diferença entre um programa lógico padrão e um normal está apenas no
tipo de negação utilizada: nos programas padrões a negação é a negação por default.
Definição 2.2.4 (Programa lógico geral) Um programa lógico geral é um conjunto
finito de regras do tipo: L ← L1 , . . . , Ln .
Exemplo 2.2.4 (Programa lógico geral) O programa seguinte é um programa lógico
geral :
p ← q, ¬r
¬q ← ¬p, s
Definição 2.2.5 (Programa lógico estendido) Um programa lógico estendido é um
conjunto finito de regras do tipo: L ← L1 , . . . , Lm , ∼ Lm+1 , . . . , ∼ Ln .
Exemplo 2.2.5 (Programa lógico estendido) O programa seguinte é um programa
lógico estendido:
p ← q, ¬r, ∼ t
¬q ←∼ ¬p, s
2.3
Lógica LFI1
Nesta seção é descrita a sintaxe e a semântica da lógica LFI1 - Logic of Formal Inconsistency. Uma apresentação detalhada pode ser encontrada no artigo [dACM00].
Seja R uma assinatura1 finita sem sı́mbolos funcionais e Var um conjunto de sı́mbolos
de variáveis. As fórmulas da lógica LFI1 são definidas de modo usual como na lógica de
primeira ordem, com a adição de um novo sı́mbolo • (cujo significado é “é inconsistente”).
Uma fórmula de LFI1 é definida indutivamente pelas seguintes regras (e somente elas):
• Se R é um sı́mbolo de predicado de aridade k e x1 , ..., xk são constantes ou variáveis,
então R(x1 , ..., xk ) e x1 = x2 são fórmulas atômicas ou átomos. O primeiro é
chamado de átomo relacional e o último de átomo de igualdade.
1
Uma assinatura denota um alfabeto constituı́do por um conjunto finito de sı́mbolos de predicados,
constantes e funções.
∨
t
i
f
t
t
t
t
i
t
i
i
f
t
i
f
t
i
f
(a)
¬
f
i
t
•
f
t
f
∼
f
f
t
14
→
t
i
f
t
t
t
t
i
i
i
t
f
f
f
t
∧
t
i
f
t
t
i
f
i
i
i
f
f
f
f
f
(b)
Figura 2.1: Matrizes dos conectivos de LFI1
• Se F, G são fórmulas e x é uma variável, então F ∨ G, ¬F , ∀xF , ∃xF e •F são
fórmulas.
Sejam x uma variável e F uma fórmula que contém x. A ocorrência da variável x
em F é ligada se x pertence ao escopo de um quantificador (∀x) ou (∃x) em F . Caso
contrário, a ocorrência da variável x em F é livre. Se existe pelo menos uma ocorrência
ligada de x em F , então a variável x é ligada em F . Se existe pelo menos uma ocorrência
livre de x em F , então a variável x é livre em F [Sou02].
Se x1 , . . . , xn são variáveis livres da fórmula F e c1 , . . . , cn são constantes ou variáveis,
denotamos por F [c1 , . . . , cn /x1 , . . . , xn ] a fórmula obtida pela substituição de cada ocorrência
de uma variável xi por ci , para i = 1, . . . , n. Uma sentença é uma fórmula sem variáveis
livres. Um fato é um átomo relacional sem variáveis livres. Denotamos por F o conjunto
de fatos.
Em seguida vamos definir interpretações para fórmulas de LFI1.
É importante
destacar, que no contexto de banco de dados, somente são consideradas as interpretações
de Herbrand, aquelas para as quais Dom (o conjunto dos sı́mbolos de constantes da
linguagem) é o domı́nio de avaliação das variáveis, e onde cada sı́mbolo de constante é
interpretado por si mesmo. Desta forma, uma avaliação é uma aplicação v : Var →
Dom.
Definição 2.3.1 Seja R uma assinatura finita. Uma interpretação sobre R é uma
aplicação δ : F → {f (falso), t (verdadeiro), i (inconsistente)}.
Uma interpretação de fatos pode ser estendida para sentenças proposicionais de modo
natural usando-se as matrizes de conectivos da Figura 2.1 (a), onde o sı́mbolo ¬ representa
a negação clássica, e o sı́mbolo ∼ representa a negação por default.
O conectivo ∧ é definido pela correspondência: A ∧ B ≡ ¬(¬A ∨ ¬B). Já o conectivo
→ é definido pela correspondência: A → B ≡ B ∨ ¬(A ∨ •A). As matrizes para ∧ e →
são dadas pela Figura 2.1 (b).
A extensão de δ para sentenças quantificadas é obtida através do conceito de quantificadores de distribuição, introduzido por [Car87]. Basicamente este conceito traduz a
15
intuição básica de que um quantificador universal pode ser visto como uma conjunção
ilimitada e um quantificador existencial como uma disjunção ilimitada.
Seja Dom o conjunto infinito de sı́mbolos de constantes da linguagem, F uma fórmula
e ai sı́mbolos de constante correspondentes a um elemento de Dom. Então, temos que:
∀xF ≡ F (a1 ) ∧ F (a2 ) ∧ . . .; e
∃xF ≡ F (a1 ) ∨ F (a2 ) ∨ . . .
Como será visto no capı́tulo 4, as regras de um programa P-Datalog¬ equivalem a
fórmulas constituı́das por uma disjunção universalmente quantificada, e que são interpretadas sobre um Universo de Herbrand finito. Para domı́nios finitos, os quantificadores
universais que aparecem nas fórmulas podem ser vistos como uma conjunção limitada,
como é mostrado a seguir.
Seja Dom o conjunto finito de sı́mbolos de constantes de cardinalidade n, onde ai são
os sı́mbolos de constante correspondentes a um elemento de Dom, e F é uma fórmula.
Então, temos que:
∀xF ≡ F (a1 ) ∧ . . . ∧ F (an ); e
∃xF ≡ F (a1 ) ∨ . . . ∨ F (an )
Definição 2.3.2 Seja F (x1 , ..., xn ) uma fórmula de LFI1 com variáveis livres x1 ,. . .,xn , v
uma avaliação e δ uma interpretação. Dizemos que (δ, v) satisfaz F (x1 , ..., xn ) (denotado
por (δ, v) |= F (x1 , ..., xn )) se e somente se δ(F [v(x1 ), ..., v(xn )/x1 , ..., xn ]) é t ou i.
Exemplo 2.3.1 Seja R um sı́mbolo de predicado binário. Seja δ uma interpretação tal
que δ(R(a, b)) = t, δ(R(c, b)) = i e δ(R(p, q)) = f para todo (p, q) tal que p 6= c e p 6= a, ou
q 6= b. Então, (δ, v) |= (∃x • R(x, y) ∧ ¬∀xR(x, y)), onde v é uma avaliação que v(y) = b,
pois: δ |= (∃x • R(x, b) ∧ ¬∀xR(x, b)) ⇐⇒ δ(∃x • R(x, b) ∧ ¬∀xR(x, b)) ∈{t, i}, e
δ(∃x • R(x, b) ∧ ¬∀xR(x, b)) = δ((•R(a, b) ∨ •R(b, b) ∨ •R(c, b)) ∧ ¬(R(a, b) ∧ R(b, b) ∧
R(c, b))) = ((•t ∨ •f ∨ •i) ∧ ¬(t ∧ f ∧ i)) = (t ∧ ¬f) = t.
Se (δ,v) |= F para toda avaliação v, dizemos que δ é um modelo de F (denotado por
δ |= F ).
A lógica LFI1 é uma lógica paraconsistente uma vez que ela não verifica o princı́pio
da explosão, isto é, {A, ¬A} 6|= B para todo B. De fato, se considerarmos a interpretação
δ do exemplo 2.3.1, temos que δ |= R(c, b) e δ |= ¬R(c, b) mas δ 6|= R(b, a).
2.4
Datalog sem negação
Nesta seção é introduzida a linguagem de consultas Datalog [AVH95], e as diferentes
abordagens na definição de sua semântica. Um texto em português e mais acessı́vel sobre
bancos de dados dedutivos é apresentado em [Lif97].
16
A linguagem Datalog pode ser vista como uma versão simplificada da programação
em lógica [Llo93]. Ao longo desta seção serão ressaltadas algumas das diferenças entre
um programa Datalog e um programa lógico.
Um programa Datalog define as relações que ocorrem nas cabeças das regras baseado
em outras relações. Esta definição é recursiva, de maneira que relações definidas podem
também aparecer no corpo de regras. Um programa Datalog é interpretado como um
mapeamento de instâncias sobre as relações que ocorrem somente nos corpos das regras,
para instâncias sobre as relações que ocorrem nas cabeças das regras.
A seguir são formalizados os principais conceitos envolvidos na linguagem Datalog.
Definição 2.4.1 (Sintaxe do Datalog) Uma regra (Datalog) é uma expressão da forma
R1 (u1 ) ← R2 (u2 ), ..., Rn (un ),
onde n ≥ 1, R1 , ..., Rn são nomes de relações e u1 , ..., un são tuplas não instanciadas de
aridades apropriadas. Cada variável ocorrendo em u1 deve ocorrer em pelo menos uma das
tuplas u2 , ..., un (esta restrição não ocorre nos programas lógicos). Um programa Datalog
é um conjunto finito de regras Datalog.
A cabeça da regra é a expressão R1 (u1 ); e R2 (u2 ), ..., Rn (un ) que forma o corpo da
regra.
Um programa Datalog responde às necessidades das linguagens de consultas a bancos
de dados, e ao contrário de um programa lógico, não aceita sı́mbolos de função na sua
sintaxe.
Exemplo 2.4.1 (Programa Datalog) Seja G uma relação que representa um grafo.
Considere o programa Datalog PF T descrito a seguir:
T (x, y) ← G(x, y)
T (x, y) ← G(x, z), T (z, y)
O programa PF T mapeia uma relação G (um grafo) sobre uma relação T . A relação T
assim definida é o fecho transitivo (FT) de G.
Definição 2.4.2 (Instanciação) Dada uma avaliação2 v de variáveis, uma instanciação
de uma regra R1 (u1 ) ← R2 (u2 ), ..., Rn (un ) com v, é a regra obtida pela substituição de
cada variável x por v(x).
R1 (v(u1 )) ← R2 (v(u2 )), ..., Rn (v(un ))
O conjunto de regras instanciadas do programa Datalog P é denotado por ground(P ).
2
Uma avaliação é um mapeamento de sı́mbolos de variáveis para sı́mbolos de constantes.
17
Note que no contexto da programação lógica, o termo predicado é frequentemente
usado no lugar do termo nome de relação, R(u) é denotado por átomo ou fórmula atômica,
o termo fato denota um átomo instanciado, e o termo literal denota um átomo ou um
átomo negado.
As instâncias do banco de dados são representadas de forma linear, como conjuntos
finitos de fatos. No caso de Datalog, estas instâncias são 2-valoradas, isto é, representam
como verdadeiros os fatos que pertencem ao banco de dados, e como falsos os fatos que
não pertencem.
Definição 2.4.3 (Instância) Seja R o esquema do banco de dados formado pelo conjunto finito de nomes de relações. Seja R uma relação de aridade n, R ∈ R. Um fato sobre
R é uma expressão do tipo R(u), onde u é uma tupla instanciada, ou seja, u = a1 , . . . , an
onde ai são constantes, 1 6 i 6 n. Uma instância de relação R é um conjunto finito de
fatos sobre R. Uma instância do banco de dados sobre o esquema R é um conjunto finito
I, que é a união de instâncias de relação R, para toda relação R ∈ R.
Exemplo 2.4.2 Seja o esquema do banco de dados que contém as relações binárias
G(x, y) e T (x, y). A seguir temos a instância I deste banco de dados:
I = {G(1, 2), G(2, 3), G(3, 4), T (1, 3), T (2, 4)}
Dado um programa Datalog P , denotamos por adom(P ) o conjunto de constantes que
aparecem em P , e por adom(I) o conjunto de constantes que ocorrem na instância I. A
união adom(P ) ∪ adom(I) é denotada por adom(P, I).
Uma relação extensional é uma relação que ocorre somente no corpo das regras. Uma
relação intencional é uma relação que ocorre na cabeça de alguma regra do programa
Datalog P . O esquema (do banco de dados) extensional, denotado por edb(P ), consiste do
conjunto de todos os nomes de relações extensionais; enquanto que o esquema intencional
idb(P ) consiste de todos os nomes de relações intencionais. O esquema de P , denotado
por sch(P ), é a união de edb(P ) e idb(P ).
Exemplo 2.4.3 Considere o programa PF T do exemplo 2.4.1. Suas relações são classificadas como:
edb(PF T ) = {G},
idb(PF T ) = {T },
sch(PF T ) = {G, T }.
A semântica de um programa Datalog é um mapeamento apropriado de instâncias do
banco de dados sobre edb(P ) para instâncias do banco de dados sobre idb(P ), isto é, é
uma certa instância das relações intencionais que captura de maneira natural o que se está
18
definindo. Em alguns contextos, os dados de entrada são chamados de banco de dados
extensional e o programa de banco de dados intencional.
Os programas lógicos possuem uma vasta coleção de propostas, métodos e ferramentas
para definição da sua semântica correta [Dix96]. O programa Datalog é um programa
lógico com restrições, o que simplifica a definição de sua semântica, como é descrito a
seguir.
Existem três diferentes abordagens para se definir a semântica do Datalog: semântica
baseada na teoria de modelos, semântica baseada no ponto fixo e semântica baseada na
teoria da prova. Estas abordagens são equivalentes.
A semântica da linguagem P-Datalog¬ será definida segundo a abordagem baseada na
teoria de modelos e no ponto fixo. Esta é a razão pela qual a seguir serão apresentadas
essas duas semânticas da linguagem Datalog em maiores detalhes do que a semântica da
teoria da prova. Em [AVH95] pode ser encontrada uma melhor descrição da semântica
da teoria da prova para a linguagem Datalog.
2.4.1
Teoria da prova
A semântica da teoria da prova é baseada na obtenção de provas dos fatos. Um fato está
no resultado se existe uma prova para ele utilizando as regras e os fatos do banco de
dados.
Na perspectiva da teoria da prova, há dois modos de se deduzir fatos. O primeiro é
visualizar programas como “fábricas” produzindo todos os fatos que podem ser provados
a partir de fatos conhecidos. As regras são usadas de forma bottom-up, começando de
fatos conhecidos e deduzindo todas as possibilidades de novos fatos.
O segundo modo é a avaliação top-down que começa a partir de um fato a ser provado
e tenta demonstrá-lo pela dedução de lemas que são necessários para a prova. Esta é
a intuição por trás de uma técnica particular (chamada Resolução SLD) que originou o
campo de provas de teoremas, e encontra-se no cerne da programação em lógica.
Exemplo 2.4.4 Considere o programa PF T do exemplo 2.4.1:
T (x, y) ← G(x, y)
T (x, y) ← G(x, z), T (z, y)
Supondo que a instância com os fatos iniciais armazenados no banco de dados seja da
seguinte forma:
{G(1, 2), G(2, 3), G(3, 4)}
Para provar T (1, 4), pela segunda regra do programa PF T , este fato pode ser provado
pela prova de G(1, 2) e T (2, 4). G(1, 2) é um fato do banco de dados, temos então que
provar T (2, 4).
19
Aplicando-se a segunda regra novamente, temos G(2, 3) (um fato do banco de dados)
e T (3, 4) (aplicando-se a primeira regra), e obtemos T (2, 4).
Portanto, T (1, 4) é verdadeiro.
2.4.2
Teoria de modelos
Segundo a teoria de modelos, o programa Datalog é um conjunto de sentenças3 da lógica de
primeira ordem [Sou02], também chamado de teoria, que descreve um resultado desejado.
A instância do banco de dados resultante da execução do programa deve satisfazer as
sentenças, e neste caso é denominada modelo do programa.
Entretanto, pode existir mais de uma instância do banco de dados que satisfaz o
programa, sendo então necessário definir qual delas corresponde ao resultado esperado.
Os critérios necessários para esta escolha vão além das próprias sentenças do programa.
Dentro do contexto da teoria de modelos, são descritos a seguir: as relações entre
regras do programa Datalog e sentenças da lógica clássica de primeira ordem, noções de
modelo e o conceito de modelo esperado.
Programa Datalog como sentenças da lógica de primeira ordem
Uma regra da linguagem Datalog pode ser associada a uma sentença da lógica de primeira
ordem da seguinte maneira.
Seja ρ uma regra Datalog do tipo:
ρ : R1 (u1 ) ← R2 (u2 ), . . . , Rn (un ).
Podemos associá-la à seguinte sentença de primeira ordem:
∀x1 . . . xn (R1 (u1 ) ← R2 (u2 ) ∧ . . . ∧ Rn (un )),
(2.1)
onde x1 , . . . , xn são variáveis que ocorrem na regra ρ e ← corresponde à implicação lógica
clássica. Para um programa Datalog P , a conjunção de sentenças associadas às regras de
P é denotada por ΣP .
Uma instância I satisfaz uma regra ρ, denotado por I |= ρ, se para cada instanciação
da forma:
Ri (v(u1 )) ← R2 (v(u2 )), . . . , Rn (v(un ))
onde se R2 (v(u2 )), . . . , Rn (v(un )) pertence à I então Ri (v(u1 )) também pertence à I.
Exemplo 2.4.5 O programa PF T do exemplo 2.4.1 equivale às seguintes fórmulas da
lógica de primeira ordem:
3
Uma sentença é uma fórmula sem variáveis livres.
20
1. ∀x∀y(T (x, y) ← G(x, y))
2. ∀x∀y∀z(T (x, y) ← (G(x, z) ∧ T (z, y)))
Seja a instância J = {G(1, 2), G(2, 3), G(3, 4), T (1, 2)}. Neste caso, uma instanciação
da primeira regra de PF T nos fornece a seguinte regra r: T (1, 2) ← G(1, 2).
Temos que G(1, 2) e T (1, 2) pertencem a J e portanto J |= r.
Note que a sentença (2.1) é equivalente à
∀x1 . . . xn (R1 (u1 ) ∨ ¬R2 (u2 ) ∨ . . . ∨ ¬Rn (un )).
(2.2)
Uma fórmula que consiste de uma disjunção de literais onde apenas um deles é positivo,
como em (2.2), é chamada de cláusula de Horn. Um programa Datalog pode ser visto
como um conjunto de cláusulas de Horn.
Modelo esperado
Entre os modelos de ΣP é preciso especificar qual deles corresponde ao resultado esperado.
Para a linguagem Datalog, tal modelo não deve conter mais fatos além do necessário para
satisfazer as sentenças de ΣP . Esta é a definição intuitiva de modelo minimal. Então o
modelo esperado é um modelo minimal, como definido a seguir.
Definição 2.4.4 Seja P um programa Datalog e I uma instância sobre sch(P ). Um
modelo de P é uma instância sobre sch(P ) que satisfaz ΣP . A semântica de P sobre I,
denotada por P (I), é, caso exista, o modelo minimal de P contendo I.
Observação 2.4.1 (Modelo minimal) Reforçando a escolha do modelo minimal como
uma solução natural, temos a hipótese do mundo fechado (CWA) que relaciona o banco de
dados com o mundo que ele modela. Normalmente os bancos de dados são incompletos,
pois fatos que estão no mundo não estão necessariamente registrados no banco de dados.
É intuitivo que os fatos que estão armazenados no banco de dados sejam considerados
verdadeiros; porém os que não estão, poderiam ser considerados falsos, verdadeiros ou
indefinidos. A hipótese do mundo fechado soluciona este problema: assume que todos os
fatos que não estão no banco de dados são falsos. Dentro desta linha de pensamento, é
razoável considerar verdadeiros somente os fatos que são verdadeiros em todos os mundos
modelados. Ou seja, o modelo minimal consiste dos fatos que são conhecidos em todos os
modelos de mundo que satisfazem as sentenças do programa.
Segundo a definição anterior 2.4.4, a semântica P (I) é uma instância sobre sch(P ). O
conjunto de todas as instâncias sobre sch(P ), considerando-se somente o domı́nio dado
por adom(P, I), é um conjunto finito.
21
Definição 2.4.5 Dados um programa P e uma instância I, B(P, I) é uma instância sobre
sch(P ) definida do seguinte modo:
a) Para cada relação R ∈ edb(P ), um fato R(u) ∈ B(P, I) se e somente se R(u) ∈ I; e
b) Para cada relação R ∈ idb(P ), cada fato R(u) com constantes em adom(P, I) está
em B(P, I).
É importante destacar que no contexto de banco de dados somente são consideradas
as interpretações de Herbrand ([Llo93]), aquelas para as quais o conjunto dos sı́mbolos
de constantes é o domı́nio de avaliação das variáveis e onde cada sı́mbolo de constante é
interpretado por si mesmo. Desta forma, B(P, I) é também chamado de base de Herbrand.
Na programação em lógica a base de Herbrand é um conjunto infinito, devido a presença
dos sı́mbolos de função.
O exemplo seguinte mostra o B(P, I) de um programa Datalog, segundo a definição
anterior.
Exemplo 2.4.6 Continuando com o programa do exemplo 2.4.1, onde sch(PF T ) = {G, T },
e considerando a instância I = {G(1, 2), G(2, 3), G(3, 4)}, temos que:
adom(P, I) =
B(P, I) =
{1, 2, 3, 4}, e
{G(1, 2), G(2, 3), G(3, 4),
T (1, 1), T (1, 2), T (1, 3), T (1, 4),
T (2, 1), T (2, 2), T (2, 3), T (2, 4),
T (3, 1), T (3, 2), T (3, 3), T (3, 4),
T (4, 1), T (4, 2), T (4, 3), T (4, 4), }
O lema apresentado a seguir mostra que B(P, I) é um modelo de P que contém I.
Lema 2.4.1 ([AVH95]) Seja P um programa Datalog e I uma instância sobre edb(P ),
então B(P, I) é modelo de P contendo I.
Desta forma, se existe semântica para P e instância I, então P (I) é um subconjunto
de B(P, I). O teorema seguinte mostra que a semântica P (I) sempre existe.
Teorema 2.4.1 ([AVH95]) Seja P um programa Datalog, I uma instância sobre edb(P )
e M o conjunto de modelos de P contendo I. Então:
T
1) A intersecção dos modelos de P que contém I, denotada por M é o modelo minimal
de P contendo I. Portanto P (I) existe e é definido.
2) adom(P (I)) ⊆ adom(P, I).
3) Para cada R ∈ edb(P ), P (I)(R) = I(R).
22
Os resultados do teorema 2.4.1 nos fornece uma maneira de calcular a semântica
de programas Datalog: dados P e I, é necessário determinar qual das instâncias que
pertencem a B(P, I) são modelos de P contendo I, para então calcular a intersecção
destes modelos. É um algoritmo ineficiente apesar de eficaz.
Na próxima seção é descrito a semântica de programas Datalog na abordagem da
teoria do ponto fixo.
2.4.3
Teoria do Ponto Fixo
Nesta seção serão utilizadas as definições e proposições sobre reticulados, operadores e
teoria do ponto fixo apresentadas na seção 2.1.
A semântica do programa, segundo a teoria do ponto fixo, pode ser definida como uma
solução particular de uma equação de ponto fixo. A abordagem direciona para a iteração
de uma consulta até que um ponto fixo é alcançado.
É definido um operador denotado por operador de consequência imediata, que produz
novos fatos a partir de fatos conhecidos. Após a definição do operador de consequência
imediata, são apresentadas propriedades algébricas (definidas na seção 2.1) que este operador possui, e que são importantes na construção da semântica do programa Datalog.
O conjunto de instâncias sobre sch(P ) é denotado por InstP . Existe uma ordem natural de precedência entre as instância fornecida pelo operador ⊆. Desta forma, (InstP , ⊆)
formam um reticulado completo.
Definição 2.4.6 Seja P um programa Datalog. O operador de consequência imediata,
denotado por TP , é um mapeamento TP : InstP → InstP da seguinte forma:
Para cada instância I pertencente a InstP , e para todo fato A ∈ B(P, I), A ∈ TP (I)
se e somente se:
1)A corresponde a uma relação R onde R ∈ edb(P ), e A ∈ I; ou
2) existe regra de ground(P ) do tipo A ← B1 , . . . , Bn , onde Bi ∈ B(P, I) e Bi ∈ I,
para todo i, 1 6 i 6 n.
O exemplo seguinte mostra a aplicação do operador TP .
Exemplo 2.4.7 Considere o programa PF T apresentado no exemplo 2.4.1 que calcula o
fecho transitivo do grafo G:
T (x, y) ← G(x, y)
T (x, y) ← G(x, z), T (z, y)
Considere a instância:
I = {G(1, 2), G(2, 3), G(3, 4)}.
23
O operador TP aplicado à instância I é mostrado a seguir:
TP (I) = I ∪ {T (1, 2), T (2, 3), T (3, 4)}.
Lema 2.4.2 ([AVH95]) Seja P um programa Datalog. O operador TP é monotônico.
Um operador monotônico (definição 2.1.4) possui propriedades que são importantes
na construção da semântica de programas Datalog, como as proposições 2.1.3 e 2.1.4, que
mostram que para um operador monotônico sempre existe um único menor ponto fixo.
Desta forma podemos garantir que o operador de consequência imediata TP possui sempre
um menor ponto fixo que é único.
O próximo lema mostra que um ponto fixo de TP é sempre um modelo de P contendo
I.
Lema 2.4.3 ([AVH95]) Seja P um programa Datalog e I uma instância sobre sch(P ).
Se I é ponto fixo de TP então I é modelo P .
Entretanto, nem todo modelo de P é ponto fixo, como mostra o exemplo a seguir:
Exemplo 2.4.8 Seja o seguinte programa Datalog P :
p←s
q←r
O programa possui o seguinte modelo:
M = {p, r, q},
e TP (M) = {r, q} 6= M. Portanto M é modelo de P e não é ponto fixo de TP .
O operador TP aplicado a qualquer modelo de um programa P contendo I, resulta
sempre em uma instância que está contida ou é igual ao modelo. É o que ocorre no
exemplo 2.4.8, onde TP (M) ⊆ M, e é o que formaliza o lema seguinte.
Lema 2.4.4 ([AVH95]) Seja P um programa Datalog e I uma instância sobre sch(P ).
I é modelo de P se e somente se TP (I) ⊆ I.
Todos os lemas anteriores levam ao teorema seguinte que conclui que o menor ponto
fixo de TP para um programa Datalog P e instância inicial I, coincide com o modelo
minimal de P contendo I, o modelo P (I).
Teorema 2.4.2 ([AVH95]) Seja P um programa Datalog e I uma instância sobre edb(P ).
O operador TP possui um menor ponto fixo contendo I que é igual a P (I).
24
O resultado apresentado pelo teorema anterior mostra que sempre existe semântica
para programas Datalog, e que esta semântica coincide com o menor ponto fixo do operador TP . A seguir será apresentado um método construtivo para obtenção da semântica.
Definição 2.4.7 Seja uma instância I sobre edb(P ). O operador TP define a sequência
TP (I), TP2 (I), TP3 (I) . . ., que é denotada por {TPi (I)}i>0 , onde:
TP1 (I) = TP (I)
TP2 (I) = TP (TP (I))
TP3 (I) = TP (TP2 (I))
...
TP ↑= sup{TPn }n>0
De I ⊆ TP (I) e de TP ser monotônico, temos que a sequência {TPn }n>0 é crescente:
I ⊆ TP (I) ⊆ TP2 (I) ⊆ TP3 (I) ⊆ . . . ⊆ B(P, I).
O conjunto B(P, I) é finito para programas Datalog, e desta forma a sequência {TPi (I)}i>0
converge para um ponto fixo em um número finito de passsos. Seja N o número de fatos
em B(P, I). A sequência {TPi (I)}i>0 converge para um ponto fixo em no máximo N passos.
Isto é, para i > N temos TPi (I) = TPN (I), e em particular temos que:
TP (TPN (I)) = TPN (I)
Então TPN (I) é ponto fixo de TP . O ponto fixo obtido pela sequência {TPi (I)}i>0 é
denotado por TP (I) ↑.
Exemplo 2.4.9 Continuando o exemplo 2.4.7, a aplicação iterativa de TP é mostrada a
seguir:
TP (I) = I ∪ {T (1, 2), T (2, 3), T (3, 4)}
TP2 (I) = TP (TP (I)) = TP (I) ∪ {T (1, 3), T (2, 4)}
TP3 (I) = TP (TP2 (I)) = TP (I) ∪ {T (1, 4)}
TP4 (I) = TP (TP3 (I)) = TP3 (I)
É possı́vel notar que a sequência de instâncias produzidas por TP é crescente e que a
partir da quarta iteração é atingido um ponto fixo que corresponde à instancia dada por
TP3 .
A partir do programa P e sua instância inicial I é possı́vel, através do operador TP ,
construir a sequência {TPi (I)}i>0 que converge para o modelo minimal de P contendo I.
Este resultado é formalizado pelo próximo teorema.
Teorema 2.4.3 ([AVH95]) Seja P um programa Datalog e I uma instância sobre edb(P ).
Então, TP (I) ↑= P (I).
25
Observação 2.4.2 (Teoria do ponto fixo na programação em lógica) Os programas
Datalog são mais simples que os programas lógicos. Em particular, os programas lógicos
podem ter sı́mbolos de função, o que torna o conjunto B(P, I) infinito. Desta forma nem
sempre a sequência {TPi (I)}i>0 converge em um número finito de passsos. Entretanto, a
sequência {TPi I (∅)}i>0 converge em um número finito de passos. Então, na programação
em lógica, a instância inicial I é incorporada ao programa dando origem a um novo programa denotado por PI . O programa PI é obtido de P com a adição de regras do tipo
A ← para cada fato A presente na instância I. Esta regra com corpo vazio é chamada
de clausula unitária, e no caso do Datalog ela não contém variáveis. O operador de consequência imediata TPI é definido sobe o reticulado completo formador InstP , onde um
fato A ∈ TPI (K) se e somente se existe regra em ground(PI ) do tipo A ← B1 , . . . , Bn
onde {B1 , . . . , Bn } ⊆ K. O operador TPI é contı́nuo e monotônico, e pela proposição
2.1.5 temos que o ponto fixo de TPI é o sup(Ki |i > 0), onde K0 = ⊥ e para cada i > 0,
Ki = TPI (Ki−1 ). No caso do Datalog, ⊥ = ∅ e:
∅ ⊆ TPI (∅) ⊆ . . . ⊆ TPi I (∅) ⊆ . . .
que converge para P (I).
2.4.4
Métodos de avaliação de Datalog
Datalog é uma linguagem declarativa, e desde a sua introdução surgiram vários métodos
procedimentais de avaliação de seus programas, e uma série de técnicas de otimização
desses métodos. Os métodos de avaliação são geralmente separados em duas classes:
avaliações bottom-up e avaliações top-down. A seguir, estas técnicas são brevemente introduzidas. Uma descrição mais detalhada pode ser encontrada em [AVH95] e [CGT90],
e em [Lif97] temos um texto introdutório em português.
As avaliações bottom-up utilizam um método baseado em uma sequência de iterações
do operador de consequência imediata Tp , onde a partir dos fatos contidos no banco de
dados inicial, e do programa Datalog, são deduzidos novos fatos que constituem em uma
instância do banco de dados intencional. As regras de um programa são vistas como
fábricas que produzem todos os fatos que são consequência lógica do programa Datalog a
partir dos fatos presentes inicialmente na instância do banco de dados. Dentre os métodos
de avaliação bottom-up, temos os métodos: ingênuo (naif ) e semi-ingênuo. O método
ingênuo corresponde ao método de avaliação bottom-up mais simples, e o método semiingênuo é uma otimização do método ingênuo, onde cálculos redundantes são eliminados.
A classe de métodos de avaliação top-down, ao invés de partir dos fatos iniciais,
primeiro consideram uma consulta e as regras do programa antes de chegar a uma resposta. Seja P um programa Datalog. Uma consulta Datalog é o par (P, q), onde q é uma
regra Datalog cuja cabeça é constituı́da de uma nova relação query, da seguinte forma:
26
query(u) ← R(v)
onde R ∈ idb(P ). Um fato é relevante à consulta (P, q) sobre a instância inicial I, se existe
uma prova para query no qual o fato ocorre. Os métodos top-down buscam melhorar a
eficiência da avaliação considerando somente fatos relevantes. Dentre os métodos topdown, temos os algoritmos Query-Subquery, Recursive Query Answering/Frozem Query
Iteration.
Um resultado importante das pesquisas sobre métodos de avaliação de Datalog, é
que existem técnicas de otimização, como magic-sets, que tornam métodos bottom-up tão
eficientes quanto os top-down.
2.5
Datalog¬ - Datalog com negação
Nesta seção é introduzida a linguagem de consulta Datalog¬ [AVH95], e são apresentadas duas abordagens semântica para programas Datalog¬ : semântica de modelo estável
[GL88] e semântica bem-fundada [Prz90]. No final desta seção, dois métodos construtivos
da semântica bem-fundada, baseados em operadores de ponto fixo [Van89, Prz89], são
descritos.
A linguagem Datalog descrita na seção anterior expressa vários tipos de consultas
recursivas, porém possui alguns pontos fracos quanto a sua força de expressão. O Datalog
não é capaz de expressar consultas do tipo diferença entre duas relações, como mostra o
exemplo a seguir:
Exemplo 2.5.1 Um programa Datalog que verifica os pares não conectados em um grafo
G, seria um complemento do programa PF T do exemplo 2.4.1 que calcula o fecho transitivo
de um grafo. Seja PF T Comp o resultado da adição da seguinte regra ao programa PF T :
CT (x, y) ←∼ T (x, y)
A linguagem Datalog¬ é uma extensão da linguagem Datalog, em que é permitido no
corpo das regras literais negativos como mostra a definição seguinte.
Definição 2.5.1 (Sintaxe de Datalog¬ ) Um programa Datalog¬ é um conjunto finito
de regras do tipo:
A ← L1 , ..., Ln
onde A é um átomo do tipo R(u), e Li são literais do tipo R(u) ou ∼ R(u), sendo que R é
o nome de relação e u é uma tupla não instanciada de aridade apropriada, e ∼ representa
o sı́mbolo da negação por default.
27
No contexto da programação em lógica, programa do tipo definido pela sintaxe de
Datalog¬ é denominado programa lógico padrão (definição 2.2.2). Nesta seção, e nas
próximas, é considerado que os programas possuem os seus dados de entrada incorporados,
da mesma forma que os programas PI (veja observação 2.4.2).
Observação 2.5.1 (Negação por default) O operador de negação (∼) que é utilizado
nos programas Datalog¬ representa a negação por default, que baseia-se na falta de
evidência de que determinado fato é verdadeiro. Esta negação está relacionada com a
hipótese do mundo fechado - CWA (veja observação 2.4.1). A maioria das semânticas
aplicadas ao programa p ←∼ q resulta em q falso e p verdadeiro. A falta de evidência de
que q é verdadeiro é usada para assumir que q é falso. A negação por default é mais fraca
do que outro tipo de negação denominada negação explı́cita [APP96], em que é necessário
que exista uma prova de que o fato é falso para que a sua negação explı́cita (¬) seja
considerada verdadeira. Ou seja, não basta o fato estar ausente do banco de dados para
que a sua negação explı́cita suceda.
2.5.1
A negação e suas implicações semânticas
Ao incluir a negação no Datalog, temos a necessidade de definir a semântica dos fatos
negativos. Infelizmente as semânticas do Datalog sem negação não podem simplesmente
ser estendidas para o Datalog¬ . No caso da semântica baseada na teoria do ponto fixo,
podemos estender de forma natural a definição do operador de consequência imediata TP
(definido em 2.4.6) para programas com negação, como mostra a definição seguinte.
Definição 2.5.2 Seja P um programa Datalog. O operador de consequência imediata
estendido, denotado por TP0 , é um mapeamento TP0 : InstP → InstP da seguinte forma:
para cada instância I pertencente a InstP , e para todo fato A ∈ B(P, I), A ∈ TP0 (I) se e
somente se:
1. A corresponde a uma relação R onde R ∈ edb(P ), e A ∈ I; ou
2. existe regra de ground(P ) do tipo A ← L1 , . . . , Ln , onde para todo literal positivo
Li = C, C ∈ B(P, I) e C ∈ I; e para todo literal negativo Li =∼ C, C ∈ B(P, I) e
C 6∈ I, para todo i, 1 6 i 6 n.
Porém o operador estendido TP0 aplicado a um programa lógico padrão não é monotônico,
como mostra o próximo exemplo.
Exemplo 2.5.2 Seja o programa Datalog¬ P0 descrito a seguir:
p ←∼ q.
28
Sejam as instâncias4 I = {p} e J = {p, q}. É fácil ver que I ⊆ J. Aplicando o operador
TP0 às instâncias I e J, temos TP0 (I) = {p} e TP0 (J) = {q}. Ou seja, TP0 (I) ⊆
6 TP0 (J).
Portanto, TP0 não é monotônico.
Como o operador TP0 não é monotônico, não se pode mais garantir que sempre existe
um ponto fixo, nem que o menor ponto fixo é único, e nem que a sequência {TP0 i (∅)}i>0
sempre converge para o menor ponto fixo de TP0 , como mostram os exemplos seguintes:
Exemplo 2.5.3 Seja o programa Datalog¬ P1 mostrado a seguir:
p ←∼ p.
O cálculo de TP0 a partir da instância vazia é dado por:
TP0 (∅) = {p}
TP01 (∅) = ∅
TP02 (∅) = {p}
TP03 (∅) = ∅
TP04 (∅) = {p}
...
Portanto TP0 não posui ponto fixo.
p ←∼ q
q ←∼ p
Portanto, TP0 posui dois pontos fixos minimais: I1 = {p} e I2 = {q}, pois TP0 ({p}) =
{p} e TP0 ({q}) = {q}.
p ←∼ r
r ←∼ p
p ←∼ p, r
Temos que TP0 ({p}) = {p}. Logo, {p} é ponto fixo de TP0 .
A sequência {TP0 i (∅)}i>0 é mostrada a seguir:
4
Seguindo a notação utilizada em Datalog (seção 2.4), as instância são representadas como conjuntos
de átomos positivos.
29
TP0 (∅) = {p, r}
TP01 (∅) = {}
TP02 (∅) = {p, r}
TP03 (∅) = {}
TP04 (∅) = {p, r}
...
Portanto, a sequência {TP0 i (∅)}i>0 não converge para o menor ponto fixo.
A semântica baseada na teoria de modelos também não pode ser naturalmente estendida para o Datalog¬ . Um programa Datalog¬ pode ter vários modelos minimais,
como mostra o exemplo 2.5.4 onde {p} e {q} são modelos minimais de P . É necessário
determinar qual deles é o modelo esperado.
Várias semânticas tem sido propostas para distinguir o modelo esperado dos outros
modelos candidatos. Entre as abordagens propostas, as mais importantes são a semântica
por estratificação, a semântica de modelo estável e a semântica bem-fundada.
A semântica por estratificação [AVH95, Lif97] impõe como restrição sintática aos programas considerados, a ausência de recursão negativa. Isto é, a definição de um predicado
intencional não deve incluir o seu próprio complemento, como no programa Pcargo do
exemplo de motivação 1.0.1 mostrado a seguir:
cargo(x) ← ∼devedor(x), indicadoPor(x,y), ∼cargo(y).
Tal restrição não é imposta pela semântica bem-fundada nem pela semântica de modelo estável. A semântica de P-Datalog¬ , definida no capı́tulo 4, é uma semântica bemfundada.
A semântica de modelo estável [GL88] possui muito em comum com a semântica bemfundada. Van Gelder et al. [VRS91] foram os primeiros a definir a semântica bem-fundada,
e esta definição foi reconstruı́da em termos de modelos 3-estáveis por Przymusinski [Prz90].
Nas próximas seções são descritas a semântica de modelos estáveis (2-valorados) [GL88] e a
semântica bem-fundada baseada em modelo 3-estável [Prz90]. Os programas considerados
são programas Datalog¬ , e serão chamados simplesmente de programas.
2.5.2
Semântica de modelo estável
Nesta seção é apresentada a definição da semântica de modelo estável apresentada por
Gelfond e Lifschitz em [GL88].
Gelfond e Lifschitz definiram que o resultado esperado de um programa é um modelo
capaz de reproduzir a si mesmo ao passar por uma certa transformação, chamada de
transformação de estabilidade. Desta forma, um fato presente no modelo não pode ser
deduzido mais tarde como falso, e todos os fatos falsos que podem ser deduzidos do modelo
30
já devem estar no modelo. Esta é a definição intuitiva de modelo estável, que é definido
formalmente a seguir.
Definição 2.5.3 A transformação de estabilidade S é definida da seguinte maneira. Seja
P um programa e I uma instância inicial. O programa P 0 é obtido de P eliminando-se:
1) Toda regra instanciada que possui literal negativo ∼ B tal que B ∈ I;
2) Todo literal negativo do corpo das regras restantes.
Desta forma P 0 é um programa sem negação, e através do operador de consequência
imediata TP (definido em 2.4.6) é possı́vel se chegar ao único modelo minimal de P 0 . O
menor ponto fixo de TP aplicado ao programa P 0 , estabilizado a partir do programa P e
instância I, é denotado por SΠ (I).
A definição de modelo estável é formalizada a seguir.
Definição 2.5.4 (Modelo estável) Seja P um programa e I uma instância. Se SΠ (I) = I
então I é modelo estável de P .
A definição anterior nos indica uma maneira de verificar se uma determinada instância
é um modelo estável através do uso da transformação de estabilidade S e do operador de
consequência imediata TP . O próximo teorema mostra que os modelos estáveis, como o
próprio nome indica, são modelos do programa.
Teorema 2.5.1 ([GL88]) Seja P um programa. Todo modelo estável de P é também
modelo de P .
A semântica de modelo estável é definida a seguir.
Definição 2.5.5 (Semântica de modelo estável) Se um programa P possui somente
um modelo estável, então P possui uma semântica de modelo estável que coincide com
este único modelo estável de P .
No próximo exemplo é mostrado o caso em que uma instância não é modelo estável e
uma outra instância que é o único modelo estável.
Exemplo 2.5.6 Considere o seguinte programa Pwin :
move(1, 2) ←
win(x) ← move(x, y), ∼ win(y)
O programa ground(P ) é mostrado a seguir:
31
move(1, 2) ←
win(1) ← move(1, 1), ∼ win(1)
win(1) ← move(1, 2), ∼ win(2)
win(2) ← move(2, 2), ∼ win(2)
win(2) ← move(2, 1), ∼ win(1)
0
Seja M1 = {win(2)}. Então, pela transformação de estabilidade S, temos que Pwin
corresponde à:
move(1, 2) ←
win(1) ← move(1, 1)
win(2) ← move(2, 1)
Então SΠ (M1 ) = {move(1, 2)} que é diferente de M1 . Portanto M1 não é modelo
estável. Tal resultado era de se esperar pois M1 não é modelo de Pwin .
0
Seja a instância M2 = {move(1, 2), win(1)}, onde Pwin
é:
move(1, 2) ←
win(1) ← move(1, 2)
win(2) ← move(2, 1)
Então SΠ (M1 ) = {move(1, 2), win(1)} = M2 . Portanto M2 é modelo estável de Pwin .
Existem outros modelos estáveis entre as 26 possibilidades5 de instâncias de Pwin ?
Neste caso, é certo que toda programa transformado P 0 inclui move(1, 2) e não inclui
move(1, 1), move(2, 1), move(2, 2). Desta forma elimina-se muitas das possibilidades, e
após examinar todas as restantes, conclui-se que M2 é o único modelo estável de P .
Portanto, M2 é a semântica de modelo estável de P .
A semântica de modelo estável não se aplica a programas que não possuem modelo
estável, ou àqueles que possuem vários modelos estáveis, como mostram os exemplos a
seguir:
Exemplo 2.5.7 (Programa com nenhum modelo estável) Considere o seguinte programa P descrito a seguir:
work ← ∼ tired
sleep ← ∼ work
tired ← ∼ sleep
angry ← ∼ paid,work
paid ←
5
O valor 6 corresponde ao número de átomos de B(P ).
32
O programa não possui nenhum modelo estável, e portanto não possui uma semântica de
modelo estável.
Exemplo 2.5.8 (Programa com vários modelos estáveis) Considere o seguinte programa P1 :
p ←∼ q
q ←∼ p
O programa possui dois modelos estáveis: {p} e {q}, e portanto não possui uma semântica
de modelo estável.
2.5.3
Semântica bem-fundada
Nesta seção é apresentada a proposta de semântica bem-fundada baseada em modelos
3-estáveis [Prz90], onde podem ser encontradas as demonstrações dos resultados aqui
relatados.
A semântica bem-fundada introduzida por Van Gelder et al. [VRS91], é definida como
um modelo de um programa que corresponde ao modelo esperado, também chamado
de modelo canônico, onde alguns fatos podem ter o seu valor indefinido. Van Gelder
introduziu o conceito de modelo total e parcial, onde os modelos parciais, ao contrário
dos modelos totais, são aqueles em que alguns fatos podem ter o seu valor-verdade não
determinado. Os modelos parciais podem ser vistos como interpretações 3-valoradas onde
é possı́vel distinguir fatos verdadeiros, falsos e indefinidos.
Przymusisnski [Prz90] argumenta que a necessidade de se considerar interpretações 3valoradas para descrever o nosso conhecimento é justificável se considerarmos que o nosso
conhecimento quase sempre é incompleto. É necessário que possamos representar fatos
nem verdadeiros e nem falsos: os fatos indefinidos. Da mesma forma, um programa pode
conter predicados cuja veracidade ou falsidade são determináveis, e outros indeterminados.
Semânticas que são definidas somente para uma classe limitada de programas geralmente
não conseguem obter uma resposta para programas deste tipo, como a semântica de
modelo estável [GL88] (veja exemplo 2.5.7).
O próximo teorema mostra a estreita ligação entre a semântica de modelo estável e a
semântica bem-fundada:
Teorema 2.5.2 ([VRS91]) Se a semântica bem-fundada de um programa P é um modelo total, então este modelo é o único modelo estável (2-valorado) de P .
Em muitos programas a semântica bem-fundada coincide com a semântica de modelo
estável, dando-nos a impressão de que a única diferença entre elas é que a semântica bemfundada define modelos parciais quando o programa possui mais de um modelo estável.
33
Entretanto, existem programas que possuem um único modelo estável e a semântica bemfundada é um modelo parcial. Ou seja, o sentido contrário do teorema 2.5.2 não é necessariamente verdadeiro, como será mostrado no exemplo 2.5.14.
A seguir é descrita a lógica 3-valorada que é a lógica base da semântica bem-fundada.
Os termos utilizados a seguir, que são relacionados a lógica, podem ser encontrados em
[Sou02].
Lógica 3-valorada
A lógica 3-valorada, definida em [Prz89, Prz90], introduz o valor-verdade indefinido em
adição aos valores-verdade verdadeiro e falso da lógica clássica 2-valorada.
Seja L uma linguagem de primeira ordem sobre o alfabeto A da lógica clássica de
primeira ordem acrescido dos sı́mbolos proposicionais t, f e u, que denotam as propriedades de um dado átomo ser verdadeiro, falso e indefinido, respectivamente. As
fórmulas de L são definidas de modo usual como na lógica de primeira ordem.
Dado um programa P , o conjunto de constantes de P é denotado por adom(P ); o
conjunto de todos os átomos de P instanciados define a base de Herbrand, e é denotado
por B(P ). O programa instanciado ground(P ), é formado pelas regras de P instanciadas
de acordo com adom(P ).
A seguir é definida uma interpretação 3-valorada, onde serão consideradas somente as
interpretações de Herbrand. Nas interpretaçõe de Herbrand os sı́mbolos de constantes são
interpretados por si mesmo [Llo93].
Definição 2.5.6 (Interpretação 3-valorada) Uma interpretação 3-valorada I é definida
pelo par hT ; F i, onde T e F são subconjuntos disjuntos de B(P ). O conjunto T contém
todos os átomos instanciados que são verdadeiros em I, o conjunto F contém todos os
átomos instanciados que são falsos em I, e o conjunto U contém os átomos restantantes,
onde U = B(P ) − (T ∪ F ). Os átomos de U são indefinidos em I. Uma interpretação
3-valorada é uma interpretação 2-valorada se o conjunto U é vazio.
Toda interpretação 3-valorada I da proposição t (f, u) é verdadeira (falsa, indefinida
respectivamente.)
Seja V ={f, u, t} o conjunto de valores-verdade. O conjunto V possui uma ordem
natural dada por: f 6 u 6 t. Przymusinski [Prz90] ressalta que o valor intuitivo de u é
o de parcialmente verdadeiro. Se um determindo fato A é interpretado como u significa
que foi atribuı́do alguma (porém limitada) verdade ao fato A.
Toda interpretação 3-valorada I = hT ; F i pode ser vista como uma função I : B(P ) →
V , onde:


 t se A ∈ T
I(A) =
f se A ∈ F


u se A ∈ U
34
A noção de interpretação é estendida para as fórmulas fechadas da linguagem na
definição seguinte.
Definição 2.5.7 Seja I uma interpretação 3-valorada. Então:
• Seja A um átomo instanciado. Então I(A) = t (u, f ) se A é verdadeiro (indefinido,
falso), respectivamente, em I.
• Seja A um átomo instanciado. Se I(A) = t então I(∼ A) = f. Se I(A) = f então
I(∼ A) = t. Se I(A) = u então I(∼ A) = u.
• Sejam F e G duas fórmulas fechadas, então:
I(F ∧ G) = min{I(F ), I(G)};
I(F ∨ G) = max{I(F ), I(G)};
(
t, se I(G) > I(F )
I(G ← F ) =
f, caso contrário
I(∀xF (x)) = min{I(F (A))|A ∈ B(P )};
I(∃xF (x)) = max{I(F (A))|A ∈ B(P )}
onde o máximo e o mı́nimo de um conjunto vazio é verdadeiro e falso respectivamente.
A definição de modelo é dada a seguir.
Definição 2.5.8 Uma interpretação M de um programa P é modelo de P se para toda
a regra r de ground(P ) temos que M(r) = t. Ou seja, se r é do tipo A ← L1 , . . . , Ln ,
temos que:
M(A) > min{M(L1 ), . . . , M(Ln )}.
Exemplo 2.5.9 Seja o programa P mostrado a seguir:
p ←∼ q
q ←∼ p
Seja I uma interpretação 3-valorada de P , tal que: I = h{p}; {q}i, onde T = {p},
F = {q} e U = ∅. Ou seja, I(p)=t e I(q)=f.
Seja J uma interpretação 3-valorada de P , tal que: J = h∅; ∅i, onde T = ∅, F = ∅ e
U = {p, q}. Ou seja, J(p)=u e J(q)=u.
Tanto a interpretação I quanto a interpretação J são modelos de P .
A ordem natural entre interpretações 3-valoradas é dada pelo operador 4 definida a
seguir.
35
Definição 2.5.9 Sejam as interpretações I = hT ; F i e J = hT 0 ; F 0 i.
I 4 J se e somente se T ⊆ T 0 e F ⊇ F 0 .
Esta definição equivale a
I 4 J se e somente se ∀A ∈ B(P ) I(A) 6 J(A).
Exemplo 2.5.10 Sejam as interpretações I = h{p}; {q}i e J = h∅; {p, q}i. Temos a
seguinte ordem: J 4 I.
Modelo 3-estável
Przymusisnski [Prz90] apresenta uma definição de modelo 3-estável, que é uma extensão
definição de modelo estável (2-valorado) [GL88]. Todo modelo estável (2-valorado) é um
modelo 3-estável, como será mostrado. No decorrer do texto é usado simplesmente modelo
estável para denotar modelo estável 2-valorado.
Przymusisnski mostra que todo programa P possui pelo menos um modelo 3-estável,
e que o modelo que possui os fatos verdadeiros e falsos presentes em todos os modelos
3-estáveis de P coincide com a semântica bem-fundada de P .
Um resultado importante, válido para programa sem negação, é que todo programa
sem negação possui um único modelo minimal (seção 2.4). Przymusinski define então,
o programa positivo estendido, que é um programa sem negação, onde são permitidas as
proposições t, u e f, que representam valores-verdade, entre os literais do corpo das regras
do programa.
Uma vez definidos os programas positivos estendidos, a definição do operador de consequência imediata TP (definido em 2.4.6) é estendida para a lógica 3-valorada da seguinte
forma:
Definição 2.5.10 (Operador de consequência imediata 3-valorado) Seja P um programa positivo estendido, I uma interpretação 3-valorada de P , e A ∈ B(P ). O operador
de consequência imediata denotado por 3-TP é definido por:


 max{I(Fk )} se existem regras do tipo A ← Fk em ground(P),
3-TP (I)(A) =
para todo k, k > 0;


f
caso contrário
Em seguida é mostrado que para um programa positivo estendido P , o operador 3-TP
possui um menor ponto fixo que corresponde ao modelo minimal de P .
Teorema 2.5.3 ([Prz90]) Se P é um programa positivo estendido, então o operador
3-TP possui um menor ponto fixo MP , e MP é modelo minimal de P .
36
Exemplo 2.5.11 Seja P o programa positivo estendido mostrado a seguir:
c←
a ← c, u
b ← b, u
O modelo minimal de P corresponde à interpretação 3-valorada I, onde I = h{c}; {b}i.
I também é o menor ponto fixo de 3-TP , obtido construtivamente a partir da interpretação
I0 = h∅; ∅i, como é mostrado a seguir:
3-TP (I0 ) = h{c}; {a, b}i
3-TP1 (I0 ) = h{c}; {b}i
3-TP2 (I0 ) = h{c}; {b}i
O menor ponto fixo de 3-TP coincide com a interpretação 3-valorada I, que por sua vez é
o modelo minimal de P .
Przymusinski propõe uma extensão da transformação de estabilidade S [GL88] (descrita na seção 2.5.3) para interpretações 3-valoradas, e a partir da qual é definido o modelo
3-estável.
Definição 2.5.11 Seja P um programa e I uma interpretação 3-valorada. A transformação GL estendida produz o programa PI pela substituição de toda ocorrência de
literais do tipo ∼ A em ground(P ), pelo valor-verdade dado por I(∼ A). Desta forma, o
programa PI é um programa positivo estendido. Denotamos o menor ponto fixo de 3-TP
aplicado a PI por Γ∗ (I).
O exemplo a seguir mostra como é aplicada a transformação GL estendida.
Exemplo 2.5.12 Considere o mesmo programa P apresentado no exemplo 2.5.7:
work ← ∼ tired
sleep ← ∼ work
tired ← ∼ sleep
angry ← ∼ paid,work
paid ←
e a interpretação 3-valorada I = hpaid; angryi. A transformação GL estendida produz o
seguinte programa PI :
work ← u
sleep ← u
tired ← u
angry ← f, work
paid ←
E o menor ponto fixo do operador 3-TP aplicado a
37
P
I
é dado por Γ∗ (I) = I.
O exemplo anterior mostra que a partir da interpretação 3-valorada I não se deduziu
nenhum fato verdadeiro e nenhum fato falso que já não estivesse em I. Logo a interpretação I satisfaz a definição intuitiva de modelo 3-estável que é formalizada a seguir.
Definição 2.5.12 Uma interpretação 3-valorada M de um programa P é um modelo
3-estável se e somente se Γ∗ (M) = M.
Esta definição é uma extensão direta da definição de modelo estável (2-valorado) de
Gelfond e Lifschitz [GL88]. É mostrado em [Prz90] que quando o modelo 3-estável é uma
interpretação 3-valorada onde nenhum fato possui o valor-verdade u, então este modelo
coincide com o modelo estável. Programas que não possuem modelo estável possuem
modelo 3-estável como foi mostrado no exemplo 2.5.12.
Observação 2.5.2 (Grau de informação) Przymusinski diferencia duas ordens naturais entre as interpretações 3-valoradas. Uma delas, denotada por 4 (definição 2.5.9), é
chamada de ordem padrão, e a outra denotada por 4k , é chamada de ordem de conhecimento (também conhecida como ordem de Fitting), onde u 6k t, u 6k f, t e f são
incomparáveis.
A noção de modelo 4k minimal é diferente da noção de modelo minimal. Enquanto que
modelo minimal de um programa P minimiza o grau de verdade dos átomos pela minimização do conjunto de átomos positivos e maximização dos negativos; modelo 4k minimal
minimiza o grau de informação de seus átomos através da minimização do conjunto de
átomos positivos e negativos, e pela maximização dos indefinidos. Desta forma, pode se
dizer que o modelo MP que contém os fatos positivos e negativos que estão presentes em
todos os modelos 3-estáveis de um programa P é o modelo 4k minimal entre todos os
modelos 3-estáveis de P .
O principal resultado apresentado por Przymusinski [Prz90] é que a semântica bemfundada de todo programa P é dada pelo modelo 3-estável 4k minimal de P . Este resultado implica em todo programa possuir pelo menos um modelo 3-estável, e implica na
semântica bem-fundada de um programa P ser modelo 3-estável de P . Este resultado é
formalizado pelo seguinte teorema:
Teorema 2.5.4 ([Prz90]) Todo programa P possui um modelo 3-estável 4k minimal
denotado por MP . O modelo MP sempre coincide com a semântica bem-fundada de P , e
é chamado de modelo bem-fundado de P .
Desta forma, o modelo MP dado pela semântica bem-fundada para um programa P
é o mais cético de todos os modelos 3-estáveis, pois é o que possui maior quantidade de
38
fatos indefinidos. Pode se dizer que a semântica bem-fundada “acredita” somente nos
fatos que são sustentados em todos os mundos (os modelos 3-estáveis) do programa.
O próximo exemplo mostra um programa para o qual a semântica de modelo estável
não se aplica, e a semântica bem-fundada se aplica.
Exemplo 2.5.13 (Programa possui apenas a semântica bem-fundada) Considere
programa P do exemplo 2.5.8, mostrado a seguir:
p ←∼ q
q ←∼ p
O programa possui dois modelos estáveis: em um deles p é verdadeiro e q é falso, e no
outro p é falso e q é verdadeiro. Portanto o programa não possui uma semântica de modelo
estável. Entretanto a semântica bem-fundada de P é dada pela interpretação 3-valorada
onde p e q são indefinidos.
Os modelos 3-estáveis são extensões de modelos estáveis. Entretanto, a semântica
bem-fundada não estende a semântica de modelo estável. O próximo exemplo mostra que
o sentido contrário do teorema 2.5.2 não é válido. Existem programas para os quais a
semântica de modelo estável não coincide com a semântica bem-fundada.
Exemplo 2.5.14 Seja P o seguinte programa:
a ←∼ b
b ←∼ a
p ←∼ p
p ←∼ b
P possui um único modelo 2-estável, onde a e p são verdadeiros, e b é falso. Porém a
semântica bem-fundada de P é um modelo parcial e igual a vazio, ou seja, a, b e p são
indefinidos.
A definição de semântica bem-fundada apresentada nesta seção, apenas oferece um
mecanismo para identificar se determinada interpretação representa a semântica bemfundada de um programa P . Para se obter o modelo correspondente à semântica bemfundada, é necessário testar todas as possı́veis de interpretações 3-valoradas do programa,
identificar as que são modelos 3-estáveis, e então construir o modelo da semântica bemfundada com os fatos verdadeiros e falsos presentes em todos os modelos 3-estáveis de
P.
Métodos construtivos e mais eficientes do que a descrição anterior foram propostos
por Przymusinski [Prz89] e Van Gelder [Van89]. Ambos os métodos são baseados na
semântica do ponto fixo, e são descritos nas próximas seções.
2.5.4
39
Ponto fixo Reincidente para Semântica bem-fundada
Na seção anterior foi apresentada a definição de semântica bem-fundada baseada em
modelos 3-estáveis [Prz90]. Um método construtivo desta semântica é apresentado por
Przymusinski em [Prz89], e é descrito nesta seção.
As definições da lógica 3-valorada, programa, interpretação 3-valorada e modelos 3estáveis, encontram-se na seção anterior 2.5.3.
Seja P um programa e I uma interpretação 3-valorada. São definidos então, dois
operadores TI e FI que geram novos fatos não presentes em I a partir do programa P e
dos fatos já conhecidos que estão em I.
Definição 2.5.13 Sejam os conjuntos T e F de átomos instanciados. É definido que:
TI (T )={A| se existe regra do tipo A ← L1 , . . . , Lm em ground(P )6 e todo i 6 m, Li
é verdadeiro em I ou Li ∈ T }
FI (F )={A| se toda regra do tipo A ← L1 , . . . , Lm em ground(P ) e existe i 6 m, Li é
falso em I ou Li ∈ F }
Proposição 2.5.1 ([Prz89]) Os operadores TI e FI são monotônicos, isto é:
TI (T ) ⊆ TI (T 0 ) se T ⊆ T 0 ; e
FI (F ) ⊆ FI (F 0 ) se F ⊆ F 0 .
Os subconjuntos TI e FI denotam os menores pontos fixos, respectivamente, dos operadores TI e FI , e são obtidos de forma iterativa como definido a seguir:
Definição 2.5.14 Seja I = hT ; F i uma interpretação 3-valorada de um programa P .
Temos que:
TI0 = ∅
TIn+1 = TI (TIn )
TI =
[
TIn
n<ω
FI0 = B(P )
FIn+1 = FI (FIn )
FI =
\
FIn
n<ω
onde B(P ) denota o conjunto de átomos de P instanciados (base de Herbrand ).
Proposição 2.5.2 ([Prz89]) A sequência {TIn }n>0 é crescente, e a sequência {FIn }n>0 é
decrescente.
Intuitivamente temos que TI contém novos fatos verdadeiros que podem ser derivados
de P conhecendo-se I, e FI contém os fatos que são deduzidos como falsos a partir de P
e I.
6
O programa instanciado é denominado ground(P )
40
A partir de TI e FI é possı́vel definir o operador I, que estende a interpretação I para
I(I), adicionando-se à interpretação I os novos fatos verdadeiros de TI e os falsos de FI
que foram obtidos de P conhecendo-se I:
Definição 2.5.15 Seja I uma interpretação 3-valorada. É definido que:
I(I) = I ∪ hTI ; FI i
Proposição 2.5.3 ([Prz89]) O operador I(I) é monotônico.
Definição 2.5.16 O operador I(I) define a seguinte sequência de passos:
Mn+1
M0 = h∅; ∅i
= I(Mn ) , isto é, Mn+1 = Mn ∪ hTMn ; FMn i
[
Mα =
Mβ
β<α
A sequência {Mn }n>0 é monotonicamente crescente e converge para o menor ponto fixo
de I, denotado por MP .
O modelo MP denota o menor ponto fixo de I, que por sua vez é definido através dos
pontos fixos dos operadores TI e FI . Isto explica a denominação operador de ponto fixo
reincidente de P .
O próximo teorema comprova que o modelo MP obtido de modo construtivo, coincide
com o modelo fornecido pela semântica bem-fundada.
Teorema 2.5.5 ([Prz89]) O modelo MP é modelo minimal 3-valorado de P , e coincide
com a semântica bem-fundada de P .
O próximo exemplo mostra a aplicação do operador I.
Exemplo 2.5.15 (Cálculo do modelo ponto fixo reincidente) Considere o seguinte
programa P :
w(X) ← m(X, Y ), ∼ w(Y )
Intuitivamente temos que para resolver w(X) é preciso encontrar um Y tal que m(X, Y )
é verdadeiro e não é possı́vel resolver w(Y ). Suponha que inicialmente temos os fatos
{m(a, b), m(b, c), m(d, d)}. Os átomos relativos ao predicado m são omitidos pois são
fixos.
B(P ) = {w(a), w(b), w(d), m(a, b), . . .}.
M0 = h∅; ∅i
41
M1 = I(M0 ) , i. e. M1 = M0 ∪ hTM0 ; FM0 i
0
TM
=∅
0
1
0
2
TM0 = TM0 (TM
) = ∅ = TM
0
0
0
FM0 = B(P )
2
0
1
= FM0 (FM
) = {w(c)} = FM
FM
0
0
0
M1 = h∅; {w(c)}i
M2 = I(M1 ) , i. e. M2 = M1 ∪ hTM1 ; FM1 i
0
TM
=∅
1
1
0
2
TM
= TM1 (TM
) = {w(b)} = TM
1
1
1
0
FM
=
B(P
)
1
1
0
2
FM
= FM1 (FM
) = {w(c)} = FM
1
1
1
M2 = h{w(b)}; {w(c)}i
M3 = I(M2 ) , i. e. M3 = M2 ∪ hTM2 ; FM2 i
0
TM
=∅
2
1
0
2
TM2 = TM2 (TM
) = {w(b)} = TM
2
2
0
FM
=
B(P
)
2
1
0
2
FM
= FM2 (FM
) = {w(a), w(c)} = FM
2
2
2
M3 = h{w(b)}; {w(a), w(c)}i = M4
Portanto, o modelo M3 é o modelo MP , e coincide com o modelo bem-fundado de P , onde
w(b) é verdadeiro, w(a) e w(c) são falsos, e w(d) é indefinido.
2.5.5
Ponto fixo Alternante para Semântica bem-fundada
Nesta seção é apresentada outra definição construtiva da semântica bem-fundada [Prz90]
(descrita na seção 2.5.3), que foi proposta por Van Gelder em [Van89].
A idéia intuitiva do método apresentado em [Van89], é construir monotonicamente um
conjunto de fatos negativos até se chegar a um ponto fixo. A partir deste conjunto de
fatos negativos são deduzidos fatos positivos. A união do conjunto de fatos positivos com
o conjunto de fatos negativos forma um conjunto que coincide com o modelo definido pela
semântica bem-fundada.
A definição do ponto fixo alternante trabalha com conjuntos de átomos, negados ou
não. Tais átomos pertencem ao conjunto de átomos instanciados do programa, denotado
por B(P ), ou base de Herbrand. Desta forma as instâncias são definidas como conjuntos
de literais (átomos ou átomos negados), e os átomos que não estão no conjunto são
considerados indefinidos.
A seguir são apresentadas definições de notações que serão utilizadas nesta seção.
Definição 2.5.17 Se I é um conjunto de literais, então ∼ I denota o conjunto de literais
42
de I complementados, do seguinte modo:
1) Para todo A ∈ I, temos ∼ A ∈∼ I;
2) Para todo ∼ A ∈ I, temos A ∈∼ I.
As operações + e − representam respectivamente as operações de união e diferença
entre conjuntos.
Exemplo 2.5.16 Seja I = {p, ∼ q} e J = {p, ∼ q, r, s}. Então:
∼ I = {∼ p, q},
I + J = {p, ∼ q, r, s},
J − I = {r, s}.
Definição 2.5.18 (Conjugado) O conjugado de um conjunto de literais é definido somente para conjuntos onde todos os literais são positivos ou todos são negativos do
seguinte modo:
1) Se I é um conjunto de literais positivos, então o seu conjugado é dado por:
Ī =∼(B(P )−I);
2) Se J é um conjunto de literais negativos, então o seu conjugado é dado por:
J̄ =B(P )−(∼ J).
É utilizada a convenção de se identificar os conjuntos de literais (ou instâncias) com o
sinal “∼” (ou “+”) sobreescrito, para indicar que se trata de um conjunto onde todos os
literais são negativos (ou positivos). Os sı́mbolos fazem parte dos identificadores, e não
representam a operação de negação (ou adição).
Na semântica de modelo estável [GL88] (descrita em 2.5.2) a instância I de um programa P é representada como um conjunto dos átomos instanciados positivos que são
verdadeiros na instância. Desta forma, o conjugado de I, denotado por Ī, é o conjunto
com os átomos instanciados negativos que são verdadeiros em I.
Exemplo 2.5.17 Seja I = {p, q} e B(P ) = {p, q, r, s}. Então:
Ī = {∼ r, ∼ s}.
Definição 2.5.19 A transformação de estabilidade S 0 é definida da seguinte maneira.
Seja P um programa e I∼ um conjunto de átomos negativos. O programa transformado
P 0 é obtido das regras de ground(P ), onde:
1) Literais negativos do tipo ∼ p, que ocorrem no corpo das regras, são considerados
como novos átomos identificados por ∼ p7 ;
2) É acrescentado ao programa transformado P 0 uma regra do tipo ∼ p ← para todo
∼ p ∈ I∼ .
7
Neste caso o sinal ∼ apenas faz parte do identificador do átomo.
43
Desta forma o programa transformado P 0 é um programa sem negação, e através do
operador de consequência imediata TP 0 , uma extensão direta de TP (definido em 2.4.6), é
possı́vel se chegar ao único modelo minimal de P 0 . O menor ponto fixo de TP 0 é denotado
por SP (I∼ ).
Definição 2.5.20 Seja P 0 um programa transformado e I uma instância. O operador
TP 0 (I) é definido por:
TP 0 (I) = {A | existe regra em ground(P ) do tipo A ← B1 , . . . , Bn onde
{B1 , . . . , Bn } ⊆ I},
onde é necessário que os literais negativos estejam explicitamente presentes em I.
Da mesma forma que o menor ponto fixo de TP pode ser obtido de forma iterativa,
o menor ponto fixo de TP 0 também pode ser obtido de forma construtiva a partir da
instância vazia, como é mostrado a seguir:
TP1 0 (∅) = TP 0 (∅)
TP2 0 (∅) = TP 0 (TP 0 (∅))
TP3 0 (∅) = TP 0 (TP2 0 (∅))
...
TP 0 ↑= sup{TPn0 }n>0
Definição 2.5.21 Seja P um programa e I∼ um conjunto de átomos negativos. SP (I∼ )
é o menor ponto fixo de TP 0 , onde P 0 é obtido da transformação S 0 de P e instância I∼ .
Ou seja, SP (I∼ ) = TP 0 ↑.
Exemplo 2.5.18 Seja o programa P descrito a seguir:
p ←∼ q
q ←∼ r
onde B(P ) = {p, q, r}.
Seja a instância M = {q}. O conjugado de M é dado por M = {∼ p, ∼ r}. Ou seja,
M é o conjunto dos átomos negativos que são verdadeiros segundo a instância M .
O programa transformado P 0 obtido de ground(P ) e instância I∼ = M , é mostrado a
seguir:
p ←∼ q
q ←∼ r
∼p←
∼r←
O cálculo iterativo de TP 0 é dado por:
44
TP 0 (∅) = {∼ p, ∼ r}
TP1 0 (∅) = {q, ∼ p, ∼ r} = TP2 0
TP 0 ↑= {q, ∼ p, ∼ r}.
Logo, SP (I∼ ) = {q, ∼ p, ∼ r}. Este resultado mostra que a partir do conjunto de fatos
negativos I∼ , foi derivado um único fato positivo (q) e o conjunto inicial de fatos negativos
({∼ p, ∼ r}).
A versão estendida do operador de transformação de estabilidade Sπ [GL88] (descrito
em 2.5.3) é definida a seguir:
Definição 2.5.22 Seja P um programa e I∼ um conjunto de fatos negativos. O operador
de transformação de estabilidade estendido S̄P (I∼ ) é definido por:
S̄P (I∼ ) = SP (I∼ ) =∼ (B(P ) − SP (I∼ )).
Exemplo 2.5.19 Continuando o exemplo 2.5.18, onde SP (I∼ ) = {q, ∼ p, ∼ r}, temos
que S̄P (I∼ ) = {∼ p, ∼ r} = I∼ .
Proposição 2.5.4 ([Van89]) Seja P um programa e M um conjunto de átomos positivos que representa uma instância de P . Seja M o conjugado de M .
Se S̄P (M ) = M então M é modelo estável de P .
Exemplo 2.5.20 A instância M dada no exemplo 2.5.18 é modelo estável de P .
O operador de ponto fixo alernatante é definido a seguir.
Definição 2.5.23 Seja P um programa e I∼ um conjunto de fatos negativos. O operador
de ponto fixo alternante denotado por AP (I∼ ) é definido por:
AP (I∼ ) = S̄(S̄P (I∼ ))
Proposição 2.5.5 ([Van89]) O operador AP (I∼ ) é monotônico.
A seguir é definido o modelo resultante da aplicação do operador ponto fixo alternante.
Definição 2.5.24 O menor ponto fixo do operador AP aplicado ao programa P e instância
I∼ é denotado por A∼ . É definido que A+ = SP (A∼ ), e o modelo do ponto fixo alternante
denotado por MAP é dado por MAP = (A+ + A∼ ).
Intuitivamente temos que A∼ é o conjunto de fatos negativos deduzidos do programa
P a partir da instância com os fatos negativos conhecidos inicialmente I∼ . A partir deste
conjunto A∼ é deduzido um conjunto de fatos positivos A+ , e a união destes conjuntos
resulta no modelo do ponto fixo alternante MAP . O modelo MAP coincide com o modelo definido pela semântica bem-fundada. Este resultado importante é formalizado no
próximo teorema.
45
Teorema 2.5.6 (Modelo bem-fundado) O modelo produzido pela aplicação operador
ponto fixo alternante AP coincide com a semântica bem-fundada.
Exemplo 2.5.21 (Cálculo do modelo ponto fixo alternante) Considere o mesmo programa P do exemplo 2.5.15:
w(X) ← m(X, Y ), ∼ w(Y )
Suponha que inicialmente temos os fatos {m(a, b), m(b, c), m(d, d)}. Desta forma, B(P ) =
{w(a), w(b), w(c), w(d), m(a, b), . . .}. Os átomos relativos ao predicado m serão omitidos
uma vez que eles são fixos.
O programa instanciado ground(P ) é descrito a seguir:
w(a) ← m(a, b), ∼ w(b)
w(b) ← m(b, c), ∼ w(c)
w(d) ← m(d, d), ∼ w(d)
Vamos calcular a sequência definida pela aplicação do operador AP mostrada a seguir:
I∼
0 = ∅
∼
I1 = S̄P (I∼
0)
1
∼
AP = I2 = S̄P (I∼
1)
∼
I∼
3 = S̄P (I2 )
∼
A2P = I∼
4 = S̄P (I3 )
...
∼
I∼
1 = S̄P (I0 )
SP (I∼
↑= ∅
0 ) = TP ∪I∼
0
∼
I1 =∼ (B(P ) − SP (Ī0 )) = {∼ w(a), ∼ w(b), ∼ w(c), ∼ w(d)}
∼
I∼
2 = S̄P (I1 )
SP (I∼
↑= {w(a), w(b), w(d), ∼ w(a), ∼ w(b), ∼ w(c), ∼ w(d)}
1 ) = TP ∪I∼
1
∼
I∼
2 =∼ (B(P ) − SP (I1 )) = {∼ w(c)}
A1P (∅) = {∼ w(c)}
∼
I∼
3 = S̄P (I2 )
↑= {w(b), ∼ w(c)}
SP (I∼
2 ) = TP ∪I∼
2
∼
I3 =∼ (B(P ) − SP (I∼
2 )) = {∼ w(a), ∼ w(c), ∼ w(d)} = Ī5
∼
I∼
4 = S̄P (I3 )
↑= {w(b), w(d), ∼ w(a), ∼ w(c), ∼ w(d)}
SP (I∼
3 ) = TP ∪I∼
3
∼
I∼
4 =∼ (B(P ) − SP (I3 )) = {∼ w(a), ∼ w(c)} = Ī6
46
A2P (∅) = {∼ w(a), ∼ w(c)} = A3P (∅)
∼
∼
∼
∼
Como I∼
5 = I3 e I4 = I6 , então I4 é o ponto fixo de AP .
A∼ = {∼ w(a), ∼ w(c)}
A+ = SP (A− ) = {w(b)}
Portanto o modelo do ponto fixo alternante é {∼ w(a), w(b), ∼ w(c)}, e este é também
o modelo fornecido pela semântica bem-fundada. Nesta representação os fatos omitidos,
como w(d), são associados ao valor-verdade indefinido.
2.6
Conclusão do capı́tulo
Neste capı́tulo foram introduzidos os fundamentos teóricos que são importantes para a
compreensão da definição de P-Datalog¬ . Na primeira seção foram apresentados conceitos
algébricos utilizados na programação em lógica. Em seguida, na seção 2.2, foi apresentada
uma classificasção de programas na programação em lógica, segundo a qual os programas
P-Datalog¬ , definidos no capı́tulo 4, são da classe de programas lógicos padrões, ou seja,
programas que aceitam a negação por default somente no corpo de suas regras.
Na seção 2.3 foi descrita a lógica paraconsistente LFI1, a lógica base de P-Datalog¬ .
Os programas P-Datalog¬ são formados por regras que podem ser associadas a fórmulas
fechadas da lógica LFI1.
A linguagem de consultas P-Datalog¬ é uma extensão da linguagem Datalog¬ , que por
sua vez, é uma extensão de Datalog, como mostra a Figura 1.1. A linguagem de consultas
Datalog, sua sintaxe, suas diferentes abordagens semânticas e métodos de avaliação, foram
descritas na seção 2.4. Em seguida, na seção 2.5, foi introduzida a linguagem Datalog¬ e
sua semântica bem-fundada, juntamente com métodos construtivos para obtenção desta
semântica bem-fundada.
Capı́tulo 3
Trabalhos Relacionados
O tratamento de inconsistências tem sido um assunto amplamente abordado em trabalhos
de pesquisa. Alguns são diretamente relacionados com a integração de banco de dados e
outros relacionados com a programação em lógica como representação do conhecimento.
Neste capı́tulo são apresentadas propostas de tratamento de informações inconsistentes
na programação em lógica (seção 3.1), e na integração de dados (seção 3.2).
3.1
Inconsistência na programação em lógica
O poder de expressão dos programas lógicos tem sido enriquecido com a adição à sua
sintaxe da negação tanto no corpo como na cabeça das regras, e também devido a inclusão de mais de um tipo de negação. Tais avanços implicam em novas maneiras de se
representar e processar o conhecimento através de programas lógicos.
A avaliação de consultas à base de dados é mais precisa, uma vez que é possı́vel
distinguir entre a consulta que falha porque não sucede (negação por default), e a que
falha num sentido mais forte, quando a negação sucede (negação explı́cita). Outro avanço
importante é a possibilidade de se representar e se raciocinar na presença de informações
conflitantes, pois a presença de literais positivos e negativos na cabeça das regras pode
gerar informações contraditórias que devem ser tratadas de alguma forma: eliminando-as
ou mantendo-as e ainda assim conseguir raciocinar.
É importante ressaltar que apesar da linguagem P-Datalog¬ , descrita em detalhes no
capı́tulo 4, não permitir literais negativos na cabeça das regras, as instâncias do banco
de dados contém inconsistências, e portanto a semântica de P-Datalog¬ também deve ser
capaz de raciocinar na presença da inconsistência.
Segundo [DP98], existem diferentes maneiras de se tratar a inconsistência na programação em lógica:
• Abordagem da revisão de crença (Belief revision): o programa é corrigido
de maneira que as inconsistências são eliminadas.
47
CAPÍTULO 3. TRABALHOS RELACIONADOS
48
• Abordagem paraconsistente: a semântica aceita as contradições e o processo de
dedução consegue lidar com a presença de inconsistências.
A informação contraditória pode ocorrer devido a algum erro na especificação e é
desejável que o erro seja corrigido. Neste caso as técnicas baseadas na abordagem da
revisão de crença devem ser utilizadas. Em outras situações a informação fornecida é por
si só contraditória e não deve ser corrigida. Neste caso é necessário um mecanismo de
dedução paraconsistente.
Entretanto, para se executar uma correção pela abordagem da revisão de crença é
necessário detectar a inconsistência e sua origem numa primeira etapa. Ou seja, um
mecanismo paraconsistente é um passo intermediário para se executar a correção pela
abordagem da revisão de crença.
Uma extensa pesquisa sobre diversas semânticas paraconsistentes( [Sak92, PA92, BS87]
e outras), é apresentada em [DP98], com enfoque nas semânticas bem-fundadas e de modelos estáveis. Em [Sak92] e [PA92], são apresentadas extensões da semântica bem-fundada
para programas lógicos estendidos, definida por Przmusinski [Prz90]. A semântica [Sak92],
ao contrário da semântica de Przymusinski, adota uma abordagem paraconsistente, e
baseia-se em uma lógica 7-valorada. Os trabalhos de Blair e Subrahmanian [BS87, CS89]
foram pioneiros na introdução da paraconsistência na programação em lógica. Neles é proposto um tratamento de informações contraditórias de modo coerente, sem a trivialização
do processo dedutivo. A semântica apresentada em [BS87] é descrita a seguir.
3.1.1
Semântica 4-valorada de programa lógico geral
Nesta seção é apresentada a semântica de programas lógicos gerais proposta por Blair e
Subrahmanian em “Paraconsistent Logic Programming” [BS87], onde podem ser encontrados maiores detalhes sobre os resultados apresentados e suas demonstrações.
Em [BS87], Blair e Subrahmanian propõem transformar um programa lógico geral em
um programa sem negação, pela substituição dos sı́mbolos de negação por átomos anotados (annotated atoms). Para possibilitar a representação de informações inconsistentes e
também das informações incompletas, é utilizada a lógica 4-valorada de Belnap [Bel77].
Lógica 4-valorada FOUR
Quando a negação é permitida na cabeça das regras, os programas podem ser inconsistentes pois podem deduzir fatos do tipo ¬A e A. Para representar a semântica destes
programas onde os fatos podem ser verdadeiros, falsos, indefinidos ou contraditórios, é
necessária uma lógica pelo menos 4-valorada. Uma das mais conhecidas lógicas 4-valoradas
é a lógica FOUR (figura 3.1), definida por Belnap [Bel77], onde temos o conjunto de
valores-verdade T ={⊥, f, t, >}, cujos elementos representam respectivamente os valores
¡¡
¡¡
¡
¡
¡¡
f>
>>
>>
>>
>
49
>=
==
==
==
=
⊥
¢
¢¢
¢
¢¢
¢¢
t
Figura 3.1: Lógica 4-valorada FOUR
indeterminado, falso, verdadeiro e contraditório. A ordem entre os valores do conjunto T
é dada por:
∀xy ∈ T x 4 y ⇔ x = y ∨ x = ⊥ ∨ y = >
de forma que o conjunto T e a ordem 4 formam um reticulado completo (veja seção 2.1.2).
Os literais anotados são introduzidos na definição seguinte.
Definição 3.1.1 Seja A um literal, isto é, um átomo ou a negação de um átomo. Então
A : µ é chamado de literal anotado, onde µ ∈ T e µ é chamado de anotação de A. Se
µ ∈ {t, f}, então A : µ é chamado de literal bem anotado, e µ de anotação-w.
O significado intuitivo de um literal bem anotado A : t é “A é conhecido como verdadeiro”. Da mesma forma A : f possui o significado intuitivo de “A é conhecido como
falso”. Note que tanto A : t quanto A : f são literais positivos anotados (não são precedidos pelo sı́mbolo de negação), mesmo que A : f contenha uma informação negativa.
As fórmulas anotadas consideradas são fórmulas bem formadas [Sou02] com a adição
dos literais anotados descritas indutivamente a seguir.
Definição 3.1.2 (Fórmulas)
1) Um átomo anotado é um literal positivo anotado.
2) Todo átomo anotado é uma fórmula anotada.
3) Se A : µ é um átomo anotado, então ¬A : µ é uma fórmula anotada.
4) Se F1 , F2 são fórmulas anotadas, então F1 ∧ F2 , F1 ∨ F2 , F1 ← F2 , F1 ↔ F2 são
fórmulas anotadas.
5) Se F é uma fórmula e x uma variável, então ∀xF e ∃xF são fórmulas anotadas.
Um programa cujos literais são anotados é chamado de programa Horn generalizado,
como é definido a seguir.
Definição 3.1.3 (Programa Horn generalizado GHP) Um programa Horn generalizado denotado por GHP é um conjunto finito de cláusulas do tipo:
A0 : µ0 ← A1 : µ1 , . . . , An : µn
50
onde A0 , . . . , An são literais e µ0 , . . . , µn são anotações-w. Este tipo de cláusula é denominada cláusula-gh.
Note que no programa GHP só aparecem anotações-w cujos valores-verdade são sempre f ou t.
Exemplo 3.1.1 O programa seguinte é um exemplo de um programa GHP.
¬p(a) : t ← p(b) : f
p(a) : f ← p(b) : t
p(b) : t ← p(a) : f
p(b) : f ← ¬p(a) : f
Semântica dos programas GHP
As interpretações de um programa GHP P são mapeamentos de B(P ) → T , onde B(P )
denota o conjunto de átomos instanciados do programa P (base de Herbrand).
A negação de uma anotação é definida por: ¬t = f, ¬f = t, ¬⊥ = ⊥ e ¬> = >.
Definição 3.1.4 Uma interpretação I satisfaz uma sentença1 F , denotado por I |= F de
acordo com:
1)
2)
3)
4)
5)
6)
7)
8)
I |= A : µ se e somente se I(A) < µ,
I |= ¬A : µ se e somente se I |= A : ¬µ,
I |= F1 ∧ F2 se e somente se I |= F1 e I |= F2 ,
I |= F1 ∨ F2 se e somente se I |= F1 ou I, |= F2 ,
I |= F1 ← F2 se e somente se I 6|= F2 ou I |= F1 ,
I |= F1 ↔ F2 se e somente se I |= F1 ← F2 e I |= F2 ← F1 ,
I |= (∀x)F se e somente se I |= F 0 para toda instanciação F 0 de F ,
I |= (∃x)F se e somente se I |= F 0 para alguma instanciação F 0 de F .
onde F , F1 , F2 são sentenças.
A definição de modelo de programa GHP é dada a seguir.
Definição 3.1.5 Uma interpretação I é modelo de um programa GHP P se e somente se
I satisfaz todas as cláusulas-gh pertencentes a P .
Definição 3.1.6 (Instância e modelo) Seja o programa GHP G descrito a seguir:
p(a) : t ← p(b) : f
p(b) : t ← p(a) : f
1
Sentenças são fórmulas sem variáveis livres.
51
Sejam I1 , I2 e I3 interpretações de G onde:
I1 (p(a)) = f
I2 (p(a)) = f
I3 (p(a)) = ⊥
I1 (p(b)) = t;
I2 (p(b)) = f;
I3 (p(b)) = ⊥.
As interpretações I1 e I3 são modelos de G, porém I2 não é modelo de G.
A ordem natural entre as instâncias I1 e I2 de um dado programa GHP P é dada por:
I1 4 I2 se e somente se ∀A ∈ B(P ), I1 (A) 4 I2 (A)
O conjunto de interpretações do programa GHP P , denotado por InstP e a ordem 4
formam um reticulado completo.
Na seção 2.5 foram apresentadas duas semânticas de programas Datalog¬ que têm
em comum o uso de alguma forma de transformação do programa com negação em um
programa sem negação, e então é aplicado um operador que é uma extensão do operador
de consequência imediata TP (definido em 2.4.6) para construir o modelo minimal. Blair
e Subrahmanian propõem um esquema similar, onde é feita a substituição dos literais
negativos (precedidos pelo sı́mbolo de negação) no programa por átomos anotados, e
depois definem um operador TG que é uma extensão do operador TP .
A definição seguinte mostra como os sı́mbolos de negação que precedem os literais do
programa são substituı́dos por anotações.
Definição 3.1.7 Se C é uma cláusula-gh de um programa GHP G, então o resultado
da substituição de todos os literais negados do tipo ¬A : µ de C por A : ¬µ é chamada
de contraparte positiva de C e denotada por C pos . O programa GHP Gpos é obtido pela
substituição de toda cláusula-gh C do programa GHP G por C pos .
O próximo teorema assegura que o esquema de átomos anotados é suficiente para
substituir os átomos negados pela negação implı́cita na forma de átomos anotados com o
valor-verdade f.
Teorema 3.1.1 ([BS87]) Uma interpretação I é modelo do programa GHP G se e somente se I é modelo de Gpos .
O programa Gpos definido anteriormente não possui literais negativos (a negação
está implı́cita na forma da anotação associada ao átomo). Assim como na definição
da semântica de programas Datalog, que são programas sem negação, foi mostrado que
é possı́vel obter o seu modelo minimal através do operador TP (definido em 2.4.6), para
programas Gpos é definido uma extensão deste operador.
52
Definição 3.1.8 Seja Gpos um programa GHP. Então TG é um mapeamento de InstP
para InstP definido por:
TG (I)(A) = sup{µ|A : µ ← B1 : µ1 , . . . , Bk : µk é uma cláusula-gh instanciada de Gpos , e
I |= B1 : µ1 , . . . , Bk : µk }.
Desta forma, o valor-verdade µ de A corresponde ao menor limitante superior de todos
os µs das cláusulas-gh onde A é cabeça, e o corpo é satisfeito em I.
De forma análoga ao desenvolvimento apresentado para a semântica do ponto fixo
de programas Datalog sem negação na seção 2.4, onde as propriedades do operador TP
(definido em 2.4.6) são apresentadas, resultados similares serão mostrados para o operador
TG de forma sucinta. Os resultados apresentados a seguir e as suas demonstrações são
encontrados em [BS87].
Lema 3.1.1 ([BS87]) Seja Gpos um programa GHP. Temos, então, os seguintes resultados:
• O operador TG é monotônico;
• Uma instância I é um modelo de Gpos se e somente se TG (I) 4 I;
Teorema 3.1.2 ([BS87]) Todo programa GHP Gpos possui um modelo minimal MG .
MG coincide com o menor ponto fixo de TG .
A próxima definição mostra que TG ao ser aplicado de forma iterativa, a partir da
instância inicial onde todos os átomos possuem o valor-verdade igual a ⊥, define uma
sequência crescente.
Definição 3.1.9 O operador TG calculado de forma iterativa é mostrado a seguir:
TG0 = ⊥
TGn = TG (TGn−1 )
TG ↑= sup{TGn }n>0
O operador TG é monotônico e, desta forma podemos definir a seguinte sequência crescente:
TG0 4 TG1 4 . . . 4 TG ↑.
O modelo minimal MG do programa GHP Gpos pode ser construı́do iterativamente
pela sequência definida em 3.1.9 pois TG ↑ corresponde ao menor ponto fixo de TG , como
mostra o próximo teorema.
53
Teorema 3.1.3 ([BS87]) Seja Gpos um programa GHP e MG o seu modelo minimal.
Então temos que TG ↑= MG .
Exemplo 3.1.2 (Aplicação do operador TG ) Considere o seguinte programa G:
p(a) : t ← q(a) : f, r(a) : t
p(b) : t ← q(b) : f, r(b) : t
p(c) : t ← q(c) : f, r(c) : t
q(a) : t ←
r(a) : t ←
r(b) : f ←
q(b) : f ←
r(a) : f ←
r(c) : t ←
q(c) : f ←
O cálculo do menor ponto fixo a partir da instância ⊥ é descrito a seguir:
TG↑ = TG3 =
TG0
TG1
TG2
=
=
=
p(a)
⊥
⊥
⊥
p(b) p(c) q(a)
⊥
⊥
⊥
⊥
⊥
t
⊥
t
t
q(b)
⊥
f
f
q(c) r(a) r(b) r(c)
⊥
⊥
⊥
⊥
f
>
f
t
f
>
f
t
A semântica de programas GHP é definida da seguinte forma:
Definição 3.1.10 (Semântica de programas GHP) A semântica do programa GHP
G é definida pelo modelo minimal de Gpos . Este modelo coincide com o menor ponto fixo
do operador TG do programa Gpos de acordo com o teorema 3.1.3.
Um programa GHP G e sua interpretação, descritos através de literais anotados,
podem ser traduzidos para um programa e interpretação sem as anotações, através de um
procedimento apresentado em [DP98], e descrito a seguir.
Tradução de GHP para programa lógico geral
Seja um programa GHP Gpos e uma cláusula-gh arbitrária de Gpos da forma
A0 : µ0 ← A1 : µ1 , . . . , An : µn .
O corpo da cláusula-gh é transformado em uma conjunção de literais denotada por Body,
onde cada literal anotado Ai : t (Ai : f) é substituı́do por Ai (¬Ai ) respectivamente.
O programa QGHP é construı́do a partir de cada uma das cláusulas-gh de Gpos do
modo descrito a seguir:
1) Se µ0 = ⊥ então nada é adicionado a QGHP .
2) Se µ0 =f (µ0 =t) então é adicionada a regra ¬A0 ← Body (A0 ← Body) respectivamente.
3) Se µ0 = > então as duas regras ¬A0 ← Body e A0 ← Body são adicionadas ao programa
QGHP .
Desta forma, QGHP é um programa lógico geral pois pode apresentar literais negativos
tanto no corpo quanto na cabeça das regras.
A relação entre uma instância G de um programa Gpos e uma instância 3-valorada
(definida em 4.2.1) M é dada por:
G(A) = ⊥
G(A) = t
G(A) = f
G(A) = >
se
se
se
se
e
e
e
e
somente
somente
somente
somente
se
se
se
se
54
A 6∈ M
A∈M
A 6∈ M
A∈M
e
e
e
e
¬A 6∈ M
¬A 6∈ M
¬A ∈ M
¬A ∈ M
Exemplo 3.1.3 (Traduzindo GHP ) Considere a tradução do programa GHP G do
exemplo 3.1.2 para um programa QGHP :
p(a) ← ¬q(a), r(a)
p(b) ← ¬q(b), r(b)
p(c) ← ¬q(c), r(c)
q(a) ←
r(a) ←
¬r(b) ←
¬q(b) ←
¬r(a) ←
r(c) ←
¬q(c) ←
A instância 3-valorada correspondente ao resultado TG ↑ é:
{ p(c), q(a), ¬q(b), ¬q(c), r(a), ¬r(a), ¬r(b), r(c)}.
Nesta representação os átomos com valor-verdade indefinido, e os contraditórios são representados da forma A e ¬A, como ocorre com o átomo r(a).
Discussão
A semântica de P-Datalog¬ , que será descrita no capı́tulo 4, também utiliza uma lógica 4valorada, porém a ordem entre os valores-verdade é dada por f 6 u 6 i 6 t (os valores u e i
correspondem a ⊥ e >). Intuitivamente, temos que o valor u (indefinido) é uma indicação
mais fraca da presença de um fato no banco de dados do que o valor i (inconsistente). A
semântica de P-Datalog¬ é uma extensão da semântica bem-fundada de Datalog¬ (seção
2.5.3).
A semântica de programas GHP assume que todo fato que não possa ser provado é
considerado indefinido, enquanto que na semântica de P-Datalog¬ ele pode ter um valor
assumido por default, como mostra o exemplo seguinte.
Exemplo 3.1.4 Considere o seguinte programa lógico geral P :
p ← ¬q
q←
O programa GHP G correspondente ao programa P é mostrado a seguir:
p:t←q:f
q:t←
Calculamos o menor ponto fixo de TG :
TG↑
= TG2 =
TG0
TG1
=
=
p q
⊥ ⊥
⊥ t
55
Portanto, a semântica de programas GHP produz o modelo que diz que q é verdadeiro e p
é indefinido, pois não existe regra com ¬p na cabeça, e desta forma não é possı́vel afirmar
que p é falso.
Se considerarmos o programa P como um programa P-Datalog¬ , e mudarmos a negação
para a negação por default, o modelo produzido pela semântica de P-Datalog¬ dirá que q
é verdadeiro e p é falso.
3.2
Inconsistência na integração de fontes de dados
O problema da ocorrência de informações inconsistentes que surgem do processo de integração de fontes heterogêneas de dados, tem sido extensamente abordado em várias
pesquisas [ABC99, ABK00, ABC03, dACM02, CG01, Cho98, Sub94]. Assim como foi
descrito na seção anterior, a inconsistência na integração de fontes de dados é tratada segundo a perspectiva da revisão de crença, ou segundo a perspectiva paraconsistente. Nas
próximas seções são descritos dois trabalhos, cada um com uma abordagem diferente,
apresentados em [CG01] e em [ABC99]. O primeiro trabalho trata a integração de fontes
de dados sob a perspectiva da revisão de crença, enquanto que o segundo apresenta uma
abordagem paraconsistente.
3.2.1
Abordagem da revisão de crença na integração
Nesta seção é descrita a proposta de Cholvy e Garion [CG01] que propõe uma lógica sob
a perspectiva da revisão de crença (belief revision), capaz de raciocinar e integrar dados
provenientes de diversas fontes de informação.
Na integração de dados, as informações podem ser vistas como crenças que as fontes
tem sobre o mundo real. Neste caso podemos dizer que o objetivo do processo de integração é aperfeiçoar a nossa percepção do mundo real através da compilação das diferentes
crenças fornecidas pelas fontes de informação.
Quando lidamos com múltiplas fontes de informação existe a possibilidade de ocorrência
de inconsistências entre as fontes, e o processo de integração de fontes deve tratar de alguma forma estas possı́veis inconsistências. Cholvy e Garion argumentam que muitas
vezes o processo de integração depende de informações adicionais sobre as fontes a serem
integradas como, por exemplo, o grau de confiabilidade de cada uma delas (quanto mais
confiável for a fonte de informação, mais de acordo com ela deve estar o resultado do processo de integração). Entretanto, se este tipo de informação adicional, também chamado
de meta-informação, não é conhecido, então é preciso definir outro critério para a integração de fontes de informação.
Cholvy e Garion citam dois operadores definidos por Konieczny e Pino-Perez [KPP98]
que podem ser utilizados como critério no processo de integração: o operador de maioria
56
e o de consenso. A diferença intuitiva entre um operador de maioria e um de consenso é
que o operador de consenso tenta negociar um resultado que agrade ao máximo possı́vel de
fontes, enquanto que um operador de maioria escolhe, como resultado da integração, o que
é acreditado pela maioria das fontes. Ou seja, o operador de consenso tenta minimizar a
insatisfação individual, enquanto que o de maioria tenta minimizar a insatisfação global.
Por exemplo, José, Pedro e Carlos têm que dedidir o que farão à noite. José e Pedro
querem ir ao restaurante e ao cinema. Carlos não que sair, não quer ir ao restaurante e nem
ao cinema. Um operador de maioria determinaria que o grupo sairia para o restaurante e
o cinema, enquanto que o de consenso definiria que o grupo iria ou ao restaurante ou ao
cinema, mas não aos dois lugares. Desta forma, cada membro do grupo seria satisfeito o
máximo possı́vel.
A partir do operador de maioria é definida a lógica MF que permite raciocinar com
os dados provenientes de diversas fontes de informações, e possibilita a integração destes
dados de acordo com o operador de maioria.
Em [CG01], Cholvy e Garion definem a linguagem da lógica MF, sua semântica segundo a teoria de modelos e segundo a teoria da prova. A semântica de MF é um tipo
de semântica de Kripke da lógica modal. Como a lógica modal foge do escopo desta
dissertação, maiores informações sobre este assunto podem ser encontradas em [Che80].
A lógica MF e o seu sistema axiomático2 são descritos a seguir.
A lógica MF
A lógica MF é definida para que seja possı́vel raciocinar com a fonte de informação resultante da integração de várias fontes. As fontes de informação são vistas como conjuntos
de literais, e representam intuitivamente, diferentes crenças sobre o mundo real. Desta
forma, a integração de fontes de informação pode ser vista como um multi-conjunto, cuja
definição é dada a seguir.
Definição 3.2.1 Um multi-conjunto M S é um conjunto onde ocorrências redundantes
são aceitas, e a relação de pertinência é dada por S ∈i M S , onde i é um inteiro que
representa o número ocorrências do elemento S em M S. A notação S ∈0 M S representa
o caso em que S 6∈ M S.
F
Sejam M S1 = [S1 , . . . , Sn ] e M S2 = [Sn+1 , . . . , Sm ] dois multi-conjuntos. M S1 M S2 =
[S1 , . . . , Sm ] é a união de M S1 e M S2 .
Sejam db1 e db2 duas fontes de informação. A fonte de informação obtida da integração
F
de db1 e db2 é denotada por db1 + db2 , que é igual a db1 db2 .
2
Um sistema axiomático é constituı́do por um conjunto de fórmulas e regras de inferência que permitem
a representação e dedução de conhecimento [Sou02].
57
Exemplo 3.2.1 Considere as seguintes fontes de dados: db1 = {a, b}, db2 = {a, ¬c} e
db3 = {¬a, c}. A integração destas fontes de dados, denotada por (db1 +db2 )+db3 , produz
o multiconjunto M descrito a seguir:
M = [a, b, a, ¬c, ¬a, c],
onde a ∈2 M , b ∈1 M , c ∈1 M , ¬a ∈1 M , ¬b ∈1 M .
Seja L a linguagem definida pela lógica proposicional [Sou02]. A linguagem da lógica
MF, denotada por L0 , é obtida de L adicionando-se operadores modais [Che80], como
mostra a definição seguinte.
i
Definição 3.2.2 (Fórmulas de L0 ) Sejam Bdb
e Bdb operadores modais, i um número
inteiro e db uma fonte de informação. Temos que:
i
1) Se F é uma fórmula de L, então Bdb
F e Bdb F são fórmulas de L0 .
2) Se F1 e F2 são fórmulas de L0 então ¬F1 , F1 ∧ F2 são fórmulas de L0 . E as fórmulas
F1 ∨ F2 e F1 → F2 são definidas a partir de ∧, ¬, da forma usual.
Sejam db1 e db2 duas fontes de informação. Então:
1
Bdb
a
1
0
Bdb2 a
1
Bdb
a
1 +db2
Bdb1 +db2 a
indica
indica
indica
indica
que
que
que
que
db1 possui uma ocorrência de a;
db2 não possui ocorrência de a;
db1 + db2 possui uma ocorrência de a;
db1 + db2 acredita em a.
A seguir é formalizado um esquema axiomático para a lógica MF. Este sistema é
correto e completo em relação à semântica de MF [CG01]. Como foi dito, a semântica
de MF é um tipo de semântica de Kripke da lógica modal, e não será descrita nesta
dissertação. É possı́vel compreender o significado dos operadores modais introduzidos,
através do sistema axiomático descrito a seguir.
Nas definições seguintes, db e db0 são fontes de informação; F e G são fórmulas de L;
L, L1 , L2 , . . . são literais de L; e i, j, k são inteiros.
Os axiomas3 da lógica MF são:
(A0 ) Axiomas da lógica proposicional [Sou02]
(A1 ) Bdb ¬F → ¬Bdb F
(A2 ) Bdb F ∧ Bdb (F → G) → Bdb G
j
i
(A3 ) Bdb
L → ¬Bdb
L se i 6= j
j
i
k
(A4 ) Bdb L ∧ Bdb0 L → Bdb+db
se k = i + j
0L
j
i
(A5 ) Bdb L ∧ Bdb ¬L → Bdb L se i > j
i
i
(A6 ) Bdb
L ∧ Bdb
¬L → ¬Bdb L
3
Um axioma é uma fórmula que representa um conhecimento dado a priori, a partir do qual novos
conhecimentos podem ser deduzidos [Sou02].
58
(A7 ) Bdb (L1 ∨ . . . ∨ Ln ) → Bdb L1 ∨ . . . ∨ Bdb Ln onde Li 6= Lj
As regras de inferência são:
(1) Se `M F F e `M F (F → G) então `M F G (Modus Ponens).
(2) Se `M F F então `M F Bbd F para todo Bbd .
A notação `M F F denota que F é teorema de MF, isto é, uma fórmula que é instância
de um axioma ou que foi deduzida dos axiomas e regras de inferência.
O significado intuitivo de alguns dos axiomas anteriores é dado a seguir:
(A3 ) diz que o número de ocorrências de um literal em uma fonte de informação é
único;
(A4 ) indica que o número de ocorrências de um literal, na fonte obtida da integração
de duas outras fontes de informação, é dado pela soma dos números de ocorrências deste
literal em cada uma das fontes integradas;
(A5 ) e (A6 ) mostram o operador de maioria sendo aplicado. O axioma (A6 ) mostra que
quando a inconsistência é detectada ela é eliminada: a fonte de informação não acredita
no literal contraditório;
A lista de informações relativas ao conteúdo de cada fonte de informação a ser integrada
é representada pela fórmula ψ definida a seguir.
Definição 3.2.3 (Fórmula ψ) Sejam db1 , . . . , dbn n conjuntos consistentes de literais L
a serem integrados. A fórmula ψ é definida da seguinte forma:
n
^
^
^
0
1
L)
Bdb
Bdb
L
∧
ψ= (
i
i
i=1 L∈dbi
L6∈dbi
Note que pela definição anterior cada literal está presente ou não em uma dada fonte
dbi , e portanto é representado sempre com o número de ocorrências igual a 0 ou 1.
O próximo resultado mostra que o conhecimento deduzido da fórmula ψ é consistente.
Proposição 3.2.1 ([CG01]) Para uma dada fórmula ψ, uma fórmula F de L e uma
fonte de informação db, temos que:
6`M F ψ → Bdb F ou 6`M F ψ → ¬Bdb F ; e
`M F ψ → Bdb F ou `M F ψ → ¬Bdb F .
O exemplo seguinte mostra resultados obtidos da aplicação do sistema axiomático de
MF à fonte de informação obtida da integração de diversas fontes.
Exemplo 3.2.2 (Dedução em MF) Considere as fontes de dados do exemplo 3.2.1:
db1 = {a, b}, db2 = {a, ¬c} e db3 = {¬a, c}.
A fórmula ψ, derivada da integração das fontes db1 , db2 e db3 , é dada por:
59
1
1
0
0
0
0
ψ =Bdb
a ∧ Bdb
b ∧ Bdb
c ∧ Bdb
¬a ∧ Bdb
¬b ∧ Bdb
¬c∧
1
1
1
1
1
1
1
0
0
0
0
1
Bdb2 a ∧ Bdb2 b ∧ Bdb2 c ∧ Bdb2 ¬a ∧ Bdb2 ¬b ∧ Bdb2 ¬c∧
0
0
1
1
0
0
Bdb
a ∧ Bdb
b ∧ Bdb
c ∧ Bdb
¬a ∧ Bdb
¬b ∧ Bdb
¬c
3
3
3
3
3
3
Da fórmula ψ, e aplicando-se os axiomas da lógica MF, temos os seguintes teoremas:
2
(1) `M F ψ → Bdb
a (de A4 )
1 +db2
2
(2) `M F ψ → B(db1 +db2 )+db3 a (de A4 e (1))
0
¬a (de A4 )
(3) `M F ψ → Bdb
1 +db2
1
(4) `M F ψ → B(db
¬a (de A4 e (3))
1 +db2 )+db3
De (2), (4) e A5 deduzimos que:
(5) `M F ψ → B(db1 +db2 )+db3 a.
Este teorema nos diz que a fonte de informação obtida pela integração das fontes db1 , db2
e db3 acredita a, pois de acordo com o critério da maioria duas fontes acreditam em a
enquanto que somente uma acredita em ¬a.
Do mesmo modo podemos provar:
(6) `M F ψ → B(db1 +db2 )+db3 b,
Outros teoremas deduzidos são mostrados a seguir:
0
(7) `M F ψ → Bdb
c (de A4 )
1 +db2
1
(8) `M F ψ → B(db
c (de A4 e (7))
1 +db2 )+db3
1
(9) `M F ψ → Bdb1 +db2 ¬c (de A4 )
1
(10) `M F ψ → B(db
¬c (de A4 e (9))
1 +db2 )+db3
(11) `M F ψ → ¬B(db1 +db2 )+db3 c (de A6 , (8) e (10))
(12) `M F ψ → ¬B(db1 +db2 )+db3 ¬c (de A6 , (8) e (10))
De (11), (12) e (A0 ) deduzimos que:
(13) `M F ψ → ¬B(db1 +db2 )+db3 c ∧ ¬B(db1 +db2 )+db3 ¬c.
Este teorema significa que a integração das fontes db1 , db2 e db3 não acredita em c e
nem ¬c, e desta forma a fonte de informação resultante da integração de db1 , db2 e db3 é
mantida consistente.
Discussão
Foi apresentada uma proposta de tratamento de inconsistências que surgem no processo
de integração de fontes de informação heterogêneas, baseada na abordagem de revisão de
crença, onde as inconsistências são eliminadas. No trabalho proposto por esta disssertação
assume-se que os dados já foram integrados, que as inconsistências foram identificadas e
armazenadas com o valor-verdade inconsistente, e não há a preocupação de como isso
foi conseguido. Em [dACM02], é apresentado um método baseado no esquema de prova
por tableau da lógica LFI1 [CM01] que executa a integração de fontes heterogêneas de
60
dados, e os dados inconsistentes são identificados e armazenados com a indicação de que
são contraditórios, ao invés de descartados.
3.2.2
Abordagem paraconsistente na integração
Em [ABC99] é apresentada uma abordagem paraconsistente no tratamento de inconsistências que podem surgir no processo de integração de fontes de dados. O objetivo do
trabalho é fornecer respostas às consultas feitas a qualquer instância de banco de dados,
consistente ou não em relação ao conjunto de restrições de integridade.
A lógica base é a lógica clássica de primeira ordem [Sou02].
Noções básicas
Neste parágrafo são introduzidas algumas definições e termos que serão utilizados na
descrição do método para obtenção de respostas consistentes.
Uma instância r do banco de dados é consistente se r satisfaz o conjunto de restrições
de integridade IC, ou seja, r ² IC. A instância r é inconsistente caso contrário.
Definição 3.2.4 Seja a instância r do banco de dados. O conjunto de fórmulas {P (a)|r ²
P (a)}, onde P é um nome de relação e a uma tupla instanciada, é denotado por Σ(r).
Desta forma, o conjunto Σ(r) corresponde ao conjunto de fatos da instância r do banco
de dados.
Definição 3.2.5 A distância ∆(r, r0 ) entre as instâncias r e r0 é dada pela diferença
simétrica:
∆(r, r0 ) = |(Σ(r) − Σ(r0 )) ∪ (Σ(r0 ) − Σ(r))|.
Ou seja, a distância ∆(r, r0 ) corresponde ao número de fatos que estão em r e não estão
em r0 , somados ao número de fatos que estão em r0 e não estão em r.
A relação de ordem no conjunto de instâncias é definida a seguir.
Definição 3.2.6 A relação de ordem no conjunto de instâncias, denotada por 6r , é
definida da seguinte forma: fixada a instância r e dadas as instâncias r0 e r00 , temos que:
r0 6r r00 se ∆(r, r0 ) 6 ∆(r, r00 ).
Uma instância r0 é dita ser 6r minimal, se ∆(r, r0 ) 6 ∆(r, r00 ), para toda instância r00 .
Exemplo 3.2.3 Considere um esquema de banco de dados com duas relações unárias p
e q sobre o domı́nio D = {a, b, c}. Sejam as instâncias r, r0 e r00 , mostradas a seguir:
61
Σ(r) = {p(a), p(b), q(a), q(c)}
Σ(r0 ) = {p(a), q(a), q(c)}
Σ(r00 ) = {p(a), p(b), p(c), q(a), q(b), q(c)}.
Temos que ∆(r, r0 ) = 1 e ∆(r, r00 ) = 2. Portanto, r0 6r r00 .
Uma vez definida a ordem entre as instâncias do banco de dados, é possı́vel definir o
que é um reparo de banco de dados. Intuitivamente, temos que um reparo do banco de
dados é uma instância que pertence ao conjunto das instâncias que satisfazem o conjunto
de restrições IC, e que possui a menor distância ∆ em relação à instância original do
banco de dados.
Definição 3.2.7 (Reparo) Sejam r e r0 duas instâncias do banco de dados. r0 é reparo
de r se r0 ² IC e r0 é 6r minimal entre as instâncias do banco de dados que satisfazem
IC.
Exemplo 3.2.4 Considere o esquema de banco de dados com as relações:
F ornecedor(IdF ornecedor, N ome, Item) e Classe(IdItem, ClasseItem),
e que possui a seguinte restrição de integridade IC: o fornecedor C é o único que fornece
itens da classe T 4, ou seja,
∀x∀y∀z(F ornecedor(x, y, z) ∧ Classe(z, T 4) → (x = C).
Seja a seguinte instância r do banco de dados, mostrada a seguir:
Fornecedor
C D1 I1
D D2 I2
Classe
I1 T 4
I2 T 4
A instância r é inconsistente, pois a restrição de integridade é violada pelo fornecerdor
D, que fornece o item I2 da classe T4 .
Os únicos reparos para esta instância r são mostrados a seguir:
Instância r0 :
Fornecedor
Classe
C D1 I1
I1 T 4
I2 T 4
Instância r00 :
Fornecedor
Classe
C D1 I1
I1 T 4
D D2 I2
62
Note que ∆(r, r0 ) = ∆(r, r00 ) = 1. Isto é, tanto r0 quanto r00 são 6r minimais.
Definição 3.2.8 (Resposta) Uma tupla instanciada t é uma resposta à uma consulta
Q(X) expressa no cálculo relacional [AVH95], sobre a instância r se r ² Q(t). Uma tupla
instanciada t é uma resposta ao conjunto de consultas {Q1 , . . . , Qn } se r ² Q1 (t) ∧ . . . ∧ Qn (t).
Definição 3.2.9 (Resposta Consistente) Seja IC um conjunto de restrições de integridade. Uma tupla instanciada t é uma resposta consistente à consulta Q(X) sobre a
instância r, denotado por r ²c Q(t), se para todo reparo r0 de r, temos que r0 ² Q(t). Se
Q é uma sentença, então o valor-verdade verdadeiro (falso) é uma resposta consistente a
Q em r, denotado por r ²c Q (r 6²c Q), se para todo reparo r0 de r, r0 ² Q (r0 6² Q).
Exemplo 3.2.5 A única resposta consistente à consulta Classe(z, T 4) sobre a instância
r do exemplo 3.2.4 é I1 , pois r ²c Classe(I1 , T 4). Ou seja, para os reparos r0 e r00 de r,
temos que r0 ² Classe(I1 , T 4) e r00 ² Classe(I1 , T 4).
Método de obtenção de respostas consistentes
O método para calcular respostas consistentes a consultas é baseado na noção de resı́duos
desenvolvida no contexto da Otimização Semântica de Consultas (SQO)[CGM90]. SQO
é utilizada para otimizar o processo de construção de respostas a consultas através do
conhecimento semântico sobre o domı́nio subjacente às restrições de integridade. Assumese que as restrições de integridade são satisfeitas pelo banco de dados, ou seja, que o banco
de dados é consistente, e uma maneira de se obter uma resposta consistente é modificar
a consulta, isto é, considerar a fórmula Q(x) ∧ IC ao invés de somente Q(x). Entretanto,
quando a instância do banco de dados é inconsistente, a resposta será sempre falso. Então
é proposto em [ABC99], que a consulta Q seja iterativamente modificada usando-se os
resı́duos, que serão definidos no texto a seguir, resultando assim, em uma consulta Tω (Q)
que produz o conjunto de respostas consistentes de Q, mesmo quando a instância onde é
calculada é inconsistente. Desta forma, é possı́vel raciocinar na presença da inconsistência.
As restrições de integridade consideradas pela proposta [ABC99], são aquelas que
podem ser representadas no formato padrão descrito a seguir:
Definição 3.2.10 Uma restrição de integridade está no formato padrão se possui a
seguinte forma:
∀(
m
_
pi (x) ∨
i=1
n
_
¬qi (y) ∨ Ψ),
i=1
onde ∀ representa o fecho universal da fórmula, p e q são sı́mbolos de predicados, x e y
são tuplas não instanciadas e Ψ é uma fórmula que contém somente predicados built-in4 .
4
Predicados built-in são relações binárias correspondentes aos sı́mbolos de comparação usuais (=, 6,
>, . . .).
63
Algumas restrições de integridade não podem ser reescritas neste formato padrão, como
as restrições do tipo ∀xp(x) → ∃yq(y). De fato, ∀xp(x) → ∃yq(y) ≡ ¬∀xp(x) ∨ ∃yq(y) ≡
∃x¬p(x) ∨ ∃yq(y) ≡ ∃x∃y(¬p(x) ∨ q(x)), que não corresponde ao formato padrão.
O exemplo seguinte mostra a idéia intuitiva da geração de resı́duos:
Exemplo 3.2.6 Considere a seguinte restrição de integridade: ∀x(¬p(x) ∨ q(x)). Neste
caso, se q(x) é falso, então ¬p(x) deve ser verdadeiro. Então, quando temos a consulta
¬q(x), a fim de encontrarmos as respostas consistentes, temos que garantir que ¬p(x) se
torne verdadeiro. Desta forma, é gerada a consulta modificada ¬q(x) ∧ ¬p(x), onde ¬p(x)
é o resı́duo adicionado à consulta.
A geração de resı́duos é baseado em cada ocorrência positiva ou negativa dos predicados
que aparecem nas restrições de integridade. Intuitivamente, temos que o resı́duo associado
a um predicado em uma dada restrição de integridade do conjunto IC, é dado pela mesma
restrição sem a presença do predicado em questão, como é descrito a seguir:
Para toda restrição de integridade do conjunto IC, no formato padrão, temos:
a) Para cada ocorrência positiva do predicado pj (x) em IC, é gerado um resı́duo R
para ¬pj (x):
j−1
R = Q̄(
_
pi (x) ∨
i=1
m
_
pi (x) ∨
i=j+1
n
_
¬qi (y) ∨ Ψ),
i=1
onde Q̄ corresponde a uma sequência de quantificadores universais sobre as variáveis que
não aparecem na tupla x.
Uma vez gerados todos os resı́duos R1 , . . . , Rr , correspondentes às ocorrências positivas
do predicado pj (x), para o predicado ¬pj (x), então é gerada a seguinte regra denotada:
¬pj (x) 7→ ¬pj (x){R1 , . . . , Rr }.
Se não há resı́duos, então é gerada a regra denotada ¬pj (x) 7→ ¬pj (x).
Esta regra denotada gerada será utilizada no processo de modificação da consulta
(definição 3.2.12). Intuitivamente, temos que uma consulta da forma ¬pj (x) deve garantir que os resı́duos {R1 , . . . , Rr } gerados para o predicado positivo pj (x) em IC também
sejam satisfeitos para que a resposta seja consistente. Esta mesma idéia se aplica aos
predicados negativos e seus resı́duos, como é descrito a seguir.
b) Para cada ocorrência negativa do predicado qj (y) em IC, é gerado um resı́duo R0
para cada qj (y):
0
R = Q̄(
m
_
j−1
pi (x) ∨
i=1
_
i=1
¬qi (y) ∨
n
_
¬qi (y) ∨ Ψ),
i=j+1
64
onde Q̄ corresponde a uma sequência de quantificadores universais sobre as variáveis que
não aparecem na tupla y.
Uma vez gerados todos os resı́duos R10 , . . . , Rr0 , correspondentes às ocorrências negativas do predicado qj (y), para o predicado qj (y), então é gerada a seguinte regra denotada:
qj (y) 7→ qj (y){R10 , . . . , Rr0 }.
Se não há resı́duos, então é gerada a regra denotada qj (y) 7→ qj (y).
Desta forma, sempre é gerada uma nova regra denotada para todo predicado positivo
e para todo predicado negativo.
Exemplo 3.2.7 Considere o seguinte conjunto IC de restrições de integridade no formato
padrão:
IC = {∀x(r(x) ∨ ¬p(x) ∨ ¬q(x)), ∀x(p(x) ∨ ¬q(x))},
Calculando-se os resı́duos para cada predicado positivo e negativo de IC, são geradas
as seguintes regras denotadas:
p(x)
q(x)
r(x)
¬p(x)
¬q(x)
¬r(x)
7→
7→
7→
7→
7→
7→
p(x){r(x) ∨ ¬q(x)}
q(x){r(x) ∨ ¬p(x), p(x)}
r(x)
¬p(x){¬q(x)}
¬q(x)
¬r(x){¬p(x) ∨ ¬q(x)}
Note que o predicado negativo ¬q(x) aparece nas duas restrições de IC, e possui dois
resı́duos: R1 = r(x) ∨ ¬p(x) e R2 = p(x).
Os predicados built-in podem aparecer nos resı́duos mas não geram regras, pois não
podem ser modificados para tornar o conjunto IC verdadeiro, como mostra o próximo
exemplo.
Exemplo 3.2.8 Considere o conjunto IC mostrado a seguir:
∀x∀y∀z(¬p(x, y) ∨ ¬p(x, z) ∨ (y = z)),
e uma instância r do banco de dados tal que Σ(r) = {p(1, 2), p(1, 3)}. Se x = 1 , y = 2 e
z = 3, para que IC fosse verdadeiro deverı́amos ter 2=3.
Uma vez gerados os resı́duos associados ao conjunto de restrições IC, a seguir é definido
um método de modificação da consulta original Q, para uma consulta modificada Tω (Q)
que produz as respostas consistente de Q.
Em toda a abordagem de [ABC99], é assumido que todas as consultas estão na forma
normal disjuntiva, isto é, uma disjunção de conjunções de literais, como é formalizado na
seguinte definição:
65
Definição 3.2.11 (Consulta) Uma fórmula Q é uma consulta se ela possui a seguinte
forma sintática:
nj
mi
s ^
_
^
Q̄ ( pi,j (ui,j ) ∧
¬q(vi,j ) ∧ Ψi ),
i=1 j=1
j=1
onde Q̄ é uma sequência de quantificadores e Ψ contém somente predicados built-in usuais.
Se s = 0, então temos uma consulta que consiste de uma cláusula vazia, denotada por
¤.
Se a sequência Q̄ contém somente quantificadores universais, então Q é uma consulta
universal. Se a sequência Q̄ contém algum quantificador existencial, então Q é uma
consulta não-universal.
A determinação de respostas consistentes a consultas em banco de dados consistentes
ou não, é obtida por uma famı́lia de operadores Tn :consulta → consulta, n > 0, e
Tω :consulta → conjunto de consultas.
Definição 3.2.12 A aplicação do operador Tn , n > 0, a uma consulta é definido de forma
indutiva, da seguinte maneira:
1. Tn (¤) = ¤, Tn (¬¤) = ¬¤, para todo n > 0 (¤ é uma cláusula vazia).
2. T0 (ϕ) = ϕ, para toda consulta ϕ.
3. Para toda consulta que corresponde ao predicado positivo p(x), se existe uma regra
p(x) 7→ p(x){R1 (x), . . . , Rr (x)}, então:
Tn+1 (p(x)) = p(x)
r
^
Tn (Ri (x)).
i=1
Se p(x) não possui resı́duos, então Tn+1 (p(x)) = p(x).
4. Para toda consulta que corresponde ao predicado negativo ¬q(x), se existe uma
regra ¬q(x) 7→ ¬q(x){R10 (x), . . . , Rs0 (x)}, então:
Tn+1 (¬q(x)) = ¬q(x)
s
^
Tn (Ri0 (x)).
i=1
Se ¬q(x) não possui resı́duos, então Tn+1 (¬q(x)) = ¬q(x).
5. Se a consulta ϕ é uma fórmula na forma normal disjuntiva prenex5 , tal que:
5
Uma fórmula está na forma prenex quando todos os seus quantificadores aparecem somente no inı́cio
da fórmula.
66
nj
mi
s ^
_
^
ϕ = Q̄ ( pi,j (ui,j ) ∧
¬q(vi,j ) ∧ Ψi ),
i=1 j=1
j=1
onde Q̄ é uma sequência de quantificadores e Ψ contém somente predicados built-in usuais,
então, para todo n > 0:
nj
mi
s ^
_
^
Tn (ϕ) = Q̄ ( Tn (pi,j (ui,j )) ∧
Tn (¬q(vi,j )) ∧ Ψi ),
i=1 j=1
j=1
Finalmente, a aplicação do operador Tω sobre uma consulta é definido por
[
Tω (ϕ) =
{Tn (ϕ)}.
n<ω
Ou seja, Tω (ϕ) corresponde à consulta ϕ modificada.
Repare que Tω pode ser um conjunto infinito de fórmulas. As condições necessárias
para que este conjunto seja finito são apresentadas em [ABC99]. Se o conjunto Tω é
finito, então em um número finito de passo n, temos que Tn (ϕ) = Tn+1 (ϕ), como ocorre
nos exemplos seguintes.
Exemplo 3.2.9 Considere o exemplo 3.2.7. Seja a consulta ¬r(x). O cálculo da consulta
¬r(x) modificada é apresentado a seguir:
T0 (¬r(x)) = ¬r(x).
T1 (¬r(x)) = ¬r(x) ∧ (¬p(x) ∨ ¬q(x)).
T2 (¬r(x)) = ¬r(x) ∧ T1 (¬p(x) ∨ ¬q(x)) = ¬r(x) ∧ (T1 (¬p(x)) ∨ T1 (¬q(x))) = ¬r(x) ∧
((¬p(x) ∧ ¬q(x)) ∨ ¬q(x)) = T3
Portanto, a consulta ¬r(x) modificada é dada por:
Tω (¬r(x)) = {¬r(x), ¬r(x) ∧ (¬p(x) ∨ ¬q(x)), ¬r(x) ∧ ((¬p(x) ∧ ¬q(x)) ∨ ¬q(x))}.
Exemplo 3.2.10 Considere o exemplo 3.2.5. A restrição de integridade IC reescrita no
formato padrão (definição 3.2.10) é mostrado a seguir:
∀x∀y∀z∀w(¬F ornecedor(x, y, z) ∨ ¬Classe(z, w) ∨ w 6= T 4 ∨ x = C).
Para a consulta Classe(z, T 4), seguinte regra é gerada:
Classe(z, w) 7→ Classe(z, w){∀xy(¬F ornecedor(x, y, z) ∨ w 6= T 4 ∨ x = C)}.
A consulta Classe(z, T 4) executada sobre a instância inconsistente r1 obtém como
resposta I1 e I2 .
Vamos calcular a consulta modificada Tω :
T0 (Classe(z, T 4)) = Classe(z, T 4).
67
T1 (Classe(z, T 4)) = Classe(z, T 4) ∧ T0 (∀xy(¬F ornecedor(x, y, z) ∨ x = C))
= Classe(z, T 4) ∧ ∀xy(¬F ornecedor(x, y, z) ∨ x = C).
T2 (Classe(z, T 4)) = Classe(z, T 4) ∧ T1 (∀xy(¬F ornecedor(x, y, z) ∨ x = C))
= Classe(z, T 4) ∧ ∀xy(T1 (¬F ornecedor(x, y, z)) ∨ T1 (x = C)) =
= Classe(z, T 4) ∧ ∀xy(¬F ornecedor(x, y, z) ∨ x = C).
Logo, T1 (Classe(z, T 4)) = T2 (Classe(z, T 4)), e portanto
Tω (Classe(z, T 4)) = {Classe(z, T 4), Classe(z, T 4)∧∀xy(¬F ornecedor(x, y, z)∨x = C)}.
A consulta Tω (Classe(z, T 4)) executada sobre a instância inconsistente r obtém como
resposta somente I1 , a única resposta consistente.
A próxima proposição mostra que a consulta definida pelo operador Tω obtém o mesmo
resultado que uma consulta aplicada a um banco de dados consistente.
Proposição 3.2.2 ([ABC99]) Seja r uma instância do banco de dados e um conjunto
IC de restrições de integridade, tal que r |= IC. Para toda consulta Q(x) e toda tupla
instanciada t: r |= Q(t) se e somente se r |= Tω (Q(t)).
Ou seja, se a tupla t é resposta da consulta Q aplicada a uma instância consistente r,
então t também é resposta da consulta modificada Tω (Q(t)) aplica à instância r.
O método de modificação de consultas é provado ser correto para certos tipos de
consultas, como é mostrado a seguir.
Teorema 3.2.1 (Corretude [ABC99]) Seja r uma instância do banco de dados, IC
um conjunto de restrições de integridade, e Q(x) uma consulta tal que r |= Tω (Q(t)).
Se Q é uma consulta universal, ou é uma consulta não-universal mas independente de
domı́nio, então t é uma resposta consistente de Q em r, isto é, r |=c Q(t).
A condição imposta pelo teorema exclui as consultas que são existenciais e dependentes
do domı́nio, como ∃x¬p(x). Para as outras consultas, o teorema da corretude garante que
as respostas obtidas pela consulta modificada são sempre respostas consistentes.
A completude do método é parcial: é válida somente para restrições de integridade
binárias, isto é, com somente dois literais, como é definido a seguir:
Definição 3.2.13 Uma restrição de integridade binária (denotada por BIC) é uma sentença da seguinte forma:
∀(L1 (x1 ) ∨ L2 (x2 ) ∨ Ψ(x)),
68
onde L1 e L2 são literais, e Ψ é uma fórmula que contém somente predicados built-in
usuais.
Exemplos de restrições de integrigade binárias incluem dependências funcionais e restrições da forma ∀x(p(x) → q(x)).
Teorema 3.2.2 (Completude [ABC99]) Seja um conjunto de restrições de integridades binárias IC. Então, para todo literal instanciado L(t), se r |=c L(t) então r |=
Tω (L(t)).
Intuitivamente temos que, toda resposta consistente a uma consulta do tipo L(x) é
obtida pela consulta modificada definida pelo operador Tω .
Discussão
Foi apresentada uma proposta de tratamento de inconsistências em instâncias de banco
de dados sob a perspectiva paraconsistente. Segundo esta proposta, as inconsistências
do banco de dados são mantidas no banco de dados, mas são eliminadas das respostas
derivadas deste banco de dados possivelmente inconsistente. As respostas produzidas são
sempre respostas que um banco de dados consistente daria.
No caso de P-Datalog¬ , as inconsistências também são mantidas no banco de dados, devidamente identificadas como tal, e as respostas produzidas podem conter fatos
classificados como verdadeiros, falsos, indefinidos e inconsistentes.
Capı́tulo 4
P-Datalog¬
Neste capı́tulo inicia-se a apresentação da principal contribuição desta dissertação, com
a descrição da linguagem dedutiva de consultas P-Datalog¬ . Inicialmente é definida a
sintaxe de programas P-Datalog¬ , na seção 4.1, e em seguida, na seção 4.2, é apresentada
a sua lógica base: a lógica 4-valorada 4-LFI1, e são introduzidas as noções de instância
4-valorada e modelo de um programa P-Datalog¬ . Na seção 4.3, é feito um aparte onde
temos a definição de programa P-Datalog¬ estendido, o qual não apresenta literais negativos. Para este tipo de programa é definido um operador de consequência imediata, a
partir do qual é possı́vel obter a semântica destes programas. A peça chave da definição
da semântica bem-fundada de P-Datalog¬ é o conceito de modelo 4-estável, que é apresentado na seção 4.4. Finalmente, na seção 4.5 é definida a semântica bem-fundada de
P-Datalog¬ .
A terminologia utilizada é a tradicional de banco de dados, e pode ser encontrada em
[AVH95].
4.1
Sintaxe P-Datalog¬
Nesta seção é apresentada a sintaxe de programas P-Datalog¬ , através dos quais são feitas
as consultas ao banco de dados contendo inconsistências.
Definição 4.1.1 (Programas P-Datalog¬ ) Um programa P-Datalog¬ é um conjunto
finito de regras do tipo:
A ← L1 , ..., Ln
onde A é um átomo do tipo R(u), e Li são literais do tipo R(u), ∼ R(u), sendo que R é o
nome de relação, u é uma tupla não instanciada e ∼ é o sı́mbolo da negação por default.
O átomo A é chamado de cabeça da regra. Os literais L1 , ..., Ln são chamados de corpo
da regra.
69
CAPÍTULO 4. P-DATALOG¬
70
Os programas P-Datalog¬ assim como os programas Datalog¬ (definição 2.5.1), pertencem à classe dos programas lógicos padrões (definição 2.2.2); ou seja, são programas
lógicos que aceitam a negação por default somente no corpo de suas regras. Apesar de
P-Datalog¬ não permitir literais negativos na cabeça das regras, os programas P-Datalog¬
atuam sobre bancos de dados paraconsistentes, cujas instâncias podem conter fatos inconsistentes além dos fatos verdadeiros e falsos.
A recursão negativa ou, em outras palavras, a definição de uma dada relação que utiliza
o seu próprio complemento, é aceita nos programas P-Datalog¬ . O exemplo seguinte
mostra um programa P-Datalog¬ com recursão negativa.
Exemplo 4.1.1 O programa Pwin descrito abaixo é um programa P-Datalog¬ :
win(x) ← move(x, y), ∼ win(y).
O conjunto de relações que aparecem em P é denotado por sch(P ) , o conjunto de
constantes que aparecem em P por adom(P ), e o conjunto com todos os fatos obtidos a
partir de R(a1 , . . . , an ) onde R ∈ sch(P ) e a1 , . . . , an ∈ adom(P ), é denotado por B(P )
(base de Herbrand de P ).
Exemplo 4.1.2 (sch(P ), adom(P ), B(P )) Considere a mesma situação apresentada no
exemplo 1.0.1: o programa Pcargo e a instância 3-valorada I. Temos então que:
sch(P )={indicadoPor, cargo, devedor },
adom(P ) = {charles, john, james, joseph, paul, kevin}, e
B(P ) = {devedor(charles), devedor(joseph), indicadoPor(charles,joseph), . . .}.
4.2
Modelos de programas P-Datalog¬
Nesta seção, inicialmente é definida uma extensão das lógicas LFI1 e lógica 3-valorada de
Przymusinski [Prz90], para a lógica 4-valorada 4-LFI1, que é a lógica base da semântica
de programas P-Datalog¬ . Em seguida é introduzido o conceito de modelo 4-valorado de
programas P-Datalog¬ .
4.2.1
Lógica 4-valorada 4-LFI1: a lógica base de P-Datalog¬
Os bancos de dados tradicionais são representados por instâncias 2-valoradas: um fato
está, ou não está armazenado no banco de dados. Estas instâncias são conjuntos contendo
os fatos presentes no banco de dados. Entretanto, bancos de dados que armazenam fatos
identificados como seguros ou contraditórios, denotados por bancos de dados paraconsistentes, requerem uma representação de instância que diferencie um fato armazenado como
seguro, do fato armazenado como contraditório, e do fato que não está armazenado no
71
t
i
u
f
Figura 4.1: Lógica 4-valorada 4-LFI1
banco de dados. Ou seja, são necessários pelo menos três valores distintos para se associar
aos fatos da instância: verdadeiro, falso e inconsistente.
A semântica de programas P-Datalog¬ , descrita na próxima seção, é uma extensão
da semântica bem-fundada de programas Datalog¬ (descrita na seção 2.5.3), onde é introduzido um novo valor associado aos fatos que representam a semântica de um dado
programa: o valor indefinido. Desta forma, a semântica bem-fundada de programas
P-Datalog¬ associa aos fatos um dos valores: verdadeiro, falso, indefinido, inconsistente.
É necessário então que a lógica base seja capaz de representar e raciocinar com esses
quatro valores-verdade, como a lógica 4-valorada 4-LFI1 descrita a seguir.
A lógica 4-LFI1 é uma extensão direta da lógica LFI1 (descrita na seção 2.3). Os
sı́mbolos proposicionais t, i, u e f que denotam os valores-verdade: verdadeiro, inconsistente, indefinido e falso, respectivamente, são adicionados ao alfabeto da lógica LFI1.
Desta forma, as matrizes dos conectivos (Figura 2.1) também são estendidas para as matrizes expostas na Figura 4.3. As outras definições de LFI1 são diretamente incorporadas
na lógica 4-LFI1.
4.2.2
Modelos 4-valorados
Os programas P-Datalog¬ são executados sobre instâncias de bancos de dados paraconsistentes, onde entre os fatos armazenados podem existir fatos identificados como inconsistentes. Desta forma, uma instância 2-valorada não é capaz de representar uma instância
de um banco de dados paraconsistente. A seguir é definida a instância 3-valorada que
representa uma instância de um banco de dados paraconsistente.
Definição 4.2.1 (Instâncias de Bancos de Dados Paraconsistentes) Seja R um esquema de banco de dados. Uma instância do banco de dados paraconsistente sobre R é
uma interpretação (definição 2.3.1) I tal que para cada R ∈ R o conjunto IR = {u :
I(R(u)) = t ou I(R(u)) = i} é finito. Assim, uma instância sobre R pode ser vista como
um conjunto finito de relações onde cada relação é um conjunto finito de tuplas (tuplas
cujo valor-verdade é t ou i). Uma tupla u sobre R tal que I(R(u)) = i é considerada
◦A
•A
∼A
A
A
A
A
A
72
está no banco de dados e é uma informação segura.
está no banco de dados e é uma informação contraditória.
não está no banco de dados.
está no banco de dados como informação segura ou contraditória.
Figura 4.2: Sı́mbolos associados a um átomo A em P-Datalog¬
controversa, isto é, existe evidência a favor de R(u) e também existe evidência contrária
a R(u). Por outro lado, se I(R(u)) = t, então R(u) é uma informação segura.
A semântica bem-fundada de P-Datalog¬ introduz o valor-verdade indefinido associado
aos fatos, o que nos leva à noção de instância 4-valorada, isto é, uma instância na qual os
fatos assumem um dos quatro valores-verdade do conjunto V = {verdadeiro(t), falso(f ),
inconsistente(i), indefinido(u)}. O conjunto V possui uma ordem entre os seus elementos
que é mostrada a seguir:
f 6 u 6 i 6 t.
Intuitivamente, temos que o valor u (indefinido) é uma indicação mais fraca da presença de um fato no banco de dados do que o valor i (inconsistente). O conjunto V e a
ordem 6 formam um reticulado completo (Figura 4.1).
Definição 4.2.2 (Instância 4-valorada) Uma instância 4-valorada I sobre sch(P ) é
uma interpretação I : B(P ) → V. Denotamos por It ,If , Iu e Ii o conjunto de átomos em
que todos os elementos possuem valor-verdade t, f, u e i, respectivamente. Uma instância
4-valorada é total quando não possui átomos com valor-verdade igual a u. Neste caso,
esta instância equivale a uma instância 3-valorada.
As instâncias 4-valoradas são representadas como um conjunto contendo fatos verdadeiros, inconsistentes e falsos. Os fatos que não estão no conjunto são considerados
indefinidos. Lembramos que na representação de instâncias 2-valoradas, os fatos que não
se encontram no conjunto são fatos falsos, de acordo com a “hipótese do mundo fechado”
(veja observação 2.4.1).
A presença de sı́mbolos junto a um átomo A em P-Datalog¬ tem diferentes significados,
como é mostrado na Figura 4.2. Intuitivamente, temos que o sı́mbolo ∼ da negação por
default possui a propriedade de retornar sempre um valor seguro, isto é, seguramente falso
ou seguramente verdadeiro que um fato não se encontra no banco de dados. Desta forma,
a negação de um valor inconsistente resulta em falso, como mostra a matriz do conectivo
∼ na Figura 4.3.
Exemplo 4.2.1 (Instância 4-valorada) Seja I uma instância 4-valorada onde I(p)=t,
I(q)=i, I(r)=u e I(s)=f. A instância I pode ser representada da seguinte forma:
t
i
u
f
∼
f
f
u
t
∨
t
i
u
f
t
t
t
t
t
i
t
i
i
i
u
t
i
u
u
73
f
t
i
u
f
∧
t
i
u
f
t
t
i
u
f
i
i
i
u
f
u
u
u
u
f
f
f
f
f
f
→
t
i
u
f
t
t
t
t
t
i
f
i
t
t
u
f
f
t
t
f
f
f
f
t
Figura 4.3: Matrizes dos conectivos de 4-LFI1
I = {◦p, •q, ∼ s}.
Existe uma ordem natural 4 entre instâncias 4-valoradas sobre sch(P ), definida por:
I 4 J se e somente se para todo A ∈ B(P ), I(A) 6 J(A).
Exemplo 4.2.2 Seja I = {◦p, ◦q, ∼ s} e J = {◦p, ◦q, •s}. Então, I 4 J.
O conjunto finito de instâncias 4-valoradas de um programa P-Datalog¬ P é denominado 4-InstP . É fácil verificar que (4-InstP , 4) forma um reticulado completo:
1. 4 é uma relação de ordem;
2. Dado X ⊆ 4 InstP , existe sup(X) e existe inf (X);
3. sup(4 InstP ) = >, onde > corresponde à instância 4-valorada máxima onde todos
os fatos são verdadeiros (It );
4. inf (4 InstP ) = ⊥, onde ⊥ corresponde à instância 4-valorada mı́nima onde todos
os fatos são falsos (If ).
Se F é o corpo de uma regra de um programa P-Datalog¬ , e I é uma instância 4valorada, denotamos por I(F ) o valor-verdade associado a F de acordo com a matriz do
connectivo ∧ (Figura 4.3).
Definição 4.2.3 (Modelo 4-valorado) Seja P um programa P-Datalog¬ e ground(P )
o conjunto de regras instanciadas1 de P . Uma instância 4-valorada I sobre sch(P ) satisfaz
uma fórmula α contendo átomos de B(P ) combinados com os conectivos booleanos ∼,
∧, ∨, →, se e somente se I(α) ∈ {t, i}. Um modelo 4-valorado de P é uma instância
4-valorada sobre sch(P ) que satisfaz toda regra em ground(P ), isto é, o valor-verdade de
toda regra em ground(P ) é t ou i (de acordo com a definição 2.3.2).
Exemplo 4.2.3 (Modelo 4-valorado) Considere o programa P-Datalog¬ Pcargo dado
no exemplo 1.0.1 e a instância J, descritos a seguir:
1
Uma regra instanciada é uma regra onde todas as variáveis são trocadas por constantes de adom(P ).
verdadeiro
t
falso
inconsistente
indefinido
f
i
u
indicadoPor(charles,joseph),indicadoPor(joseph,charles),
indicadoPor(paul,james), indicadoPor(james,kevin),
devedor(james), cargo(paul)
cargo(james), cargo(kevin)
indicadoPor(john,kevin), cargo(john)
Vamos verificar se J é um modelo 4-valorado de ground(Pcargo ):
cargo(charles) ←∼ devedor(charles), indicadoPor(charles,joseph), ∼ cargo(joseph)
u ←∼ f, t, ∼ u
u ← t, t, u
u←u
t
cargo(joseph) ←∼ devedor(joseph), indicadoPor(joseph,charles), ∼ cargo(charles)
u ←∼ f, t, ∼ u
u ← t, t, u
u←u
t
cargo(paul) ←∼ devedor(paul), indicadoPor(paul,james), ∼ cargo(james)
t ←∼ f, t, ∼ f
t ← t, t, t
t←t
t
cargo(james) ←∼ devedor(james), indicadoPor(james,kevin), ∼ cargo(kevin)
f ←∼ t, t, ∼ f
f ← f, t, t
f←f
t
cargo(john) ←∼ devedor(john), indicadoPor(john,kevin), ∼ cargo(kevin)
i ←∼ f, i, ∼ f
i ← t, i, t
i←i
i
74
75
A instância 4-valorada J satisfaz todas as regras de ground(Pcargo ) e portando J é um
modelo 4-estável de Pcargo .
Observação 4.2.1 (Conectivo implicação) A semântica da operação de implicação
na lógica 4-LFI1 difere da lógica LFI1. Intuitivamente temos que na lógica 4-LFI1, a
partir de um fato verdadeiro, é falso que se deduza um fato inconsistente. Por exemplo,
seja I uma instância tal que I(p) = t e I(q) = i. Seja F ≡ p → q. Na lógica 4-LFI1,
temos que I(F ) = f, ou seja, I não satisfaz F em 4-LFI1. Entretanto, na lógica LFI1,
temos que I(F ) = i, ou seja, I satisfaz F em LFI1.
4.3
Programas P-Datalog¬ Estendidos
Na seção 2.4 foi definido um operador de consequência imediata monotônico e contı́nuo,
cujo menor ponto fixo coincide com a semântica do programa Datalog sem negação. Nesta
seção é introduzida a noção de programa P-Datalog¬ estendido que, assim como os programas Datalog, são programas sem negação, mas que podem deduzir fatos verdadeiros,
inconsistentes, indefinidos e falsos.
Definição 4.3.1 (Programa Estendido) Um programa P-Datalog¬ estendido P é um
programa P-Datalog¬ onde:
(1) fatos negativos do tipo ∼ A não aparecem no corpo das regras; e
(2) valores-verdade t, f, u e i podem aparecer no corpo das regras.
Exemplo 4.3.1 (Programa estendido) O programa P descrito abaixo é um programa
P-Datalog¬ estendido:
p←i
p ← q, i
q ← p, r
q ← p, s
r←t
s←q
Observação 4.3.1 (Programas que incluem dados de entrada) Assim como no contexto de programação em lógica (veja observação 2.4.2), é suposto que os programas
P-Datalog¬ sempre incluem os seus fatos de entrada, da maneira descrita a seguir.
Seja P um programa P-Datalog¬ e I uma instância paraconsistente 3-valorada (definição
4.2.1). É denotado por PI o programa obtido de P com a adição a P de regras do tipo
A ← para cada A tal que I(A) = t; e A ← i para cada A tal que I(A) = i.
76
Exemplo 4.3.2 (Programa PI ) Vamos considerar a mesma situação apresentada no
exemplo 1.0.1: o programa Pcargo e a instância 3-valorada J. Temos então que PJ é dado
por:
cargo(X) ←∼ devedor(X),indicadoPor(X,Y), ∼cargo(Y)
indicadoPor(paul, james) ←
indicadoPor(charles, joseph) ←
indicadoPor(joseph, charles) ←
indicadoPor(james, kevin) ←
indicadoPor(john, kevin) ← i
devedor(james) ←
4.3.1
Operador de consequência imediata 4-TP
Os programas P-Datalog¬ estendidos são programas sem negação, e desta forma não estão
sujeitos às implicações semânticas da negação (descritas na seção 2.5.1). Podemos então,
obter a semântica deste programas através da aplicação de um operador de consequência
imediata. Este operador é chamado de 4-TP , e sua definição é uma extensão da definição
do operador 3-TP de Datalog¬ (definição 2.5.10).
Definição 4.3.2 (Operador 4-TP ) Seja P um programa P-Datalog¬ estendido. O operador de consequência imediata associado a P , denotado por 4-TP , é um mapeamento
4-TP : 4-InstP → 4-InstP . Mais precisamente, seja I uma instância 4-valorada e A ∈
B(P ). O operador 4-TP é definido da seguinte forma:


 max{I(Fk )} se existem regras do tipo A ← Fk em ground(P),
4-TP (I)(A) =
para todo k, k > 0;


f
caso contrário
Exemplo 4.3.3 Seja P o mesmo programa P-Datalog¬ estendido do exemplo 4.3.1, isto
é,
p←i
p ← q, i
q ← p, r
q ← p, s
r←t
s←q
Seja I uma instância 4-valorada, onde I={•p, ∼ q, ◦r, ∼ s}. Então temos:
4-TP (I)(p) =max{I(i), I(q ∧ i)}=max{i, (f ∧ i)}=max{i, f }=i.
77
4-TP (I)(q) =max{I(p ∧ r), I(p ∧ s)}=max{(i ∧ t), (i ∧ f)}=max{i, f }=i.
4-TP (I)(r) = t.
4-TP (I)(s) = f.
Portanto, 4-TP (I)= {•p, •q, ◦r, ∼ s}.
De forma análoga aos programas Datalog (seção 2.4), são apresentadas a seguir propriedades algébricas (descritas na seção 2.1) do operador 4-TP . Estas propriedades são
utilizadas para comprovar que o único menor ponto fixo de 4-TP pode ser obtido iterativamente a partir da instância ⊥, e este coincide com o modelo minimal do programa
positivo P-Datalog¬ estendido.
A seguir é mostrado que o operador 4-TP é monotônico e contı́nuo.
Proposição 4.3.1 Seja P um programa P-Datalog¬ estendido. O operador 4-TP associado a P é um operador monotônico.
Demonstração:
O operador 4-TP é monotônico se I 4 J então 4-TP (I) 4 4-TP (J).
Supondo que ∀A ∈ B(P ) I(A) 6 J(A), vamos mostrar que ∀A ∈ B(P ) 4-TP (I)(A) 6
4-TP (J)(A).
Para todo A de B(P ), em ground(P ) temos as seguintes possibilidades:
a) Não existe regra com A na cabeça. Neste caso temos que 4-TP (I)(A) = 4-TP (J)(A)=f.
b) Existem regras com A na cabeça, da forma A ← Fk , para todo k, k > 0. Neste
caso temos que:
4-TP (I)(A) = max{I(Fk )} e 4-TP (J)(A) = max{J(Fk )},
onde Fk corresponde a uma conjunção de átomos de B(P ) e sı́mbolos representando os
valores-verdade t, i, u, f.
Segundo a nossa hipótese, o valor-verdade de todos os átomos de B(P ) em I é sempre
menor ou igual ao valor em J. Desta forma, max{I(Fk )} 6 max{J(Fk )} e, portanto,
¤
4-TP (I)(A) 6 4-TP (J)(A).
Proposição 4.3.2 Seja P um programa P-Datalog¬ estendido. O operador 4-TP associado a P é um operador contı́nuo.
Demonstração:
Seja X um subconjunto direto do conjunto finito de instâncias 4-valoradas 4-InstP , onde:
X={In , In+1 , . . . , In+m }.
78
Temos que sup(X) = Is , onde Is ∈ 4-InstP , Is ∈ X e Ij 4 Is , para todo Ij ∈ X,
n 6 j 6 n + m. Ou seja, sup(X) é uma instância de 4-InstP .
Vamos mostrar que 4-TP (sup(X)) = sup(4-TP (X)).
Como Ij 4 Is para todo Ij ∈ X, n 6 j 6 n + m, e 4-TP é monotônico, temos que:
4-TP (Ij ) 4 4-TP (Is ), para todo Ij ∈ X, n 6 j 6 n + m. Então, 4-TP (X) 4 4-TP (Is ).
Logo, sup(4-TP (X))=4-TP (Is ).
Como sup(X) = Is , então temos que 4-TP (sup(X)) = sup(4-TP (X)).
¤
4.3.2
Semântica do ponto fixo para programas P-Datalog¬ estendidos
Uma vez definido que o operador 4-TP é monotônico, então é garantido que existe um
único menor ponto fixo, e este é dado por:
lf p(4-TP ) = inf {I | 4-TP (I) 4 I} (proposição 2.1.4),
onde lf p denota o menor ponto fixo e inf denota o maior limitante inferior. Este resultado
é então utilizado com outro resultado: para todo modelo M de um programa P-Datalog¬
estendido P , temos que 4-TP (M ) 4 M . Logo, o modelo minimal de P é o menor ponto
fixo de 4-TP . A seguir estes resultados são formalizados.
Proposição 4.3.3 Seja P um programa P-Datalog¬ estendido e M uma instância de P .
A instância M é um modelo 4-valorado de P se e somente se 4-TP (M ) 4 M .
Demonstração:
Vamos mostrar que M é modelo de P se e somente se 4-TP (M ) 4 M .
M é modelo de P ⇐⇒
⇐⇒ ∀A ∈ B(P ), para toda regra de ground(P ) do tipo A ← Fk , temos M (A ← Fk ) ∈
{t, i} para todo k, k > 0.
⇐⇒ ∀A ∈ B(P ), para toda regra de ground(P ) do tipo A ← Fk , temos M (Fk ) 6 M (A)
para todo k, k > 0.
⇐⇒ ∀A ∈ B(P ), para toda regra de ground(P ) do tipo A ← Fk , temos max{M (Fk )} 6 M (A)
para todo k, k > 0.
⇐⇒ ∀A ∈ B(P ), 4-TP (M )(A) 6 M (A).
⇐⇒ 4-TP (M ) 4 M .
¤
Proposição 4.3.4 Seja P um programa P-Datalog¬ estendido e M uma instância de P .
Se M é ponto fixo de 4-TP então M é modelo de P .
79
Demonstração:
Se M é ponto fixo de 4-TP então M é modelo de P .
M é ponto fixo de 4-TP =⇒
⇐⇒ 4-TP (M ) = M.
⇐⇒ ∀A ∈ B(P ), 4-TP (M )(A) = M (A).
⇐⇒ ∀A ∈ B(P ), existem regras em ground(P ) do tipo A ← Fk , onde max{M (Fk )} = M (A).
=⇒ ∀A ∈ B(P ), existem regras em ground(P ) do tipo A ← Fk , onde M (Fk ) 6 M (A).
=⇒ ∀A ∈ B(P ), existem regras em ground(P ) do tipo A ← Fk , onde M (A ← Fk ) ∈ {t, i}.
=⇒ M é modelo de P .
¤
Porém nem todo modelo de um programa P é ponto fixo de 4-TP , como mostra o
próximo exemplo.
Exemplo 4.3.4 (Modelo que não é ponto fixo) Considere o seguinte programa P ,
um programa P-Datalog¬ estendido:
p←q
p←i
q←f
Temos que M1 = {•p, •q} é modelo do programa P , porém 4-TP (M1 ) = {•p, ∼ q}. Ou
seja, M1 é modelo de P mas não é ponto fixo de 4-TP . Desta forma, o sentido inverso da
proposição 4.3.4 não é válido.
Seja a sequência {4-TPi (⊥)}i>0 ={I0 , I1 , I2 , . . . }, onde:
I0 = ⊥
I1 =4-TP (I0 )
I2 =4-TP (I1 )
...
Como o operador 4-TP é monotônico, e I0 4 Ij para todo j, j > 0, temos que:
I0 4 I1 ⇐⇒ 4-TP (I0 ) 44-TP (I1 ) ⇐⇒ I1 4 I2 .
I1 4 I2 ⇐⇒ 4-TP (I1 ) 44-TP (I2 ) ⇐⇒ I2 4 I3 .
...
Continuando este mesmo procedimento, é obtida a seguinte sequência:
I0 4 I1 4 I2 4 I3 . . ..
Portanto a sequência {4-TPi (⊥)}i>0 é crescente, e o seu menor limitante superior é
denotado por 4-TP ↑.
80
O lema seguinte mostra que o modelo minimal único do programa P-Datalog¬ estendido P corresponde ao menor ponto fixo do operador 4-TP . Por ser um operador
contı́nuo, a proposição 2.1.5 nos indica que o menor ponto fixo de 4-TP pode ser obtido
construtivamente a partir da sequência {4-TPi (⊥)}i>0 .
Lema 4.3.1 Seja P programa P-Datalog¬ estendido. Então
1) O menor ponto fixo de 4-TP é dado por 4-TP ↑; e
2) P possui um único modelo minimal 4-valorado que coincide com o menor ponto
fixo de 4-TP .
Demonstração:
Seja M modelo do programa P-Datalog¬ estendido P , e MP o modelo minimal de P .
⇐⇒ MP = inf {M |M é modelo de P }.
⇐⇒ MP = inf {M | 4-TP (M ) 4 M } pela proposição 4.3.3.
⇐⇒ MP = lf p(4-TP ), pelas proposições 2.1.4 e 4.3.1.
⇐⇒ MP = 4-TP ↑, pelas proposições 2.1.5 e 4.3.2.
¤
Exemplo 4.3.5 (Cálculo do ponto fixo de 4-TP ) Considere o programa P-Datalog¬
estendido P :
p←i
p ← q, i
q ← p, r
q ← p, s
r←t
s←q
Temos a seguinte sequência de aplicações sucessivas de 4-TP , a partir da instância
⊥ = {∼ p, ∼ q, ∼ r, ∼ s}:
4-TP1 (⊥)= {•p, ∼ q, ◦r, ∼ s}
p←i
p ← q, i
q ← p, r
q ← p, s
r←t
s←q
4-TP2 (⊥)= {•p, •q, ◦r, ∼ s}=4-TP3 (⊥)
p←i
p ← f,i
q ← f,f
q ← f,f
r←t
s←f
p←i
p←f
q←f
q←f
r←t
s←f
81
p←i
p ← q, i
q ← p, r
q ← p, s
r←t
s←q
p←i
p ← f,i
q ← i,t
q ← i,f
r←t
s←f
p←i
p←f
q←i
q←f
r←t
s←f
A instância {•p, •q, ◦r, ∼ s} é o menor ponto fixo de 4-TP e também o modelo minimal
4-valorado do programa P-Datalog¬ estendido P .
4.4
Modelos 4-estáveis
Definir a semântica de um programa Datalog¬ , é encontrar um modelo 3-valorado I apropriado para este programa. De acordo com Przymusinski [Prz90](seção 2.5.3), o modelo
3-valorado apropriado é um modelo 3-estável (definição 2.5.12). Nesta seção, o conceito
de 3-estabilidade é estendido para o contexto de P-Datalog¬ .
Seja I uma instância 4-valorada sobre sch(P ). A versão positiva instanciada de P
de acordo com I, denotado por pg(P, I), é o programa P-Datalog¬ obtido de ground(P )
através da substituição de cada literal negativo ∼ A por I(∼ A), isto é, por seu respectivo
valor-verdade: t, f, u, i.
Logo, pg(P, I) é agora um programa P-Datalog¬ estendido e, pelo lema 4.3.1, a sua
semântica coincide com o menor ponto fixo do operador de consequência imediata 4-TP .
Esta semântica contém todos os fatos que são deduzidos de P e I, assumindo-se os valores
dos átomos negados como os valores dados por I. O cálculo do menor ponto fixo do
programa P-Datalog¬ positivo instanciado P de acordo com I, é obtido através de um
operador de estabilidade chamado conseqP , formalmente definido a seguir.
Definição 4.4.1 (Operador de estabilidade) Seja pg(P, I) o programa P-Datalog¬
positivo instanciado, obtido do programa P-Datalog¬ P , e da instância 4-valorada I.
O operador de estabilidade, denotado por conseqP , associado ao programa P e instância
I, é um mapeamento conseqP : 4-InstP → 4-InstP , tal que:
conseqP (I) =4-Tpg(P,I) ↑,
onde 4-Tpg(P,I) ↑ corresponde ao menor ponto fixo do operador de consequência imediata
4-TP aplicado ao programa pg(P, I), a partir da instância ⊥.
Uma vez definido o operador de estabilidade conseqP , é possı́vel definir formalmente
o modelo 4-estável, que é a peça chave da semântica bem-fundada de P-Datalog¬ .
Definição 4.4.2 (Modelo 4-estável) Seja P um programa P-Datalog¬ . Uma instância
4-valorada I sobre sch(P ) é um modelo 4-estável de P se e somente se conseqP (I) = I.
82
Intuitivamente, temos que o modelo 4-estável é aquele que é capaz de reproduzir a si
mesmo ao passar pelo operador de estabilidade conseqP .
O exemplo seguinte ilustra a noção de modelo 4-estável.
Exemplo 4.4.1 (Modelo 4-estável) Considere o programa P-Datalog¬ Pcargo dado no
exemplo 1.0.1 e a instância J descritos a seguir:
verdadeiro
t
falso
f
inconsistente i
indefinido
u
indicadoPor(charles,joseph),indicadoPor(joseph,charles),
indicadoPor(paul,james), indicadoPor(james,kevin),
devedor(james), cargo(paul)
cargo(james), cargo(kevin)
indicadoPor(john,kevin), cargo(john)
Vamos verificar se J é um modelo 4-estável de Pcargo . Para tal, temos que calcular
conseq(J) e mostrar que conseq(J) = J.
O programa positivado instanciado pg(Pcargo , J) é descrito a seguir:
cargo(charles) ← t,indicadoPor(charles, joseph), u
cargo(joseph) ← t,indicadoPor(joseph, charles), u
cargo(paul) ← t,indicadoPor(paul, james), t
cargo(john) ← t,indicadoPor(john, kevin), t
cargo(james) ← f,indicadoPor(james, kevin), t
indicadoPor(john, kevin) ←i
devedor(james) ←
Vamos então calcular pg(Pcargo , J)(⊥). Os átomos indicadoPor e devedor serão omitidos nas instâncias produzidas pela aplicação do operador 4-TP mostradas a seguir, pois
os valores destes coincidem com os valores apresentados pela instância J.
1
4-Tpg(P
(⊥)= {∼ cargo(charles), ∼ cargo(james), ∼ cargo(john), ∼ cargo(joseph),
cargo ,J)
∼ cargo(kevin), ∼ cargo(paul)}
cargo(charles) ← t,f,u
cargo(joseph) ← t,f,u
cargo(paul) ← t,f,t
cargo(john) ← t,f,t
cargo(james) ← f,f,t
=⇒
=⇒
=⇒
=⇒
=⇒
cargo(charles) ← f
cargo(joseph) ←f
cargo(paul) ←f
cargo(john) ← f
cargo(james) ← f
83
2
4-Tpg(P
(⊥)= {∼ cargo(james), • cargo(john), ∼ cargo(kevin), ◦ cargo(paul)}=
cargo ,J)
3
=4-Tpg(Pcargo ,J)
cargo(charles) ← t,t,u
cargo(joseph) ← t,t,u
cargo(paul) ← t,t,t
cargo(john) ← t,i,t
cargo(james) ← f,t,t
=⇒ cargo(charles) ← u
=⇒ cargo(joseph) ← u
=⇒ cargo(paul) ← t
=⇒ cargo(john) ← i
=⇒ cargo(james) ← f
Portanto, temos que :
conseqPcargo (J) =4-Tpg(Pcargo ,J) ↑= J,
e J é um modelo 4-estável de Pcargo .
4.5
Semântica bem-fundada de P-Datalog¬
Programas P-Datalog¬ , assim como os programas Datalog¬ podem ter vários modelos
4-estáveis (como mostra o exemplo 4.5.1), e cada programa P-Datalog¬ possui pelo
menos um modelo 4-estável (como será visto no teorema 5.1.2 do capı́tulo 5). Então
é razoável dizer que a resposta esperada para um programa P-Datalog¬ consiste dos fatos
verdadeiros, inconsistentes e falsos que pertençam a todos os modelos 4-estáveis do programa.
Definição 4.5.1 (Semântica bem-fundada de P-Datalog¬ ) Seja P um programa
P-Datalog¬ . A semântica bem-fundada P-Datalog¬ de P é uma instância 4-valorada consistindo de todos os fatos verdadeiros, inconsistentes e falsos que pertencem a todos os
modelos 4-estáveis de P . Tal instância é denotada por P 4wf .
Exemplo 4.5.1 (Programa P-Datalog¬ com vários modelos 4-estáveis) Considere
o seguinte programa P-Datalog¬ P :
p←i
q ← ∼r
r ← p, ∼q
s ← ∼ r, p, q
O programa possui três modelos 4-estáveis (os fatos indefinidos são omitidos):
M1 = {• p, •r, ∼q,∼s},
M2 = {• p, •s, ◦q, ∼r } e
M3 = {• p}.
Portanto, a semântica bem-fundada de P-Datalog¬ do programa P é P 4wf ={• p}.
84
Discussão: Semântica bem-fundada P-Datalog¬ fraca
Um fato é dito ser inconsistente quando existe evidência de sua presença no banco de
dados e também quando existe evidência do contrário. Baseando-se nesta definição intuitiva, investigamos a possibilidade de uma definição da semântica bem-fundada fraca de
P-Datalog¬ , cujo modelo é denotado por wP 4wf . Em tal modelo os fatos inconsistentes
seriam os que são inconsistentes em pelo menos um dos modelos 4-estáveis do programa,
e os verdadeiros e falsos seriam os que são verdadeiros e falsos, respectivamente, em todos
os modelos 4-estáveis. Entretanto, como mostra o exemplo a seguir, esta definição produz
modelos não estáveis.
Exemplo 4.5.2 (Semântica bem-fundada fraca P-Datalog¬ ) Considere o programa
P-Datalog¬ P do exemplo 4.5.1. A definição de semântica bem-fundada fraca de PDatalog¬ wP 4wf produz o modelo wP 4wf = {• p, •r, •q}.
O programa positivado instanciado pg(P, wP 4wf ) é descrito a seguir:
p←i
q ←f
r ← p, f
s ← f, p, q
1
2
4-Tpg(P,wP
4wf ) (⊥)={• p, ∼r, ∼q, ∼ r }=4-Tpg(P,wP 4wf ) .
Temos então que conseqP (wP 4wf ) ={•p, ∼r, ∼q, ∼r }.
Ou seja, conseqP (wP 4wf ) 6= wP 4wf e wP 4wf não é modelo 4-estável.
Capı́tulo 5
Método de avaliação bottom-up
Neste capı́tulo é descrito um método construtivo de avaliação de programas P-Datalog¬ ,
baseado em um operador de ponto fixo. Na seção 5.1, é apresentado o algoritmo do ponto
fixo alternante, através do qual se obtém a semântica bem-fundada P-Datalog¬ . Em
seguida, na seção 5.2, são apresentados resultados que mostram que a semântica bemfundada P-Datalog¬ estende a semântica bem-fundada Datalog¬ . No final do capı́tulo,
na seção 5.3, são apresentadas considerações sobre a implementação do provador de programas P-Datalog¬ .
5.1
Algoritmo do ponto fixo alternante
A descrição da semântica bem-fundada de P-Datalog¬ , apresentada no capı́tulo 4, produz
um algoritmo para obtenção desta semântica que envolve, em primeiro lugar, a determinação dos modelos 4-estáveis dentre todas as instâncias 4-valoradas do programa, para
em seguida calcular a sua intersecção. A intersecção dos modelos 4-estáveis resulta na
semântica bem-fundada de P-Datalog¬ . Tal algoritmo apesar de eficaz é ineficiente. Um
algoritmo mais simples e mais eficiente para se obter, de forma construtiva, a semântica
bem-fundada de P-Datalog¬ , é proposto nesta seção. Este algoritmo é uma extensão do
algoritmo do ponto fixo alternante de Datalog¬ , apresentado em [AVH95], que por sua
vez é uma adaptação do algoritmo de Van Gelder [Van89] (descrito na seção 2.5.5).
O algoritmo do ponto fixo alternante de P-Datalog¬ consiste na construção de uma
sequência alternante de instâncias que converge para a semântica bem-fundada P-Datalog¬ ,
como é descrito a seguir.
5.1.1
Sequência alternante
Na definição da semântica bem-fundada de P-Datalog¬ , foi proposto um operador de
estabilidade, denotado por conseqP . Este operador conseqP é utilizado para definir uma
85
CAPÍTULO 5. MÉTODO DE AVALIAÇÃO BOTTOM-UP
86
sequência de instâncias a partir da instância ⊥, na qual todos os átomos de B(P ) são
falsos.
Definição 5.1.1 (Sequência alternante) A sequência alternante {Ii }i>0 é definida da
seguinte forma:
I0 = ⊥
Ii+1 = conseqP (Ii ), i > 0
Exemplo 5.1.1 Considere o programa P-Datalog¬ P apresentado no exemplo 4.5.1, isto
é:
p
q
r
s
←i
← ∼r
← p, ∼q
← ∼ r, p, q
A partir do programa P e do operador conseqP obtemos a seguinte sequência alternante:
I0 ={∼p, ∼q, ∼r, ∼s}
I2 ={•p, ∼q, ∼r, ∼s}
I4 ={•p, ∼q, ∼r, ∼s}
I1 ={•p, ◦q, •r, •s}
I3 ={•p, ◦q, •r, •s}
Note que toda instância Ii pertencente à sequência alternante do exemplo anterior,
é uma instância total, isto é, não possui átomos com valor-verdade u. De fato, isto se
verifica em geral, como mostra a próxima proposição.
Proposição 5.1.1 Toda instância 4-valorada Ii , i > 0, pertencente à sequência alternante {Ii }i>0 é uma instância total.
Demonstração:
Isto decorre dos seguintes fatos:
• se I é total, então conseqP (I) é total; e
• Ii é construı́da a partir da instância total ⊥, pela aplicação repetida de conseqP .
De fato, no cálculo de conseqP são utilizados o operador negação ∼ e conjunção ∧,
e estes apenas resultam no valor-verdade u se aplicados a pelo menos um átomo cujo
valor-verdade também é u. Como a instância I é total, para todo A ∈ B(P ) temos que
I(A) 6=u. Logo, conseqP (I) também é uma instância total.
¤
O próximo resultado apresentado justifica a denominação de alternante para a sequência
{Ii }i>0 .
87
Teorema 5.1.1 O operador conseqP (I) é antimonotônico. Ou seja, se I 4 J, então
conseqP (J) 4 conseqP (I).
Demonstração:
Queremos mostrar que se I 4 J então conseqP (I) 4 conseqP (J).
Ou seja, se ∀A ∈ B(P ), I(A) 6 J(A) então ∀A ∈ B(P ), conseqP (J)(A) 6 conseqP (I)(A).
Sabemos que por definição conseqP (I) é o menor ponto fixo do programa positivo
instanciado, denotado por pg(P, I)(⊥), obtido por aplicações sucessivas do operador 4TP .
Temos, então, os seguintes casos:
1. conseqP (J)(A)=t. Vamos mostrar que conseqP (I)(A) =t.
Por indução em n vamos provar a seguinte asserção:
j
n
P(n)= “Se n é tal que 4-Tpg(P,J)
(⊥)(A) =t, e ∀j, j > n, 4-Tpg(P,J)
(⊥)(A) =t, então
conseqP (I)(A) =t.”
• Base da Indução: n=1
Vamos demonstrar que conseqP (I)(A) =t.
Segundo a hipótese, existe em ground(P ) regra da forma:
A ←∼ B1 , . . . , ∼ Bn , onde Bk são átomos, J(Bk ) =f para todo k, 1 6 k 6 n.
De I 4 J temos que I(Bk ) =f para todo k, 1 6 k 6 n.
Logo conseqP (I)(A) =t.
Portanto a base da indução é verdadeira.
• Passo da indução: Supomos P(n) e vamos demonstrar P(n+1).
Vamos mostrar que conseqP (I)(A) =t.
A ←∼ B1 , . . . , ∼ Bn , D1 , . . . , Dm , onde Bk , Dg são átomos, J(Bk ) =f para todo k,
n
1 6 k 6 n e 4-Tpg(P,J)
(⊥)(Dg ) =t, para todo g, 1 6 g 6 m.
De P(n) temos conseqP (I)(Dg ) =t, para todo g, 1 6 g 6 m.
Logo conseqP (I)(A) =t.
Portanto a base e o passo da indução estão demonstrados e P(n) é válido para todo
n, n > 1.
2. conseqP (J)(A)=i. Vamos mostrar que conseqP (I)(A) > i.
88
j
n
P(n)=“Se n é tal que 4-Tpg(P,J)
(⊥)(A) =i, e ∀j, j > n, 4-Tpg(P,J)
(⊥)(A) =i, então
conseqP (I)(A) >i.”
Vamos demonstrar que conseqP (I)(A) >i.
A ←∼ B1 , . . . , ∼ Bn , c1 , . . . , cp , onde Bk são átomos e cg são valores-verdade,
J(Bk ) =f para todo k, 1 6 k 6 n, cg >i para todo g, 1 6 g 6 p, e existe um
w tal que cw =i, 1 6 w 6 p.
Logo conseqP (I)(A) >i.
Vamos mostrar que conseqP (I)(A) >i.
A ←∼ B1 , . . . , ∼ Bn , D1 , . . . , Dm , onde Bk , Dg são átomos, J(Bk ) =f para todo k,
n
1 6 k 6 n e 4-Tpg(P,J)
(⊥)(Dg ) >i, para todo g, 1 6 g 6 m.
De P(n) temos conseqP (I)(Dg ) >i, para todo g, 1 6 g 6 m.
Logo conseqP (I)(A) =i.
n, n > 1.
3. conseqP (J)(A)=u. Vamos mostrar que conseqP (I)(A) > u.
j
n
P(n)=“Se n é tal que 4-Tpg(P,J)
(⊥)(A) =u, e ∀j, j > n, 4-Tpg(P,J)
(⊥)(A) =u, então
conseqP (I)(A) >u.”
Vamos demonstrar que conseqP (I)(A) >u.
A ←∼ B1 , . . . , ∼ Bn , c1 , . . . , cp , onde Bk são átomos e cg são valores-verdade,
J(Bk ) ∈ {f,u} para todo k, 1 6 k 6 n, cg >u para todo g, 1 6 g 6 p, e existe um
w, 1 6 w 6 p, tal que cw =u ou existe y, 1 6 y 6 n, tal que J(By ) =u.
De I 4 J temos que I(Bk ) ∈ {f,u} para todo k, 1 6 k 6 n.
89
Logo conseqP (I)(A) >u.
Vamos mostrar que conseqP (I)(A) >u.
A ←∼ B1 , . . . , ∼ Bn , D1 , . . . , Dm , onde Bk , Dg são átomos, J(Bk ) ∈{f,u} para todo
n
(⊥)(Dg ) >u, para todo g, 1 6 g 6 m.
k, 1 6 k 6 n e 4-Tpg(P,J)
De I 4 J temos que I(Bk ) ∈ {f,u} para todo k, 1 6 k 6 n.
De P(n) temos conseqP (I)(Dg ) >u, para todo g, 1 6 g 6 m.
Logo conseqP (I)(A) >u.
n, n > 1.
4. conseqP (J)(A)=f. Neste caso temos que sempre conseqP (I)(A) > f.
¤
A instância I0 = ⊥ é a menor de todas as instâncias 4-valoradas relativas ao programa
P , ou seja, I0 4 In , ∀n > 0. Aplicando-se o operador conseqP à desigualdade anterior,
obtemos que conseqp (In ) 4 conseqP (I0 ). Então, In+1 4 I1 , ∀n > 0. Desta forma, as
instâncias I0 e I1 são, respectivamente, a menor e a maior das instâncias 4-valoradas da
sequência {Ii }i>0 .
Aplicando-se o operador conseqP sucessivamente à desigualdade I0 4 I2 , obtemos:
I0 4 I2
I3 4 I1
I2 4 I4
I5 4 I3
I4 4 I6
...
=⇒ conseqP (I2 ) 4 conseqP (I0 ) =⇒
E, de I0 4 I1 obtemos:
I0 4 I1
I2 4 I1
I2 4 I3
I4 4 I3
I4 4 I5
...
90
A partir das desigualdades anteriores, obtemos a sequência alternante {Ii }i>0 , mostrada
a seguir:
I0 4 I2 4 I4 4 .. 4 I2i 4 I2i+2 4 .. 4 I2i+1 4 I2i−1 4 .. 4 I5 4 I3 4 I1
5.1.2
Instâncias I∗ , I∗ e I∗∗
Na sequência alternante, temos que a subsequência par está crescendo e a ı́mpar está
decrescendo. Como o conjunto de instâncias 4-valoradas sobre o universo de Herbrand
do programa P é finito, cada uma delas torna-se constante em algum ponto. Ou seja,
I2k = I2k+2 e I2j+1 = I2j+3 , para algum k > 0 e algum j > 0. Os limitantes da sequência
par e sequência ı́mpar são definidos a seguir.
Definição 5.1.2 O menor limitante superior da sequência crescente é denotado por I∗ ,
e definido da seguinte forma:
I∗ = sup{I2i }i>0 .
O maior limite inferior da sequência decrescente é denotado por I∗ , definido da
seguinte forma:
I∗ = inf {I2i+1 }i>0 .
Exemplo 5.1.2 As instâncias I∗ e I∗ para a sequência alternante do exemplo 5.1.1 são
mostradas a seguir:
I∗ ={•p, ∼q, ∼r, ∼s} e I∗ ={•p, ◦q, •r, •s}
Observe que I∗ 4 I∗ . De fato, na sequência {Ii }i>0 temos que uma instância par é
sempre menor ou igual a uma instância ı́mpar.
Vamos mostrar a seguir que o operador conseqP aplicado ao menor limite da sequência
par resulta no maior limite da sequência ı́mpar. Do mesmo modo, conseqP aplicado ao
maior limite da sequência ı́mpar resulta no menor limite da sequência par.
Proposição 5.1.2 Seja I uma instância 4-valorada e P um programa P-Datalog¬ . Temos
que:
conseqP (I∗ ) = I∗ e conseqP (I∗ ) = I∗ .
Demonstração:
Suponha que o limite da sequência par seja I∗ = I2k = I2k+2 , para algum k > 0.
Vamos mostrar que conseqP (I∗ ) = I∗ .
Sabemos que Ii+1 = conseqP (Ii ). Então, temos que:
91
I2k = conseqP (I2k−1 )
I2k+1 = conseqP (I2k )
I2k+2 = conseqP (I2k+1 )
I2k+3 = conseqP (I2k+2 )
Pela nossa suposição, I∗ = I2k = I2k+2 . Então , conseqP (I2k ) = conseqP (I2k+2 ). Logo,
I2k+1 = I2k+3 , o que define o limite I∗ da sequência ı́mpar. Portanto, conseqP (I∗ ) = I∗ .
De forma análoga mostramos que conseqP (I∗ ) = I∗ .
¤
A partir das instâncias I∗ e I∗ é definida uma instância 4-valorada I∗∗ , que coincide
com a semântica bem-fundada, como é enunciado no teorema 5.1.2.
Definição 5.1.3 (Instância I∗∗ ) Seja I∗∗ a instância 4-valorada consistindo de fatos contidos na intersecção de I∗ e I∗ , como é definido a seguir:

t se I∗ (A) = I∗ (A) = t



 i se I (A) = I∗ (A) = i
∗
∗
I∗ (A) =

f se I∗ (A) = I∗ (A) = f



u caso contrário
A próxima proposição mostra que a instância I∗∗ é uma instância que pode não ser
total, e portanto pode não pertencer à sequência alternante, mas que se encontra, em
termos de precedência, entre as instâncias totais I∗ e I∗ .
Exemplo 5.1.3 No exemplo 5.1.2 foram definidas as instâncias I∗ ={•p, ∼q, ∼r, ∼s} e
I∗ ={•p, ◦q, •r, •s}. A partir destas duas instâncias, obtemos a instância I∗∗ mostrada a
seguir:
I∗∗ ={•p}.
Observe que as instâncias I∗ e I∗ são instâncias totais, enquanto que I∗∗ não é uma
instância total.
Proposição 5.1.3 Seja I uma instância 4-valorada de um programa P-Datalog¬ , então:
I∗ 4 I∗∗ 4 I∗ .
Demonstração:
A demonstração deste resultado é direta da aplicação da definição de I∗∗ , onde temos
apenas um caso em que a desigualdade não é válida: quando I∗ (A)=i e I∗ (A)=t.
Vamos mostrar que este caso não ocorre, ou seja, se I∗ (A)=t então I∗ (A) ∈{f,t}.
Podemos reescrever I∗ (A) como conseqP (I∗ )(A) e I∗ (A) como conseqP (I∗ )(A). Supondo
conseqP (I∗ )(A)= t, vamos mostrar que neste caso conseqP (I∗ )(A) ∈{f,t}.
92
Vamos provar por indução em n a seguinte asserção:
j
n
P(n)=“Se n é tal que 4-Tpg(P,I
(⊥)(A) =t, então
(⊥)(A) =t, e ∀j, j > n, 4-Tpg(P,I
∗)
∗)
∗
conseqP (I )(A) ∈{f,t}.”
Vamos demonstrar que conseqP (I∗ )(A) ∈{f,t}.
A ←∼ B1 , . . . , ∼ Bn , onde Bk são átomos, I∗ (Bk ) =f para todo k, 1 6 k 6 n.
De I∗ 4 I∗ temos que I∗ (Bk ) ∈{f,i,t} para todo k, 1 6 k 6 n.
Logo conseqP (I∗ )(A) ∈{t,f } e a base da indução é verdadeira.
Vamos mostrar que conseqP (I∗ )(A) ∈ {f,t}.
A ←∼ B1 , . . . , ∼ Bn , D1 , . . . , Dm , onde Bk , Dg são átomos, I∗ (Bk ) =f para todo k,
n
1 6 k 6 n e 4-Tpg(P,I
(⊥)(Dg ) =t, para todo g, 1 6 g 6 m.
∗)
∗
De I∗ 4 I temos que I∗ (Bk ) ∈{f,i,t} para todo k, 1 6 k 6 n.
De P(n) temos conseqP (I∗ )(Dg ) ∈{f,t}, para todo g, 1 6 g 6 m.
Logo conseqP (I∗ )(A) ∈{f,t}. Portanto a base e o passo da indução são verdadeiros.
P(n) é válido para todo n, n > 1.
¤
Exemplo 5.1.4 Para as sequências definidas no exemplo anterior (exemplo 5.1.3), mostradas
novamente a seguir:
I∗ ={•p, ∼q, ∼r, ∼s},
I∗ ={•p, ◦q, •r, •s},
I∗∗ ={•p},
é verificada a desigualdade I∗ 4 I∗∗ 4 I∗ .
5.1.3
Cálculo da semântica bem-fundada de P-Datalog¬
A construção do ponto fixo alternante produz a semântica bem-fundada para programas
P-Datalog¬ , como mostra o próximo teorema. A prova do teorema indica que um programa P-Datalog¬ tem pelo menos um modelo 4-estável e, desta forma sua semântica
bem-fundada é sempre definida. Mostra também que o modelo obtido pela construção do
ponto fixo alternante é um modelo 4-estável.
Teorema 5.1.2 Para todo programa P-Datalog¬ P :
1. A instância I∗∗ é um modelo 4-estável de P .
2. A semântica bem-fundada P-Datalog¬ P 4wf coincide com a instância I∗∗
93
Demonstração:
I) Vamos mostrar que I∗∗ é modelo 4-estável de P .
Sabemos que I∗ 4 I∗∗ 4 I∗ , e conseqP (I∗ ) = I∗ , conseqP (I∗ ) = I∗ . Como conseqP é
antimonotônico, temos:
I∗ 4 I∗∗ 4 I∗
=⇒ conseqP (I∗ ) < conseqP (I∗∗ ) < conseqP (I∗ )
=⇒ I∗ < conseqP (I∗∗ ) < I∗
=⇒ I∗ 4 conseqP (I∗∗ ) 4 I∗
(5.1)
Vamos verificar cada um dos possı́veis valores de I∗∗ (A).
1) Se I∗∗ (A)=f
Pela definição de I∗∗ , temos que I∗ (A)=f e I∗ (A)=f. Trocando-se os valores de I∗ (A) e
I∗ (A) na desigualdade (5.1) temos que f 6 conseqP (I∗∗ )(A) 6 f.
Logo, conseqP (I∗∗ )(A)=f.
2) Se I∗∗ (A)=t
Pela definição de I∗∗ , temos que I∗ (A)=t e I∗ (A)=t. Trocando-se os valores de I∗ (A) e
I∗ (A) na desigualdade (5.1) temos que t 6 conseqP (I∗∗ )(A) 6 t.
Logo, conseqP (I∗∗ )(A)=t.
3) Se I∗∗ (A)=i
Pela definição de I∗∗ , temos que I∗ (A)=i e I∗ (A) = i. Trocando-se os valores de I∗ (A)
e I∗ (A) da desigualdade (5.1) temos que i 6 conseqP (I∗∗ )(A) 6 i.
Logo, conseqP (I∗∗ )(A)=i.
4) Se I∗∗ (A)=u
Pela definição de I∗∗ , temos os seguintes casos:
a) I∗ (A)=i e I∗ (A) =t.
Este caso não é possı́vel. É equivalente a conseqP (I∗ )(A) =i e conseqP (I∗ )(A) =t, e
se conseqP (I∗ )(A) =t então conseqP (I∗ )(A) ∈{f,t}, como foi mostrado na demonstração
da proposição 5.1.3.
b) I∗ (A)=f e I∗ (A) ∈{i,t}.
É equivalente a conseqP (I∗ )(A) =f e conseqP (I∗ )(A) >i.
Por definição, conseqP (I∗ ) é o menor ponto fixo de pg(P, I∗ )(⊥).
Vamos considerar a seguinte asserção:
j
n
n
P(n)=“Se n é tal que 4-Tpg(P,I
(⊥)(A) >i, e ∀j, j > n, 4-Tpg(P,I
(⊥)(A) =4-Tpg(P,I
(⊥)(A),
∗)
∗)
∗)
∗
então conseqP (I∗ )(A) =u.”
Vamos demonstrar que conseqP (I∗∗ )(A) =u.
94
A ←∼ B1 , . . . , ∼ Bn , c1 , . . . , cp , onde Bk são átomos e cg são valores-verdade, I∗ (Bk ) =f
para todo k, 1 6 k 6 n, cg >i para todo g, 1 6 g 6 p.
De I∗ 4 I∗ temos que I∗ (Bk ) ∈{f,i,t} para todo k, 1 6 k 6 n. Por conseqP (I∗ )(A) =f
então existe um l, 1 6 l 6 n tal que I∗ (Bl ) ∈{i,t}.
Da definição I∗∗ temos que I∗∗ (Bk ) ∈{f,u} para todo k, 1 6 k 6 n, e existe um l,
1 6 k, l 6 n tal que I∗∗ (Bl )=u.
Logo conseqP (I∗∗ )(A) =u.
Vamos mostrar que conseqP (I∗∗ )(A) =u.
A ←∼ B1 , . . . , ∼ Bn , D1 , . . . , Dm , onde Bk , Dg são átomos, I∗ (Bk ) =f para todo k,
n
(⊥)(Dg ) >i, para todo g, 1 6 g 6 m.
1 6 k 6 n e 4-Tpg(P,I
∗)
∗
De I∗ 4 I temos que I∗ (Bk ) ∈{f,i,t} para todo k, 1 6 k 6 n. Segundo a hipótese
inicial, conseqP (I∗ )(A) =f então existe um l, 1 6 l 6 n tal que I∗ (Bl ) ∈{i,t}.
Da definição I∗∗ temos que I∗∗ (Bk ) ∈{f,u} para todo k, 1 6 k 6 n, e existe um l,
1 6 l 6 n, tal que I∗∗ (Bl )=u.
De P(n) temos conseqP (I∗∗ )(Dg ) =u, para todo g, 1 6 g 6 m.
Logo conseqP (I∗∗ )(A) =u.
Portanto a base e o passo da indução são verdadeiros. P(n) é válido para todo n,
n > 1.
II) Agora vamos demostrar que P 4wf = I∗∗ . Para todo A ∈ B(P ), temos:
(⇒) Se P 4wf (A) =t (i, f ) então I∗∗ (A) =t (i, f ).
Como P 4wf é a intersecção de todos os modelos 4-estáveis e I∗∗ é um modelo 4-estável,
então todos os fatos verdadeiros, falsos e inconsistentes de P 4wf também são verdadeiros,
falsos e inconsistentes, respectivamente em I∗∗ .
(⇐) Se I∗∗ (A) =t (i, f ) então P 4wf (A) =t (i, f ).
Vamos então mostrar por indução em i, que para todo modelo 4-estável M do programa
P , e para todo i > 0, temos que:
I2i 4 M 4 I2i+1 .
(5.2)
• Base da indução: i = 0.
Sabemos que I0 = ⊥. Logo I0 4 M.
Sabemos que conseqP é antimonotônico, então conseqP (M) 4 conseqP (I0 ). Como
conseqP (I0 ) = I1 e M é um modelo 4-estável (conseqP (M) = M) então temos que M 4 I1 ,
e portanto I0 4 M 4 I1 .
A base da indução é verdadeira.
95
• O passo da indução é similar.
De (5.2), temos que I∗ 4 M 4 I∗ e para cada A ∈ B(P ) temos os seguintes casos:
B Se I∗∗ (A)=t, então I∗ (A)=t, e de I∗ (A) 6 M(A), temos M(A)=t.
B Se I∗∗ (A)=i, então I∗ (A)=I∗ (A)=i, e de I∗ (A) 6 M(A) 6 I∗ (A), temos M(A) = i.
B Se I∗∗ (A)=f, então I∗ (A)=f, e de I∗ (A) > M(A), M(A)=f.
Portanto I∗∗ = P 4wf .
¤
O exemplo a seguir mostra passo a passo o cálculo da instância I∗∗ .
Exemplo 5.1.5 (Cálculo de I∗∗ ) Considere o programa P-Datalog¬ Pcargo e a instância
I, apresentados no exemplo 1.0.1. Vamos calcular a instância I∗∗ correspondente a partir da instância I0 = ⊥ onde todos os fatos são falsos. Os átomos indicadoPor e devedor
serão omitidos pois os valores destes coincidem com os valores apresentados pela instância
inicial I.
Vamos então calcular I1 = conseqP (I0 ).
O programa positivado instanciado pg(Pcargo , I0 ) é descrito a seguir:
cargo(charles) ← t,indicadoPor(charles, joseph), t
cargo(joseph) ← t,indicadoPor(joseph, charles), t
cargo(james) ← t,indicadoPor(james, kevin), t
devedor(james) ←
4-TP1 (⊥):
cargo(charles) ← t,f,t
cargo(joseph) ← t,f,t
cargo(james) ← t,f,t
=⇒
=⇒
=⇒
=⇒
=⇒
cargo(joseph) ← f
cargo(paul) ← f
cargo(john) ← f
cargo(james) ← f
4-TP1 (⊥)= {∼cargo(charles), ∼cargo(james), ∼cargo(john), ∼cargo(joseph), ∼cargo(kevin)}
4-TP2 (⊥):
cargo(charles) ← t,t,t
cargo(joseph) ← t,t,t
cargo(james) ← t,t,t
=⇒
=⇒
=⇒
=⇒
=⇒
96
cargo(charles) ← t
cargo(joseph) ← t
cargo(paul) ← t
cargo(john) ← i
cargo(james) ← t
4-TP2 (⊥)= {◦cargo(charles), ◦cargo(joseph),◦cargo(james), •cargo(john), ∼cargo(kevin),
◦cargo(paul)}=4-TP3 (⊥)
I1 = conseqP (I0 ) ={◦cargo(charles), ◦cargo(joseph),◦cargo(james), •cargo(john),
∼cargo(kevin), ◦cargo(paul)}.
cargo(charles) ← t,indicadoPor(charles, joseph), f
cargo(joseph) ← t,indicadoPor(joseph, charles), f
cargo(paul) ← t,indicadoPor(paul, james), f
devedor(james) ←
4-TP1 (⊥):
cargo(charles) ← t,f,f
cargo(joseph) ← t,f,f
cargo(paul) ← t,f,f
=⇒
=⇒
=⇒
=⇒
=⇒
cargo(joseph) ← f
cargo(paul) ← f
cargo(john) ← f
cargo(james) ← f
4-TP1 (⊥)= {∼cargo(charles), ∼cargo(joseph), ∼cargo(paul), ∼cargo(john), ∼cargo(james),
∼cargo(kevin)}
4-TP2 (⊥):
cargo(charles) ← t,t,f
cargo(joseph) ← t,t,f
cargo(paul) ← t,t,f
=⇒
=⇒
=⇒
=⇒
=⇒
97
cargo(joseph) ← f
cargo(paul) ← f
cargo(john) ← i
cargo(james) ← f
4-TP2 (⊥)= {∼cargo(charles), ∼cargo(joseph), ∼cargo(paul), •cargo(john), ∼cargo(james),
∼cargo(kevin)}=4-TP3 (⊥)
I2 = conseqP (I1 ) ={∼cargo(charles), ∼cargo(joseph), ∼cargo(paul), •cargo(john),
∼cargo(james), ∼cargo(kevin)}.
cargo(charles) ← t,indicadoPor(charles, joseph), t
cargo(joseph) ← t,indicadoPor(joseph, charles), t
devedor(james) ←
4-TP1 (⊥):
cargo(charles) ← t,f,t
cargo(joseph) ← t,f,t
=⇒
=⇒
=⇒
=⇒
=⇒
cargo(joseph) ← f
cargo(paul) ← f
cargo(john) ← f
cargo(james) ← f
∼cargo(kevin)}
4-TP2 (⊥):
cargo(charles) ← t,t,t
cargo(joseph) ← t,t,t
=⇒
=⇒
=⇒
=⇒
=⇒
98
cargo(charles) ← t
cargo(joseph) ← t
cargo(paul) ← t
cargo(john) ← i
cargo(james) ← f
4-TP2 (⊥)= {◦cargo(charles), ◦cargo(joseph), ◦cargo(paul), •cargo(john), ∼cargo(james),
∼cargo(kevin)}=4-TP3 (⊥)
I3 = conseqP (I2 ) ={◦cargo(charles), ◦cargo(joseph), ◦cargo(paul),
•cargo(john), ∼cargo(james), ∼cargo(kevin)}=I5 .
cargo(charles) ← t,indicadoPor(charles, joseph), f
cargo(joseph) ← t,indicadoPor(joseph, charles), f
devedor(james) ←
4-TP1 (⊥):
cargo(charles) ← t,f,f
cargo(joseph) ← t,f,f
=⇒
=⇒
=⇒
=⇒
=⇒
cargo(joseph) ← f
cargo(paul) ← f
cargo(john) ← f
cargo(james) ← f
∼cargo(kevin)}
4-TP2 (⊥):
cargo(charles) ← t,t,f
cargo(joseph) ← t,t,f
=⇒
=⇒
=⇒
=⇒
=⇒
99
cargo(joseph) ← f
cargo(paul) ← t
cargo(john) ← i
cargo(james) ← f
4-TP2 (⊥)= {∼cargo(charles), ∼cargo(joseph), ◦cargo(paul), •cargo(john), ∼cargo(james),
∼cargo(kevin)}=4-TP3 (⊥).
I4 = conseqP (I3 ) = {∼cargo(charles), ∼cargo(joseph), ◦cargo(paul), •cargo(john),
∼cargo(james), ∼cargo(kevin)}=I6
I∗ = I4 = I6 ={∼cargo(charles), ∼cargo(joseph), ◦cargo(paul), •cargo(john), ∼cargo(james),
∼cargo(kevin)}.
I∗ = I3 = I5 ={◦cargo(charles), ◦cargo(joseph), ◦cargo(paul), •cargo(john), ∼cargo(james),
∼cargo(kevin)}.
Portanto I∗∗ = {∼ job(james), • job(john), ∼ job(kevin), ◦ job(paul)}. A instância I∗∗
corresponde à instância J do exemplo 1.0.1, e que no exemplo 4.4.1 foi mostrado ser um
modelo 4-estável.
Exemplo 5.1.6 (Cálculo de I∗∗ para programa com mais de um modelo 4-estável)
Considere o seguinte programa P-Datalog¬ P que possui mais de um modelo 4-estável
apresentado no exemplo 4.5.1:
p←i
q ← ∼r
r ← p, ∼q
s ← ∼ r, p, q
O algoritmo do ponto fixo alternate produz as seguintes instâncias:
I0 ={∼p, ∼q, ∼r, ∼s}
I1 ={•p, ◦q, •r, •s}
I2 ={•p, ∼q, ∼r, ∼s}
I3 ={•p, ◦q, •r, •s}
I4 ={•p, ∼q, ∼r, ∼s}
I∗ ={•p, ∼q, ∼r, ∼s}
I∗ ={•p, ◦q, •r, •s}
100
I∗∗ ={•p}.
Portanto, como era de se esperar, a instância I∗∗ coincide com a intersecção de todos
os modelos 4-estáveis de P apresentada no exemplo 4.5.1.
5.2
Resultados Comparativos
A semântica bem-fundada P-Datalog¬ é uma extensão da definição da semântica bemfundada Datalog¬ [Prz90] (descrita na seção 2.5.3), e portanto produz os mesmos resultados quando aplicada a instâncias consistentes, onde não existem fatos inconsistentes.
O exemplo mostrado a seguir é um clássico: foi discutido por Van Gelder [VRS91],
Przymusinski [Prz92] e por Gelfond e Lifschitz em [GL88]. É o exemplo de um programa
que não é suportado por algumas semânticas por conter recursão negativa (como no programa do exemplo seguinte, onde o predicado intencional win é definido recursivamente
pela sua negação) e, não ser estratificável [AVH95, Lif97]. O programa apresentado neste
exemplo também foi utilizado, com os identificadores dos predicados abreviados, nos exemplos 2.5.15 e 2.5.21.
Exemplo 5.2.1 (Programa Datalog¬ sobre instância sem inconsistências) O programa Pwin : win(X) ←move(X,Y), ∼win(Y), pode ser visto como um jogo entre dois
jogadores que movem sobre os vértices de um grafo direto G. As arestas do grafo são
especificadas pelo predicado move(X,Y). Um vértice X sobre o grafo G é considerado:
• uma posição vencedora: se um dado jogador pode mover de uma posição X para
uma posição Y a qual é uma posição perdedora para o jogador oponente, de forma que o
oponente perde o jogo.
• uma posição perdedora: se todos os movimentos possı́veis a partir desta posição
levam o jogador a uma posição em que o seu oponente é vencedor.
Normalmente, existe também um terceiro tipo de vértice, uma posição indeterminada
(empate), a partir da qual não é possı́vel determinar o resultado do jogo.
Vamos considerar a seguinte instância inicial: {◦ move(a,b), ◦ move(b,c), ◦ move(d,d)}.
Neste caso, o algoritmo do ponto fixo alternante resulta nas seguintes instâncias:
I0 ={∼win(a), ∼win(b), ∼win(c), ∼win(d)}
I1 ={◦win(a), ◦win(b), ∼win(c), ◦win(d)}
I2 ={∼win(a), ◦win(b), ∼win(c), ∼win(d)}
I3 ={∼win(a), ◦win(b), ∼win(c), ◦win(d)}
I4 ={∼win(a), ◦win(b), ∼win(c), ∼win(d)}
I5 ={∼win(a), ◦win(b), ∼win(c), ◦win(d)}.
I∗ ={∼win(a), ◦win(b), ∼win(c), ∼win(d)}.
I∗ ={∼win(a), ◦win(b), ∼win(c), ◦win(d)}.
101
I∗∗ ={∼win(a), ◦win(b), ∼win(c)}.
Tal resultado coincide com o resultado apresentado pela semântica bem-fundada [Prz92].
O modelo indica que c é uma posição perdedora porque não há aresta ligando-a a outra
possı́vel posição. Desta forma b é uma posição vencedora pois o jogador oponente somente
pode mover para a posição c que é uma posição perdedora. No caso da posição a, esta é
uma posição perdedora pois o jogador possui uma única possibilidade de movimentação:
posição b, uma posição vencedora (neste caso vencedora para o oponente). Entretanto,
a posição d não é vencedora nem perdedora, pois a única posição que se pode atingir a
partir de d é a própria posição d, a partir da qual não existe uma estratégia de vitória
para o jogador e nem o força a perder.
Para o mesmo programa apresentado no exemplo anterior, é introduzida uma inconsistência na instância do banco de dados, e os resultados obtidos são analisados.
Exemplo 5.2.2 (Instância com inconsistência) Vamos modificar a instância inicial
apresentada pelo exemplo anterior 5.2.1 para: {◦ move(a,b), • move(b,c), ◦ move(d,d)}
e o programa é o mesmo Pwin .
O algoritmo do ponto fixo alternante produz as seguintes instâncias:
I0 ={∼win(a), ∼win(b), ∼win(c), ∼win(d)}
I1 ={◦win(a), •win(b), ∼win(c), ◦win(d)}
I2 ={∼win(a), •win(b), ∼win(c), ∼win(d)}
I3 ={∼win(a), •win(b), ∼win(c), ◦win(d)}
I4 ={∼win(a), •win(b), ∼win(c), ∼win(d)}
I5 ={∼win(a), •win(b), ∼win(c), ◦win(d)}.
I∗ ={∼win(a), •win(b), ∼win(c), ∼win(d)}.
I∗ ={∼win(a), •win(b), ∼win(c), ◦win(d)}.
I∗∗ ={∼win(a), •win(b), ∼win(c)}.
Portanto a instância I∗∗ , que corresponde à semântica bem-fundada P-Datalog¬ , diz
que é seguro que a posição a não é uma posição vencedora (∼win(a)) apesar de que para
se chegar a tal conclusão usou-se um fato contraditório: •win(b).
Entretanto, em relação à posição b também é usado um fato inconsistente (•move(b,c))
na sua dedução, e esta inconsistência é propagada: é controverso que b é uma posição
vencedora (•win(b)).
O diferencial está no sı́mbolo que precede o fato inconsistente presente no corpo da
regra: o sı́mbolo ∼ da negação por default possui a propriedade de retornar sempre um
102
valor seguro, isto é, seguramente falso ou seguramente verdadeiro que um fato não se
encontra no banco de dados.
Logo, no caso da regra win(a) ← move(a,b),∼win(b), temos o sı́mbolo ∼ precedendo
o fato inconsistente win(b). Já no caso da regra win(b) ← move(b,c),∼win(c), o fato
inconsistente move(b,c) não possui nenhum sı́mbolo precedendo-o e a sua inconsistência
pode ser propagada.
5.3
Implementação do provador P-Datalog¬
Dentro do escopo desta dissertação, a implementação de P-Datalog¬ foi realizada isoladamente, sem a manipulação de grandes coleções de dados persistente, e gerou um provador
de programas P-Datalog¬ . A implementação do provador P-Datalog¬ é descrita a seguir
e no anexo A encontra-se a listagem da implementação.
5.3.1
A linguagem de programação OCaml
A linguagem de programação utilizada na implementação do provador P-Datalog¬ é uma
linguagem funcional que é uma extensão da famı́lia de linguagens ML (Meta-Language),
chamada Objective Caml (OCaml) [Ler02]. OCaml é uma linguagem de programação
desenvolvida pelo INRIA (Institut National de Recherche en Informatique et en Automatique), e é uma derivação da linguagem ML clássica projetada por Robin Milner em 1975
para o provador de teoremas LCF (Logic of Computable Functions). OCaml possui várias
caracterı́sticas comuns com outros dialetos do ML, e provê várias outras caracterı́sticas
próprias como os conceitos de orientação a objeto.
OCaml é uma linguagem funcional, onde funções podem ser encadeadas, podem ser
passadas como argumento de outras funções, e também podem ser armazenadas em estruturas de dados. OCaml é fortemente tipada: o tipo de toda variável e expressão
em um programa é determinado em tempo de compilação, o que reduz a taxa de erros
que ocorrem na execução do programa. Outras caracterı́sticas de OCaml são: suporte
a tipos polimórficos, gerenciamento de memória automático, tipos de dados algébricos,
casamento de padrão. Estas caracterı́sticas possibilitam o rápido desenvolvimento de sistemas, devido às baixas taxas de erro e inferência de tipos. Além disso, um número
pequeno de construtores simples e ortogonais, permite que o programador se concentre
nas dificuldades da aplicação, e desenvolva soluções sucintas e eficientes.
O compilador OCaml gera código comparável a C/C++ em velocidade, e inclui bibliotecas de uso geral para diversas plataformas, incluindo Unix e Windows.
5.3.2
103
Provador P-Datalog¬
A implementação do Provador P-Datalog¬ foi desenvolvida a partir do procedimento
de casamento de padrão “Match”, e do programa “Forward-chaining rule-based ” e suas
estruturas de dados, apresentados em [WH89].
As estruturas de dados utilizadas são fundamentadas em um elemento básico: tuplas do tipo ([lista de strings], valor ), onde lista de strings corresponde a uma lista
representado um átomo e valor corresponde ao valor-verdade do átomo. Por exemplo,
([“cargo”;“james”], t) representa o literal ◦ cargo(james). A partir deste elemento básico
são construı́das listas de tuplas e listas de listas de tuplas para representar as instâncias
do banco de dados e o programa P-Datalog¬ .
Outra estrutura de dados importante é a lista de asssociações de variáveis e constantes
do programa. O elemento básico desta lista é uma tupla do tipo (Variável ; Constante),
que associa uma variável com uma constante. A partir da lista de lista de associações as
regras são instanciadas.
O provador P-Datalog¬ pode ser dividido nos seguintes blocos:
1. Entrada e saı́da de dados;
2. Casamento de padrão e geração de listas de associações;
3. Operador de consequência imediata;
4. Corpo principal.
A entrada de dados é constituı́da por dois arquivos texto: um arquivo que contém o
programa P-Datalog¬ e um arquivo que contém a instância inicial do banco de dados.
O resultado consiste no conjunto de fatos verdadeiros, falsos, inconsistentes e indefinidos deduzidos.
O arquivo texto que contém o programa P-Datalog¬ , possui as seguintes caracterı́sticas:
• Cada linha do arquivo contém uma regra do programa P-Datalog¬ . As regras são
terminadas por “.” (ponto final), e os literais do corpo das regras são separados por
“;” (ponto e vı́rgula);
• Os identificadores de variáveis devem iniciar com letras maiúsculas;
• Os identificadores de constantes devem iniciar com letras minúsculas;
• Os caracteres “o”, “*”, “~”, “:-” denotam, respectivamente, os sı́mbolos “◦”, “•”,
“∼”, “←”;
104
O arquivo texto que contém a instância inicial do banco de dados, possui as seguintes
caracterı́sticas:
• Cada linha do arquivo contém um fato pertencente ao banco de dados;
• Todo fato é precedido dos caracteres “o” ou “*”, que representam respectivamente,
os sı́mbolos “◦” (verdadeiro), “•” (inconsistente);
O caracter “?” que precede fatos da saı́da produzida, denota que o valor-verdade do
fato é indefinido.
Os exemplos seguintes mostram a execução de programas P-Datalog¬ apresentados
anteriormente.
Exemplo 5.3.1 Considere o programa P-Datalog¬ Pwin e a instância inicial I dados no
exemplo 5.2.2.
Arquivo texto com o programa:
win(X):- move(X,Y); ~ win(Y).
Arquivo texto com a instância do banco de dados:
o move(a,b).
* move(b,c).
o move(d,d).
Resultado produzido:
~
~
~
o
move(a,a),
move(b,b),
move(c,c),
move(d,d),
o
*
~
~
move(a,b), ~ move(a,c), ~ move(a,d), ~ move(b,a),
move(b,c), ~ move(b,d), ~ move(c,a), ~ move(c,b),
move(c,d), ~ move(d,a), ~ move(d,b), ~ move(d,c),
win(a), * win(b), ~ win(c), ? win(d)
Exemplo 5.3.2 (Exemplo de motivação) Considere o programa P-Datalog¬ Pcargo e
a instância inicial I dados no exemplo 1.0.1.
Arquivo texto com o programa:
cargo(X):-~ devedor(X); indicadoPor(X,Y); ~ cargo(Y).
Arquivo texto com a instância do banco de dados:
o
o
o
*
o
o
indicadoPor(charles,joseph)
indicadoPor(joseph,charles)
indicadoPor(paul,james)
indicadoPor(john,kevin)
indicadoPor(james,kevin)
devedor(james)
~
?
~
~
~
o
~
~
~
~
~
~
~
~
~
~
~
~
~
o
~
~
105
Resultado produzido:
cargo(james), * cargo(john), ~ cargo(kevin), o cargo(paul),
cargo(charles), ? cargo(joseph),
devedor(charles), o devedor(james), ~ devedor(john), ~ devedor(joseph),
devedor(kevin), ~ devedor(paul), ~ indicadoPor(charles,charles),
indicadoPor(charles,james), ~ indicadoPor(charles,john),
indicadoPor(charles,joseph), ~ indicadoPor(charles,kevin),
indicadoPor(charles,paul), ~ indicadoPor(james,charles),
indicadoPor(james,james), ~ indicadoPor(james,john),
indicadoPor(james,joseph), o indicadoPor(james,kevin),
indicadoPor(james,paul), ~ indicadoPor(john,charles),
indicadoPor(john,james), ~ indicadoPor(john,john),
indicadoPor(john,joseph), * indicadoPor(john,kevin),
indicadoPor(john,paul), o indicadoPor(joseph,charles),
indicadoPor(joseph,james), ~ indicadoPor(joseph,john),
indicadoPor(joseph,joseph), ~ indicadoPor(joseph,kevin),
indicadoPor(joseph,paul), ~ indicadoPor(kevin,charles),
indicadoPor(kevin,james), ~ indicadoPor(kevin,john),
indicadoPor(kevin,joseph), ~ indicadoPor(kevin,kevin),
indicadoPor(kevin,paul), ~ indicadoPor(paul,charles),
indicadoPor(paul,james), ~ indicadoPor(paul,john),
indicadoPor(paul,joseph), ~ indicadoPor(paul,kevin),
indicadoPor(paul,paul)
Capı́tulo 6
Conclusão e trabalhos futuros
O trabalho desta dissertação foi realizado sob a perspectiva da definição de uma linguagem
de consultas a um tipo especial de banco de dados, onde podem existir fatos armazenados
com a identificação de que são inconsistenstes, ou seja, um banco de dados paraconsistente.
Alguns objetivos foram plenamente alcançados, como:
1. A definição da linguagem de consultas P-Datalog¬ ;
2. A definição da semântica bem-fundada de P-Datalog¬ ;
3. A definição do método de avaliação bottom-up de programas P-Datalog¬ ;
4. Implementação do provador de programas P-Datalog¬ .
O desenvolvimento de um provador baseado em um Método de Resolução para programas P-Datalog¬ é deixado como um trabalho a ser futuramente desenvolvido.
Inicialmente a proposta era mais ambiciosa: a sintaxe de um programa P-Datalog¬
envolvia a ocorrência de literais do tipo •A e ◦A no corpo das regras. Os valores-verdade
destes literais seriam dados pelas matrizes da Figura 6.1.
Neste caso, o poder de expressão dos programas P-Datalog¬ seria incrementado com a
possibilidade de discernir entre fatos controversos, seguros ou simplesmente fatos presentes
no banco de dados como controversos ou seguros, como é mostrado no exemplo a seguir:
A
t
i
u
f
•A
f
t
u
f
◦A
t
f
u
f
Figura 6.1: Matriz dos valores-verdade associados aos literais •A e ◦A
106
CAPÍTULO 6. CONCLUSÃO E TRABALHOS FUTUROS
107
Exemplo 6.0.3 Suponha que no exemplo de motivação 1.0.1 da introdução, fosse adicionada às condições necessárias para que um candidato consiga o emprego, a condição
de que seja certo e seguro que o candidato tenha sido indicado por uma pessoa influente.
Não basta a evidência de que ele tenha sido indicado, esta condição deve ser seguramente
positiva. Neste caso, o predicado indicadoPor deveria ser precedido por “◦” na regra do
programa, como é mostrado a seguir:
cargo(x) ← ∼devedor(x), ◦indicadoPor(x,y), ∼cargo(y)
Entretanto, a tentativa de adaptar a semântica bem-fundada para programas que
incluı́ssem os literais ◦A e •A no corpo das regras não foi bem sucedida. Programas
P-Datalog¬ com estes novos literais não se enquadram em nenhum dos programas lógicos
classificados na seção 3.1. Desta forma, é possı́vel que a definição da semântica de programas P-Datalog¬ incrementados com estes novos literais, não seja simplesmente uma
extensão de uma das semânticas existentes, e esta definição é um trabalho a ser desenvolvido futuramente.
Referências Bibliográficas
[ABC99]
M. Arenas, L. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In Proceedings of ACM Symposium on Principles of Database
Systems-ACM PODS’99, Philadelphia, pages 68–79, 1999.
[ABC03]
M. Arenas, L. Bertossi, and J. Chomicki. Answer sets for consistent query answers in inconsistent databases. In Theory and Practice of Logic Programming,
volume 3 (4+5), pages 393–424, July 2003.
[ABK00]
M. Arenas, L. Bertossi, and M. Kifer. Applications of Annotated Predicate
Calculus to Querying Inconsistent Databases. In Computational Logic — CL
2000, First International Conference, London, UK, July 2000. Proceedings,
pages 926–941. Springer Verlag, 2000.
[APP96]
J. J. Alferes, L. M. Pereira, and T. C. Przymusinski. Strong and explicit
negation in non-monotonic reasoning and logic programming. In Logics in
Artificial Intelligence, European Workshop, JELIA, Évora, Portugal, September 30 - October 3, Proceedings, volume 1126 of Lecture Notes in Computer
Science, pages 143–163. Springer, 1996.
[Ari02]
O. Arieli. Paraconsistent declarative semantics for extended logic programs.
Annals of Mathematics and Artificial Intelligence, 36(4):381–417, 2002.
[AVH95]
S. Abiteboul, V. Vianu, and R. Hull. Foundations of databases. AddisonWesley, 1995.
[Bel77]
N. D. Belnap. A useful four-valued logic. In G. Epstein and J.M. Dunn,
editors, Modern Uses of Many-valued Logic. Reidel, 1977.
[BS87]
H. A. Blair and V. S. Subrahmanian. Paraconsistent logic programming. In
Proceedings of the seventh conference on Foundations of software technology
and theoretical computer science, pages 340–360. Springer-Verlag, 1987.
[Car87]
W. A. Carnielli. Systematization of the finite many-valued through the method
of tableaux. The Journal of Symbolic Logic, 52, pages 473–493, 1987.
108
REFERÊNCIAS BIBLIOGRÁFICAS
[CG01]
109
L. Cholvy and C. Garion. A logic to reason on contradictory beliefs with a
majority approach. Workshop IJCAI ”Inconsistency in Data and Knowledge”,
Seattle, August 2001.
[CGM90] U. S. Chakravarthy, J. Grant, and J. Minker. Logic-based approach to semantic query optimization. ACM Trans. Database Syst., 15(2):162–207, 1990.
[CGT90]
S. Ceri, G. Gottlob, and L. Tanca. Logic programming and databases (surveys
in computer science). Springer-Verlag, 1990.
[Che80]
B. F. Chellas. Modal logic, an introduction. Cambridge University Press,
1980.
[Cho98]
L. Cholvy. A general framework for reasoning about contradictory information and some of its applications. ECAI Workshop ”Conflicts among
agents”Brighton, August 1998.
[CM01]
W. A. Carnielli and J. Marcos. Tableau systems for logics of formal inconsistency. In Proceedings of the 2001 International Conference on Artificial
Intelligence - IC-AI, pages 848–852, 2001.
[CS89]
N. C. A. Costa and V. S. Subrahmanian. Paraconsistent logics as a formalism
for reasoning about inconsistent knowledge bases. Artificial Intelligence in
Medicine 1, pages 167–174, 1989.
[dACM00] S. de Amo, W. A. Carnielli, and J. Marcos. Formal inconsistency and evolutionary databases. Logic and Logical Philosophy, 8:115–152, 2000.
[dACM02] S. de Amo, W. A. Carnielli, and J. Marcos. A logical framework for integration
inconsistent information in multiple databases. 2nd Symposium on Foundations of Information and Knowledge Systems, FOIKS 2002, Salzau Castle,
Germany, February 2002, 2284:67–84, 2002.
[Dix96]
J. Dix. Semantics of Logic Programs: Their Intuitions and Formal Properties.
An Overview. In Andre Fuhrmann and Hans Rott, editors, Logic, Action and
Information. Proceedings of the Konstanz Colloquium in Logic and Information (LogIn ’92), pages 241–327. DeGruyter, 1996.
[DP98]
C. V. Damásio and L. M. Pereira. A survey on paraconsistent semantics for
extended logic programas. Handbook of Defeasible Reasoning and Uncertainty
Management Systems, 2:241–320, 1998.
[Fit96]
M. Fitting. First-Order Logic and Automated Theorem Proving. Graduate
Texts in Computer Science - Springer Verlag, second edition, 1996.
110
[GH91]
D. Gabbay and A. Hunter. Making inconsistency respectable: A logical framework for inconsistency in reasoning. In P. Jorrand and J. Kelemen, editors, Proceedings of Fundamentals of Artifical Intelligence Research (FAIR’91),
pages 19–32. Springer-Verlag, 1991.
[GL88]
M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proceedings of the Fifth International Conference on Logic Programming, pages 1070–1080, 1988.
[KPP98]
S. Konieczny and R. Pino-Perez. On the logic of merging. Proceedings of the
Sixth International Conference of the Principles of Knowledge Representation
and Reasoning (KR’98), Trento, Italy., June 2-5 1998.
[Ler02]
X. Leroy. The objective caml system - release 3.06. Documentation and user´s
manual, August 2002.
[Lif97]
S. Lifschitz. Teoria e aplicações de bancos de dados dedutivos. In XVII Congresso da Sociedade Brasileira de Computação/XVI Jornada de Atualização
em Informática, pages 177–219, 1997.
[Llo93]
J. W. Lloyd. Foundations of logic programming. Springer-Verlag, 1993.
[NS97]
A. Nerode and R. A. Shore. Logic for Applications. Graduate Texts in Computer Science - Springer Verlag, second edition, 1997.
[PA92]
L. M. Pereira and J. J. Alferes. Well founded semantics for logic programs
with explicit negation. In European Conference on Artificial Intelligence, pages
102–106, 1992.
[Prz89]
T. C. Przymusinski. Every logic program has a natural stratification and an
iterated least fixed point model. In Proceedings of the eighth ACM Symposium
on Principles of Database Systems-ACM PODS’89, pages 11–21. ACM Press,
1989.
[Prz90]
T. C. Przymusinski. Well-founded semantics coincides with three-valued stable
semantics. Fundamentae Informaticae, XIII, pages 445–463, 1990.
[Prz92]
T. C. Przymusinski. Two simple characterizations of well-founded semantics.
In Mathematical Foundations of Computer Science, pages 451–462, 1992.
[RU95]
R. Ramakrishnan and J.D. Ullman. A survey of deductive database systems.
In J. Logic Programming, pages 125–149, 1995.
111
[Sak92]
C. Sakama. Extended well-founded semantics for paraconsistent logic programs. In Proceedings of the International Conference on Fifth Generation
Computer Systems, pages 592–599. ACM, 1992.
[Sou02]
J. N. Souza. Lógica para ciência da computação: fundamentos da linguagem,
semântica e sistemas de dedução. Ed. Campus, 2002.
[Sub94]
V. S. Subrahmanian. Amalgamating knowledge bases. ACM Transactions on
Database Systems, 1994.
[Van89]
A. Van Gelder. The alternating fixpoint of logic programs with negation. In
Proceedings of the eighth ACM Symposium on Principles of Database SystemsACM PODS’89, pages 1–10, 1989.
[VRS91]
A. Van Gelder, K. Ross, and J. S. Schlipf. The well-founded semantics for
general logic programs. Journal of the ACM, 38(3):620–650, 1991.
[WH89]
P. H. Winston and B. K. P. Horn. Lisp. Addison-Wesley, 1989.
Apêndice A
Listagem da implementação do
provador P-Datalog¬
112
Apêndice A. Listagem da implementação do provador P-Datalog
A. 1
(* Definição de Constantes correspondentes aos símbolos*)
let f = 0;;
(*false = ~ *)
let u = 1;;
(*unknown*)
let i = 2;;
(*inconsistent = * *)
let t = 3;;
(*true*)
let anonymousVariable = "_";;
(* E N T R A D A
D E
D A D O S *)
(*======================================================================
função: valorVerdade
Retorna um caracter que representa o valor verdade correspondente ao
símbolo dado de entrada.
======================================================================*)
let valorVerdade e =
match (e) with
|("*") -> i;
|("~") -> f;
|(_)
-> t;
;;
(*======================================================================
função: trimEmptyString
Retira da lista de strings os strings vazios "".
======================================================================*)
let rec trimEmptyString l =
match l with
[] -> []
|x::xs -> if x = "" then
trimEmptyString xs
else
x::trimEmptyString xs
;;
(*======================================================================
funcao explode
Recebe uma string e retorna uma tupla com uma lista de strings onde
cada elemento da lista corresponde a uma palavra da string recebida,
ou seja, divide a string pelo caracter de espaco " ", e o valor verdade
correspondente.
Ex.: explode "o cargo X Y";;
-> (["cargo";"X";"Y"],t)
======================================================================*)
let explode string =
try
let pos = (Str.search_forward (Str.regexp "[^~^*^o]") string 0 )
in
if pos>0 then
let symbol = String.sub string 0 pos
in
(trimEmptyString (Str.split (Str.regexp "[,.()]")(String.sub
string (pos+1)((String.length string)-(pos+1)))), (valorVerdade symbol))
else
(trimEmptyString (Str.split (Str.regexp "[,.()]") string),t)
with
Not_found -> (trimEmptyString (Str.split (Str.regexp "[,.()]")
string),t);
;;
(*======================================================================
A. 2
funcao trim
Retira os caracteres de espaço (" ") do inicio da string.
======================================================================*)
let trim string =
try
let pos = Str.search_forward (Str.regexp "[^ ]") string 0
in
String.sub string pos ((String.length string)-pos)
with
Not_found -> string;
;;
(*======================================================================
função: splitBody
Recebe um string contendo o corpo da regra e devolve uma lista de
tuplas correspondente.
Ex: splitBody "~ cargo(X,Y);o padrinho(X,Y)."
-> [(["cargo";"X";"Y"],f);(["padrinho";"X";"Y"],t)];
======================================================================*)
let rec splitBody body =
match body with
[] -> []
|x::xs -> (explode (trim x))::(splitBody xs)
;;
(*======================================================================
função explodeRegra
Recebe um string contendo uma regra P-datalog.
Retorna uma lista de tuplas (lista de strings,valor), once cada lista
de strings representa um literal.
A última tupla da lista é a cabeça da regra.
Ex: explodeRegra "cargo(X,Y):-~ deve(X,Y); padrinho(X,Y)."
->
[(["deve";"X";"Y"],f);(["padrinho";"X";"Y"],t);(["cargo";"X";"Y"],t)]
======================================================================*)
let explodeRegra string =
try
let pos = Str.search_forward (Str.regexp "[:]") string 0 in
let head = String.sub string 0 pos in
let body = Str.split (Str.regexp "[;.]") (String.sub string (pos+2)
((String.length string) - (pos+2))) in
(splitBody body)@[(explode (trim head))];
with
Not_found -> [(explode (trim string))];
;;
(*======================================================================
funcao armazenaFato
Entrada:
fato
- string representando uma asserção
baseFatos - lista de asserções (lista de tuplas (lista de strings,
valor), onde cada lista de strings representa um fato
e o valor representa o valor verdade associado a ele)
Efeito:
acrescenta a asserção "fato" na lista de asserções "baseFatos".
A string "fato" é primeiramente transformada em uma tupla (lista de
strings, valor).
Ex.: armazenaFato "o deve(a)" [(["deve";"b"],t)];;
A. 3
-> [(["deve";"b"],t);(["deve";"b"],t)]
======================================================================*)
let armazenaFato fato baseFatos =
List.append (baseFatos) ((explode fato)::[])
;;
(*======================================================================
funcao armazenaRegra
Entrada:
regra
- lista de tuplas (lista de strings, valor), o ultimo
elemento da lista é uma lista que representa o
consequente da regra e os elementos intermediários são
tuplas que representam os antecedentes da regra.
baseRegras - lista de regras (lista de listas, onde
cada uma dessas representa uma regra)
Efeito: acrescenta a regra "regra" na lista de regras "baseRegras".
======================================================================*)
let armazenaRegra regra baseRegras =
List.append (baseRegras) (regra::[])
;;
(*======================================================================
funcao constroiListaFatos
Entrada:
canalEntrada - canal de entrada representando um "ponteiro" para o
arquivo de fatos que foi aberto pela função
carregaFatos.
Efeito: A função varre o arquivo linha por linha e monta uma lista
de listas, onde cada uma destas representa um fato.
======================================================================*)
let rec constroiListaFatos canalEntrada =
try
let
fato = input_line canalEntrada
in
List.append (armazenaFato (trim fato) []) (constroiListaFatos
canalEntrada)
with
End_of_file -> []
;;
(*======================================================================
funcao carregaFatos
Entrada:
arquivo - nome do arquivo contendo a base de fatos. O arquivo
deve possuir um fato em cada linha, em texto simples.
Efeito: A função carrega todos os fatos presentes no arquivo e retorna
uma lista de fatos. Cada fato é representado por uma lista de strings.
A função constroiListaFatos é utilizada para tal.
Ex.: Se o arquivo "baseFatos.txt" contem as seguintes linhas:
~ deve(a).
~ deve(b).
então a função retorna a lista:
-> [(["deve";"a"],f);(["deve";"b"],f)]
======================================================================*)
A. 4
let carregaFatos arquivo =
let canalEntrada = open_in arquivo
in
constroiListaFatos canalEntrada
;;
(*======================================================================
funcao constroiListaRegras
Entrada:
canalEntrada - canal de entrada representando um "ponteiro" para o
arquivo de regras que foi aberto pela função
carregaRegras.
Efeito: Esta função é utilizada pela função "carregaRegras"
e é responsável por carregar do arquivo todas as regras presentes
no mesmo e montar uma lista dessas regras.
======================================================================*)
let rec constroiListaRegras canalEntrada =
try
let
regra = input_line canalEntrada
(* le a linha referente a
regra *)
in
print_string "Regra = "; print_string regra; print_newline();
(explodeRegra regra)::(constroiListaRegras canalEntrada)
with
End_of_file -> []
;;
(*======================================================================
funcao carregaRegras
Entrada:
arquivo - nome do arquivo contendo a base de regras.
Efeito: A função carrega todos as regras presentes no arquivo e retorna
uma lista de regras.
OBS: as regras são armazenadas no arquivo da sequinte forma:
======================================================================*)
let carregaRegras arquivo =
let canalEntrada = open_in arquivo
in
constroiListaRegras canalEntrada;
;;
(*======================================================================
Função equal
Parâmetros: i, j
Retorna true se i=j e false caso contrário.
È utilizada na função inter
======================================================================*)
let equal i j = (i=j)
;;
(*======================================================================
Função compare
Parâmetros: a b
Retorna o se a=b, 1 se a>b e -1 se a<b
È utilizada em List.sort
======================================================================*)
let compare a b =
if (a=b) then 0
else if (a>b) then 1
A. 5
else -1
;;
(*======================================================================
Função inter
Parâmetros: l1, l2 -> duas listas
Retorna uma lista com a instersecção entre as duas listas de entrada
======================================================================*)
let rec inter l1 l2 =
match l1 with [] -> []
| x::xs ->
if (x=List.hd l2) then
[x]@inter xs (List.tl l2)
else match x with
(l,v) -> [(l, u)]@inter xs (List.tl l2);;
(*======================================================================
Função min
Parametros: v1, v2
Retorna no menor valor dado de entrada.
======================================================================*)
let min v1 v2 =
if (v1 < v2) then v1
else v2;;
(*======================================================================
FUNÇÃO: print_list
Imprime elementos de uma lista de strings
PARÂMETROS:
l: Lista de strings
======================================================================*)
let rec print_list l =
match l with
[] -> ();
| x::xs -> print_string x;
if xs <> [] then
begin
print_string ",";
print_list xs;
end
;;
(*======================================================================
Função print_truth_value
Concatena valor verdade v para caracter correspondente:
0=~, 1=U, 2=*, 3=o
Parametros: v
======================================================================*)
let print_truth_value v =
match (v) with
(0) -> print_string "~ ";
|(1) -> print_string "? ";
|(2) -> print_string "* ";
|(3) -> print_string "o ";
|(_) -> print_string "error"
;;
(*======================================================================
Função print_one_tupla
Parametros: b
Imprime uma tupla b. Usada em print_list_tupla
A. 6
Por exemplo, se b=(["moves";"a";"b"],2) imprime "* moves a b"
======================================================================*)
let print_one_tupla b =
match b with
(l,v) -> print_truth_value v;
match l with
[] -> ()
|x::xs -> print_string x;
if xs<>[] then
begin
print_string "(";
print_list xs;
print_string ")";
end;
;;
(*======================================================================
Função print_list_tupla
Parametros: l
Imprime uma lista de tuplas (lista de strings, int).
Por exemplo, se l=[(["moves";"a";"b"],2);(["moves";"b";"c"],3)],
imprime "*moves a b, omoves b c"
======================================================================*)
let rec print_list_tupla l =
match l with
[] -> ();
|x::xs ->
print_one_tupla x;
if xs <> [] then
begin
print_string ", ";
print_newline();
print_list_tupla xs;
end
;;
(*======================================================================
FUNÇÃO: print_one_binding
Imprime elementos de uma lista de associações
PARÂMETROS:
b: Lista de associações
======================================================================*)
let rec print_one_binding b =
match b with
[] -> print_string "]";
|(a,b)::xs ->
print_string "(";print_string a;print_string ",";print_string
b;print_string ")";
print_one_binding xs;
;;
(*======================================================================
FUNÇÃO: print_bindings
Imprime elementos de uma lista de associações
PARÂMETROS:
b: Lista de lista de associações
======================================================================*)
let rec print_bindings b =
match b with
[] -> print_newline ();
A. 7
|x::xs ->
print_string "[";
print_one_binding x;
print_string " ; ";
print_bindings xs;
;;
(*======================================================================
FUNÇÃO: limpalista
percorre lista l e retira elementos iguais a e
PARÂMETROS:
l: Lista de lista de strings
e: elemento da lista a ser retirado
======================================================================*)
let rec limpalista l e=
match l with
[] -> []
| x::xs -> if (x=e) then
limpalista xs e
else [x]@(limpalista xs e)
;;
(*======================================================================
FUNÇÃO: atom
Retorna true se p é uma lista que contém somente um string, senao
retorna false
PARÂMETROS:
p: Lista de strings
======================================================================*)
let atom p =
match p with []-> false
| x::xs -> (xs = [])
;;
(*======================================================================
FUNÇÃO: variable
Retorna true se p é uma lista que contém somente um string que
possui o 1º caracter está em maiúscula senao retorna false
PARÂMETROS:
p: Lista de strings
======================================================================*)
let variable p =
match p with
[] -> false
|x::xs -> ((((Char.code x.[0])>=(Char.code 'A'))&&((Char.code
x.[0])<=(Char.code 'Z')))
or (x=anonymousVariable)) && (xs = [])
;;
(*======================================================================
FUNÇÃO: listp
Retorna true se p é uma lista, senao retorna false
PARÂMETROS:
p: Lista de strings
======================================================================*)
let listp p =
match p with
[] -> false
|x::xs -> (xs <> [])
;;
A. 8
(*======================================================================
FUNÇÃO: rule_ifs
Retorna lista tuplas contendo os antecedentes da regra.
Por exemplo:
[(["deve";X"],f);(["padrinho";"X";"Y"],t);(["cargo";"Y"],f)]
PARÂMETROS:
rule: tupla contendo a regra = (id_regra, lista_com_corpo_da_regra)
======================================================================*)
let rec rule_ifs rule =
match rule with [] -> []
| x::xs -> if (xs=[]) then []
else [x]@(rule_ifs xs)
;;
(*======================================================================
FUNÇÃO: rule_then
Retorna lista com a tupla que representa consequente da regra, a
ultima tupla da lista que representa a regra.
PARÂMETROS:
rule: tupla contendo a regra = (id_regra,
lista_com_corpo_da_regra)
======================================================================*)
let rec rule_then rule =
match rule with [] -> ([],0)
| x::xs -> if (xs=[]) then x
else (rule_then xs)
;;
(*======================================================================
FUNÇÃO: mymatch
Faz o casamento de padrao entre p e d, a partir de uma lista de
associações bindings, e retorna a lista de associações resultante
deste casamento de padrão. Se p é uma variável substuir p pelo
valor associado pela lista de bindings e tentar fazer o casamento
novamente. Note que "_" representa uma "anonymous variable".
PARÂMETROS:
p:
lista de strings que inicialmente representa um
antecedente da regra
bindings:
lista de associações
d:
lista de strings que inicialmente representa um
fato do mundo
======================================================================*)
let rec mymatch p bindings d=
if (variable p) then
let name_var = List.hd p in
if (List.mem_assoc name_var bindings) then
if (name_var = anonymousVariable) then (*new*)
bindings
else (*substitui o nome da variável pelo valor associado e
chama mymatch novamente *)
mymatch [(List.assoc name_var bindings)] bindings d
else
if (name_var = anonymousVariable) then
(*new*)
List.append [(name_var,anonymousVariable)] bindings
else
(* a variável não possui valor associado, então um
novo par é inserido*)
List.append (List.combine [name_var] d) bindings
A. 9
else if (atom p) && (atom d) then
(* match_atoms *)
if (List.hd p) = (List.hd d) then
bindings
else
[("FAIL","FAIL")]
else if (listp p) && (listp d) then
(*match_pieces p d bindings*)
let result = mymatch [List.hd p] bindings
[List.hd d] in
if (result = [("FAIL","FAIL")]) then
[("FAIL","FAIL")]
else mymatch (List.tl p) result (List.tl d)
else [("FAIL","FAIL")];;
(*======================================================================
FUNÇÃO: try_assertion
Faz o casamento de padrão (MYMATCH) de pattern com assertion, a
partir de uma lista de associações, e retorna um lista de lista de
associações resultante:
[("EMPTY","EMPTY")]-> representa sucesso no match, porem não gerou
associações
[] -> representa falha no match
caso contrario -> representa sucesso no match e gera associações.
PARÂMETROS:
assertion
lista com um fato do mundo
pattern
lista com um antecedente de uma regra
bindings:
======================================================================*)
let try_assertion pattern bindings assertion =
let result = mymatch (fst pattern) bindings (fst assertion) in
if result = [] then
(* mymatch não falhou, apenas retornou e não gerou associação *)
List.append [("EMPTY","EMPTY")] bindings
else if (List.mem_assoc "FAIL" result) then
if (snd pattern)=f then
if bindings=[] then
[("EMPTY","EMPTY")]
else
bindings
else
(* mymatch falhou, então retorna lista vazia*)
[]
else
(* mymatch sucedeu e retornou uma lista de associações *)
result;;
(*======================================================================
FUNÇÃO: limpalistavazia
percorre lista l e retira elementos []
PARÂMETROS:
l: Lista de lista de strings
======================================================================*)
let rec limpalistavazia l =
match l with
[] -> []
| x::xs -> if (x=[]) then limpalistavazia xs
else [x]@(limpalistavazia xs);;
A. 10
(*======================================================================
FUNÇÃO: match_pattern_to_assertion
Aplica TRY_ASSERTIONS a todos fatos da lista de fatos, e retorna um
lista de lista de associações
PARÂMETROS:
assertions lista com todos fatos do mundo
pattern
bindings:
======================================================================*)
let rec match_pattern_to_assertion assertions pattern resultbinding
bindings=
match assertions with
[] -> resultbinding
| x::xs -> let bind = try_assertion pattern bindings x
in
if (bind=[]) or (List.mem bind resultbinding) then
match_pattern_to_assertion xs pattern resultbinding
bindings
else
match_pattern_to_assertion xs pattern
(bind::resultbinding) bindings
;;
(*======================================================================
FUNÇÃO: filter_binding
Aplica MATCH_PATTERN_TO_ASSERTION a cada ambiente da lista de
associações, e retorna a lista de lista de associacoes.
PARÂMETROS:
assertions
lista com todos fatos do mundo
pattern
bindingslista
======================================================================*)
let rec filter_binding assertions pattern bindingslist =
List.flatten(List.map (match_pattern_to_assertion assertions pattern
[]) bindingslist);;
(*======================================================================
FUNÇÃO: apply_filters
Aplica FILTER_BINDING a cada antecedente de uma regra,
e retorna a lista de lista de associações.
PARÂMETROS:
assertions
lista com todos fatos do mundo
patterns
lista com todos os antecedente de uma regra
bindingslista
======================================================================*)
let rec apply_filters assertions patterns bindingslist =
match patterns with
[]-> bindingslist
| x::xs ->
let resultbindings = (filter_binding assertions x
bindingslist) in
apply_filters assertions xs resultbindings;;
(*======================================================================
FUNÇÃO: instantiate_variable
Verifica o consequente da regra para cada ambiente de associação da
lista, e retorna a lista contendo o fato deduzido.
PARÂMETROS:
pattern
lista com o consequente da regra
A. 11
alista
======================================================================*)
let rec instantiate_variable pattern alist =
if (variable pattern) then
let name_p = (List.hd pattern) in
if (List.mem_assoc name_p alist) then
[List.assoc name_p alist]
else
[] (*não tem valor associado em bindings *)
else if (atom pattern) then
pattern
else
(instantiate_variable [List.hd pattern] alist)
@(instantiate_variable (List.tl pattern) alist)
;;
(*======================================================================
FUNÇÃO: instantiate_body
Calcula o valor-verdade associado ao corpo da regra para uma dada
PARÂMETROS:
rule_ifs_list
bindinglist
assertions
lista com os literais do corpo da regra
lista com fatos do mundo que estão sendo
deduzido
oldassertions
lista com fatos do mundo a partir dos
quais é gerado a versão
instanciada positivada da regra.
value
valor-verdade do corpo da regra
======================================================================*)
let rec instantiate_body rule_ifs_list bindinglist assertions
oldassertions value =
match rule_ifs_list with
[] -> value
|x::xs ->
if ((fst x)=[anonymousVariable]) then
(* O valor verdade do corpo da regra eh o valor associado a
variavel anonima *)
(snd x)
else
let result = (instantiate_variable (fst x) bindinglist) in
if ((snd x) = f) then (* literal negativo *)
if (List.mem_assoc result oldassertions) then
let oldvalue = (List.assoc result oldassertions) in
if (oldvalue = f) then
instantiate_body xs bindinglist assertions
oldassertions (min value t)
else if (oldvalue = u) then
oldassertions (min value oldvalue)
else f
else
(* este caso não deveria acontecer, uma vez que todos os
fatos sao explicitamente negados *)
instantiate_body xs bindinglist assertions oldassertions
(min value t)
else (* literal positivo *)
A. 12
if (List.mem_assoc result assertions) then
let value_literal = (List.assoc result assertions) in
if (snd(x) = t) then
oldassertions (min value_literal value)
else f
else f
;;
(*======================================================================
FUNÇÃO: assertion_remember
Inclui um novo fato se e somente se ele ainda não está presente na
lista original.
Retorna lista de fatos.
PARÂMETROS:
assertions
lista de fatos
newassertion
fato a ser inserido
======================================================================*)
let assertion_remember assertions newassertion =
if (List.mem_assoc (fst newassertion) assertions) then
(* novo fato já se encontra na lista *)
begin
let oldvalue = (List.assoc (fst newassertion) assertions)
in
if (oldvalue < (snd newassertion)) then
(* o valor do novo fato é maior que o do já existente*)
(* remover fato anterior e inserir o novo*)
List.sort compare ((List.remove_assoc (fst newassertion)
assertions)@[newassertion])
else
assertions
end
else
List.sort compare (assertions @ [newassertion]);;
(*======================================================================
Função: instantiate_consequents
Rotina auxiliar recursiva: testa consequentes com cada lista de
bindings. Quando é possivel instanciar o consequente, é necessario
então, calcular o valor-verdade resultante do corpo da implicação,
e atribuí-lo a tupla que representa o novo fato deduzido.
Parâmetros:
rule
tupla contendo uma regra
assertions
lista de tuplas que representam os fatos gerados
oldassertions
lista de tuplas que representam os fatos baseado
nos quais os literais negativos serao positivados
bindings
lista contendo ambientes de ligação
======================================================================*)
let rec instantiate_consequents rule assertions oldassertions bindinglist
=
match bindinglist with [] -> assertions
| x::xs ->
let result = instantiate_variable (fst (rule_then rule)) x in
if (result = []) then
assertions
else
let value = (instantiate_body (rule_ifs rule) x
A. 13
assertions oldassertions t) in
let newassertions = (assertion_remember assertions
(result,value)) in
(* verifica o consequente da regra com outra lista de
associações *)
instantiate_consequents rule newassertions oldassertions
xs
;;
(*======================================================================
FUNÇÃO: use_rule
Aplica uma regra a uma lista de fatos do mundo.
Retorna a lista de fatos do mundo contendo os novos fatos
concluídos.
PARÂMETROS:
rule
lista contendo a regra
assertions
lista de fatos do mundo
oldassertions
======================================================================*)
let use_rule assertions oldassertions rule=
let blist = (apply_filters assertions (rule_ifs rule) [[]]) in
if (blist = []) then
assertions
else
instantiate_consequents rule assertions oldassertions blist;
;;
(*======================================================================
Função auxiliar: use_rulelist
Executa todas as regras da lista e retorna nova lista de fatos do
mundo.
Parâmetros:
assertions
lista de fatos do mundo
list
lista de regras
oldassertions
velha lista dos fatos do mundo
======================================================================*)
let rec use_rulelist assertions oldassertions list =
match list with [] -> assertions
| x::xs -> let newassertions = (use_rule assertions
oldassertions x) in
use_rulelist newassertions oldassertions xs;;
(*======================================================================
FUNÇÃO: conseqp
(Foward_chain)
Percorre a lista de regras e lista de fatos verificando se novos
fatos são deduzidos. Caso novos fatos sejam inseridos na lista de
fatos do mundo, executa novamente a lista de regras com estes
novos fatos até que nenhum novo fato seja concluído.
PARÂMETROS:
rulelist
lista de regras
assertions lista de fatos do mundo
======================================================================*)
let rec conseqp assertions oldassertions rulelist blist =
let newassertions = (use_rulelist assertions oldassertions
rulelist) in
if (newassertions = assertions) then
newassertions
else
conseqp newassertions oldassertions rulelist blist ;
A. 14
;;
(*======================================================================
FUNÇÃO: i_star_star
Resulta a semântica de um dado programa (conjunto de regras)
P-datalog, que equivale a instancia I**.
PARÂMETROS:
rules
conjunto de regras do programa P-datalog
i
array de instâncias
n
instância anterior
blist
lista de bindings
======================================================================*)
let rec i_star_star rules i n blist assertions=
let ind =(n+1) mod 4 in
i.(ind)<-conseqp assertions i.(n mod 4) rules blist;
print_string "I"; print_int (n+1); print_string " = ";
print_list_tupla i.(ind); print_newline();
if ((i.(0)=i.(2))&&(i.(1)=i.(3))) then
inter i.(2) i.(3)
else if (i.(ind)=i.(n mod 4)) then
i.(ind)
else
i_star_star rules i (n+1) blist assertions
;;
(*======================================================================
FUNÇÃO: bindPair
Monta uma tupla (var,const) e a insere na lista binding.
PARÂMETROS:
binding var const
*======================================================================*)
let bindPair binding var const =
(var,const)::binding
;;
(*======================================================================
FUNÇÃO: bindVarToConst
Monta uma tupla com a variável var e cada uma das constantes da
lista const, e insere a tupla na lista binding.
PARÂMETROS:
consts var binding
*======================================================================*)
let bindVarToConst consts var binding =
List.map (bindPair binding var) consts
;;
(*======================================================================
FUNÇÃO: filterBind
Para cada lista de associações da lista bindlist, adiciona uma
nova tupla com a variável var e cada uma das constantes da lista
const.
PARÂMETROS: consts var bindlist
*======================================================================*)
let filterBind consts var bindlist =
List.flatten(List.map (bindVarToConst consts var) bindlist)
;;
(*======================================================================
FUNÇÃO: applyVar
PARÂMETROS: consts vars bindlist
*======================================================================*)
let rec applyVar consts vars bindlist =
match vars with
A. 15
[] -> bindlist
|x::xs ->
let bindResult = filterBind consts x bindlist
in
applyVar consts xs bindResult
;;
(*======================================================================
FUNÇÃO: literalScanConstVar
Escaneia um literal de uma regra e retorna listas de constantes e
variáveis
PARÂMETROS:
l dom
*======================================================================*)
let rec literalScanConstVar l dom =
match l with
[] -> dom
| x::xs ->
if (variable [x]) then
if not (List.mem x (snd dom)) then
literalScanConstVar xs ((fst dom), x::(snd dom))
else
literalScanConstVar xs dom
else if not (List.mem x (fst dom)) then
literalScanConstVar xs (x::(fst dom), (snd dom))
else
literalScanConstVar xs dom
;;
(*======================================================================
FUNÇÃO: ruleScanConstVar
Escaneia uma regra r e retorna um par com listas de constantes e
variáveis
PARÂMETROS: r dom
*======================================================================*)
let rec ruleScanConstVar r dom=
match r with
[]-> dom
|((head::tail),_)::xs -> let domResult = literalScanConstVar tail dom
in
ruleScanConstVar xs domResult
|_ -> dom
;;
(*======================================================================
FUNÇÃO: programScanConstVar
Escaneia as regras do program p e retorna duas listas: uma de
constantes e outra de variáveis
PARÂMETROS:
p
lista contendo as regras do programa
dom ([constantes],[variáveis]) par contendo uma lista de
constantes e lista de variáveis encontradas no programa
EXEMPLO:
dom = (["kevin"; "john"; "james"; "paul"; "joseph"; "charles"],
["Y"; "X"]);
*======================================================================*)
let rec programScanConstVar p dom =
match p with
[] -> dom
|x::xs ->
let domResult = ruleScanConstVar x dom
in
A. 16
programScanConstVar xs domResult
;;
(*======================================================================
FUNÇÃO: addFactsToProgram facts rules
adiciona facts positivos e inconsistentes como clausulas unitarias
do programa rules.
PARÂMETROS:
facts rules
*======================================================================*)
let rec addFactsToProgram facts rules=
match facts with
[] -> rules
|x::xs -> match (snd x) with
2 -> addFactsToProgram xs
(((["_"],2)::[(fst(x),3)])::rules)
|3 -> addFactsToProgram xs ([x]::rules)
|4 -> addFactsToProgram xs ([x]::rules)
|_ -> addFactsToProgram xs rules
;;
(*======================================================================
FUNÇÃO: instantiateOneRule
Produz uma lista com os átomos instanciados de uma regra.
PARÂMETROS:
assertions rule binding
======================================================================*)
let rec instantiateOneRule assertions rule binding =
match rule with
[] -> assertions
| x::xs ->
let result = instantiate_variable (fst x) binding in
if (result = []) then
instantiateOneRule assertions xs binding
else
let newassertions = (assertion_remember assertions
(result,0)) in
instantiateOneRule newassertions xs binding
;;
(*======================================================================
FUNÇÃO: instantiateRules
Produz uma lista com os átomos instanciados de uma lista de
regras.
PARÂMETROS:
assertions rules binding
======================================================================*)
let rec instantiateRules assertions rules binding =
match rules with
[] -> assertions
|x::xs ->
let newassertions = instantiateOneRule assertions x binding in
instantiateRules newassertions xs binding
;;
(*======================================================================
FUNÇÃO: instantiateProgramPredicates
Produz uma lista com os átomos instanciados de um programa
a partir de cada lista de bindings.
PARÂMETROS:
assertions rules blist
A. 17
======================================================================*)
let rec instantiateProgramPredicates assertions rules blist =
match blist with
[] -> assertions
|x::xs ->
let newassertions = instantiateRules assertions rules x in
instantiateProgramPredicates newassertions rules xs
;;
(*======================================================================
Corpo principal
======================================================================*)
let mainloop =
print_newline();
print_newline();
print_string " ============= R E S U L T A D O =============== ";
print_newline();
print_newline();
let rules = (carregaRegras "C:/Meus
documentos/Mestrado/ocamlsources/regrasMulti.txt") in
let facts = (carregaFatos "C:/Meus
documentos/Mestrado/ocamlsources/fatosMulti.txt") in
let ruleslist = addFactsToProgram facts rules in
let (consts,vars) = programScanConstVar ruleslist ([],[]) in
let blist = applyVar consts vars [[]] in
(* Gera \neg B(P) *)
let initialAssertions = instantiateProgramPredicates [] rules blist
in
let i=Array.create 4 [] in
let l = i_star_star ruleslist i 0 blist initialAssertions in
print_newline();
print_string "I** = ";
print_newline();
print_list_tupla l;
print_newline();
print_newline();
print_newline();
print_string "DONE \n";
;;
let main() = mainloop;;

P-Datalog - Universidade Federal de Uberlândia

Transcrição

Documentos relacionados

SHELLAC 78`

A Semente de Discrepância

Ficha de Controle - FIC Exóticas

Teorema de Ptolomeu

risposta della conferenza. episcopale brasiliana

Reitores na Moncloa - Duvi

Terrorismo Poético

RAFAEL CUNHA DE ALMEIDA

1a Frequência — 2002/2003

Copyright, Voice Of God Recordings