Datalog

A Datalog é uma linguagem de consulta não procedural baseada na linguagem de programação lógica Prolog. Foi baseada na lógica relacional, na qual o usuário descreve as informações desejadas, sem fornecer um procedimento específico para obter essas informações. A linguagem foi originado no início da programação lógica, mas ganhou reconhecimento por volta de 1978, quando Hervé Gallaire e Jack Minker organizaram um workshop sobre bancos de dados lógicos.

Características da linguagem

Em contraste com o Prolog, a datalog:

desativa termos complexos como argumento do predicado. Ex: P(1,2) é permitido, mas P(F(1),2) não é.
impoem certas restrições no stratification para o uso de negação e recursão
permite apenas variaveis restritas, isto é, cada variavel na conclusão da regra, deve aparecer na sua forma não negada, na premissa dessa.

A Datalog é a princípio, uma linguagem academica de banco de dados, que nunca conseguiu um grande sucesso nos banco de dados comerciais, apesar de suas vantagens em comparação com outras linguagens como SQL: pesquisas recursivas e uma semantica limpa. Mesmo assim, alguns SGDB usaram as ideias criadas para a Datalog. Por exemplo, a SQL99 incluiu a busca recursiva e o algoritmo Magic Set foi implementado no DB2 da IBM.

Duas importantes extensões foram feitas para a Datalog, a extensão para permitir a Programação Orientada a Objeto e para disjunção na declaração das cláusulas. Ambas, tiveram um importante impacto na definição da semantica e na execução de um interpretador do Datalog.

Estrutura Básica

universidade
Aluno	Materia	Nota
Alberto	Calculo	10
Lucas	Banco de Dados	8
Andréia	Programação	7
Lucas	Calculo	5
Mariana	Física	10
Fernando	Calculo	7

Um programa Datalog consiste em um conjunto de regras. Consideremos uma regra de Datalog para definir uma relação de visualização v1, contendo a matéria Calculo e as notas maior que 6.

v1(A,B) :- universidade(A, "Calculo", B), B > 6

Os resultados serão:

Aluno	Nota
Alberto	10
Fernando	7

Essa declaração é equivalente a:

para todo A,B
se (A, "Calculo",B) esta_contido_em Universidade e B > 6 
então (A,B) esta_contido_em v1

Podemos recuperar a nota recebida de fernando, na relação de visualização v1 escrevendo a seguinte consulta:

? v1 ("Fernando", B)

A resposta para a consulta é:

(Fernando, 7)

Em geral, precisamos de mais de uma regra para definir uma relação de visualização. Cada regra define um conjunto de tuplas que a relação de visualização precisa conter. O programa Datalog a seguis especifica se o aluno passou de ano:

Resultado_Final(A, "Passou de Ano") :- universidade (A, N, B), B >= 5
Resultado_Final(A, "Reprovado") :- universidade (A, N, B), B < 5

As implementações da Datalog reconhecem atributos de uma relação por posição. Assim, as regras Datalog são compactas, se comparadas com as consultas SQL. Entretanto, quando as relações possuem um grande número de atributos ou quando a ordem ou o número de atributos das relações mudam, a notação posicional pode ser confusa e propensa a erros. Então Podemos criar um atributo nomeado ao invés de atributos possicionais. Então, a regra V1 escrita acima, pode ser definida como:

v1 (nome A, nota B) :- universidade (nome A, materia "Calculo", nota B), B > 6

Sintaxe das regras Datalog

As principais sintaxes da linguagem Datalog são:

Literais

Uma literal positiva e uma literal negativa tem as respectivas formas

p(t1,t2,..,tn) e not p(t1,t2,..,tn)

onde p é o nome de uma relação com n atributos e t1,t2,..,tn são constantes ou variáveis.

Fatos

Um fato tem a forma:

p(v1, v2,..., vn)

e indica que a tupla (v1, v2,...,vn) está na relação p. Na tabela universidade, cada linha representa um fato.

Regras

As regras são construídas de literais e têm a forma:

p(t1,t2,..,tn) :- L1, L2,L3,..,Ln

onde cada Li é uma literal. A literal p(t1,t2,...,tn) é chamado o cabeçalho da regra e o restante das literais constitui o corpo da regra. Um programa Datalog consiste em um conjunto de regras; a ordem em que elas são escritas não tem significância.

Segurança

É possível escrever regras que geram um número infinito de respostas. Considere a regra

infinito (X, Y) :- X > Y

Como a relação definindo > é infinita, essa regra geraria um número infinito de fatos, cujo cálculo correspondentemente, levaria uma quantidade infinita. Para que essas possibilidades sejam evitadas, as regras Datalog são necessárias satisfazer as seguintes condições de segurança.

Cada variável que aparece no cabeçalho da regra também aparece em uma literal positiva não aritmética, no corpo da regra
Cada variável aparecendo em uma literal negativa no corpo da regra também aparece em alguma literal positiva no corpo da regra

Se todas as regras em um programa Datalog satisfizerem essas condições de segurança, então, todas as relações de visualização definidas no programa podem ser mostradas como finita, desde que as relações de banco de dados sejam finitas.

Ligações externas

Coral Database Project - Uma implementação da Datalog
XSB - Uma implementação Prolog, que aceita consultas de banco de dados