Datalog

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 inicio 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[editar | editar código-fonte]

Em contraste com o Prolog, a datalog:

  1. destiva termos complexos como argumento do predicado. Ex: P(1,2) é permitido, mas P(F(1),2) não é.
  2. impoem certas restrições no stratification para o uso de negação e recursão
  3. 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 principio, 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 idéias 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[editar | editar código-fonte]

universidade
Aluno Materia Nota
Alberto Calculo 10
Lucas Banco de Dados 8
Andréia Programação 7
Lucas Calculo 5
Mariana Fisica 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éz 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[editar | editar código-fonte]

As principais sintaxes da linguagem Datalog são:

Literais[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

É possivel 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.

  1. 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
  2. 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[editar | editar código-fonte]

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