Registro de dados - Datalog

Datalog é uma linguagem de programação lógica declarativa que sintaticamente é um subconjunto do Prolog . Geralmente é usado como uma linguagem de consulta para bancos de dados dedutivos . Nos últimos anos, a Datalog encontrou novos aplicativos em integração de dados , extração de informações , rede , análise de programas , segurança , computação em nuvem e aprendizado de máquina .

Suas origens remontam ao início da programação lógica , mas se tornou uma área separada por volta de 1977, quando Hervé Gallaire e Jack Minker organizaram um workshop sobre lógica e bancos de dados . David Maier é responsável por cunhar o termo Datalog.

Recursos, limitações e extensões

Ao contrário do Prolog, as declarações de um programa Datalog podem ser declaradas em qualquer ordem. Além disso, as consultas do Datalog em conjuntos finitos têm a garantia de terminar , portanto, o Datalog não tem o operador cut do Prolog . Isso torna o Datalog uma linguagem totalmente declarativa .

Em contraste com Prolog, Datalog

1. não permite termos complexos como argumentos de predicados , por exemplo, p (1, 2) é admissível, mas não p (f (1), 2),
2. impõe certas restrições de estratificação sobre o uso de negação e recursão ,
3. requer que cada variável que aparece na cabeça de uma cláusula também aparece em um positivo nonarithmetic (isto é, não negada) literal no corpo da cláusula,
4. requer que cada variável que aparece em um literal negativo no corpo de uma cláusula também apareça em algum literal positivo no corpo da cláusula

A avaliação da consulta com Datalog é baseada na lógica de primeira ordem e, portanto, é sólida e completa . No entanto, o Datalog não é Turing completo e, portanto, é usado como uma linguagem de domínio específico que pode tirar proveito de algoritmos eficientes desenvolvidos para resolução de consultas. Na verdade, vários métodos têm sido propostos para realizar consultas de forma eficiente, por exemplo, o algoritmo Magic Sets, programação lógica tabelada ou resolução SLG.

Alguns sistemas de banco de dados amplamente usados ​​incluem ideias e algoritmos desenvolvidos para Datalog. Por exemplo, o padrão SQL: 1999 inclui consultas recursivas e o algoritmo Magic Sets (inicialmente desenvolvido para a avaliação mais rápida de consultas do Datalog) é implementado no DB2 da IBM . Além disso, os motores de registro de dados estão por trás de sistemas de banco de dados especializados , como o banco de dados do Intellidimension para a web semântica .

Várias extensões foram feitas para Datalog, por exemplo, para suportar funções agregadas , para permitir a programação orientada a objetos ou para permitir disjunções como cabeçalhos de cláusulas . Essas extensões têm impactos significativos na definição da semântica do Datalog e na implementação de um interpretador do Datalog correspondente.

Fragmentos

Os programas de registro de dados podem ou não usar negação em corpos de regras: os programas de registro de dados com negação geralmente precisam usá-los como negação estratificada para garantir que a semântica seja bem definida. Os programas de registro de dados podem ou não usar desigualdades entre variáveis ​​em corpos de regras.

Alguns fragmentos sintáticos do Datalog foram definidos, como o seguinte (do mais restrito ao menos restrito):

• Datalog linear , onde os corpos das regras devem consistir em um único átomo
• Datalog guardado , onde para cada regra, todas as variáveis ​​que ocorrem nos corpos da regra devem ocorrer juntas em pelo menos um átomo, chamado de átomo de guarda
• Frontier-guarded Datalog , onde para cada regra, todas as variáveis ​​que são compartilhadas entre o corpo da regra e o cabeçalho da regra (chamadas de variáveis ​​de fronteira ) devem ocorrer juntas em um átomo de guarda

Outra restrição diz respeito ao uso de recursão: o Datalog não recursivo é definido por não permitir a recursão na definição de programas de Datalog. Este fragmento de Datalog é tão expressivo quanto uniões de consultas conjuntivas , mas escrever consultas como Datalog não recursivo pode ser mais conciso.

Expressividade

O problema de limitação para Datalog pergunta, dado um programa Datalog, se ele é limitado , ou seja, a profundidade máxima de recursão alcançada ao avaliar o programa em um banco de dados de entrada pode ser limitada por alguma constante. Em outras palavras, esta pergunta pergunta se o programa Datalog pode ser reescrito como um programa Datalog não recursivo. Resolver o problema de limitação em programas de Datalog arbitrários é indecidível , mas pode ser decidido restringindo-se a alguns fragmentos de Datalog.

Exemplo

Essas duas linhas definem dois fatos , ou seja, coisas que sempre valem:

parent(xerces, brooke).
parent(brooke, damocles).

Isso é o que eles querem dizer: xerces é pai de Brooke e Brooke é pai de Dâmocles . Os nomes são escritos em minúsculas porque strings que começam com uma letra maiúscula representam variáveis.

Essas duas linhas definem regras , que definem como novos fatos podem ser inferidos de fatos conhecidos.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

significado:

• X é um ancestral de Y se X for um pai de Y.
• X é um ancestral de Y se X é um pai de algum Z e Z é um ancestral de Y.

Esta linha é uma consulta:

?- ancestor(xerces, X).

Ele pergunta o seguinte: Quem são todos os X dos quais xerces é ancestral? Ele retornaria brooke e damocles quando colocado contra um sistema de registro de dados contendo os fatos e regras descritos acima.

Mais sobre as regras: uma regra tem um : - símbolo no meio: a parte à esquerda deste símbolo é a cabeça da regra, a parte à direita é o corpo . Uma regra é lida assim: <head> é conhecido como verdadeiro se for conhecido que <body> é verdadeiro . Letras maiúsculas em regras representam variáveis: no exemplo, não sabemos que X ou Y são, mas alguns X é o antepassado de algum Y se que X é o pai de que Y . A ordem das cláusulas é irrelevante no Datalog, ao contrário do Prolog, que depende da ordem das cláusulas para calcular o resultado da chamada de consulta.

Datalog distingue entre símbolos de predicados extensionais (definidos por fatos) e símbolos de predicados intensionais (definidos por regras). No exemplo acima, ancestoré um símbolo predicado intensional e parenté extensional. Predicados também podem ser definidos por fatos e regras e, portanto, nem ser puramente extensional nem intensional, mas qualquer programa Datalog pode ser reescrito em um programa equivalente sem esses símbolos de predicado com funções duplicadas.

Sintaxe

Um programa Datalog consiste em uma lista de fatos e regras ( cláusulas de Horn ). Se constante e variável são dois conjuntos contáveis de constantes e variáveis ​​respectivamente e a relação é um conjunto contável de símbolos de predicados , então a seguinte gramática expressa a estrutura de um programa Datalog:

<program> ::= <fact> <program> | <rule> <program> | ɛ
<fact> ::=  <relation> "(" <constant-list> ")." 
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list>
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list>
<constant-list> ::= <constant> | <constant> "," <constant-list>

Os átomos também são chamados de literais na literatura.

Semântica

Existem três abordagens amplamente utilizadas para a semântica de programas Datalog: modelo teórico , ponto fixo e prova teórica .

Teoria do Modelo

Um fato ou regra é denominado fundamento se todos os seus subtermos forem constantes. Uma regra básica R ₁ é uma instância básica de outra regra R ₂ se R ₁ for o resultado de uma substituição de constantes para todas as variáveis ​​em R ₂ .

A base Herbrand (consulte Herbrand Universe ) de um programa Datalog é o conjunto de todos os átomos no solo que podem ser feitos com as constantes que aparecem no programa. Uma interpretação (também conhecida como instância de banco de dados ) é um subconjunto da base Herbrand. Um átomo de chão é verdade em uma interpretação que se é um elemento de I . A regra é verdadeiro em uma interpretação I se para cada instância do solo dessa regra, se todas as cláusulas do corpo são verdadeiras em I , então a cabeça da regra também é verdade no que eu .

Um modelo de um programa de registro de dados P é uma interpretação I de P que contém todos os fatos no solo de P , e faz com que todas as regras de P verdadeiros em I . A semântica teórica de modelo afirma que o significado de um programa Datalog é seu modelo mínimo (equivalentemente, a interseção de todos os seus modelos).

Semântica de ponto fixo

Seja I o conjunto de interpretações de um programa Datalog P (ou seja, I = P ( H ) onde H é a base de Herbrand de P e P é o operador do conjunto de potência . Defina um mapa de I a I da seguinte forma: Para cada instância de solo de cada regra em P , se cada cláusula no corpo estiver na interpretação de entrada, adicione o cabeçalho da instância de base à interpretação de saída. Então, o ponto fixo deste mapa é o modelo mínimo do programa. A semântica do ponto fixo sugere um algoritmo para calcular o modelo mínimo: Comece com o conjunto de fatos básicos no programa e, em seguida, adicione repetidamente as consequências das regras até que um ponto fixo seja alcançado.

Avaliação

Existem muitas maneiras diferentes de avaliar um programa Datalog, com diferentes características de desempenho.

Estratégias de avaliação de baixo para cima

As estratégias de avaliação ascendente começam com os fatos no programa e aplicam as regras repetidamente até que algum objetivo ou consulta seja estabelecido, ou até que o modelo mínimo completo do programa seja produzido.

Avaliação ingênua

A avaliação ingênua reflete a semântica do ponto de fixação para programas Datalog. A avaliação ingênua usa um conjunto de "fatos conhecidos", que é inicializado com os fatos do programa. Ele prossegue enumerando repetidamente todas as instâncias básicas de cada regra do programa. Se cada átomo no corpo da instância fundamental estiver no conjunto de fatos conhecidos, o átomo principal será adicionado ao conjunto de fatos conhecidos. Este processo é repetido até que um ponto fixo seja alcançado, e nenhum outro fato possa ser deduzido. A avaliação ingênua produz todo o modelo mínimo do programa.

Sistemas implementando Datalog

Aqui está uma pequena lista de sistemas que são baseados no Datalog ou fornecem um intérprete do Datalog:

Software livre / código aberto

Software não-livre

• Datomic é um banco de dados distribuído projetado para permitir aplicativos escaláveis, flexíveis e inteligentes, rodando em novas arquiteturas de nuvem. Ele usa Datalog como linguagem de consulta.
• FoundationDB fornece uma ligação de banco de dados gratuita para pyDatalog, com um tutorial sobre seu uso.
• Leapsight Semantic Dataspace (LSD) é um banco de dados dedutivo distribuído que oferece alta disponibilidade, tolerância a falhas, simplicidade operacional e escalabilidade. LSD usa Leaplog (uma implementação Datalog) para questionar e raciocinar e foi criado pela Leapsight.
• LogicBlox , uma implementação comercial do Datalog usado para planejamento de varejo baseado na web e aplicativos de seguro.
• Profium Sense é um banco de dados gráfico compatível com RDF nativo escrito em Java. Ele fornece suporte de avaliação de registro de dados de regras definidas pelo usuário.
• .QL , uma variante comercial orientada a objetos do Datalog criado por Semmle para analisar o código-fonte para detectar vulnerabilidades de segurança.
• SecPAL uma linguagem de política de segurança desenvolvida pela Microsoft Research .
• Stardog é um banco de dados gráfico , implementado em Java . Ele fornece suporte para RDF e todos os perfis OWL 2, fornecendo amplos recursos de raciocínio, incluindo avaliação de registro de dados.
• StrixDB: um armazenamento gráfico RDF comercial, SPARQL compatível com Lua API e capacidades de inferência Datalog. Pode ser usado como módulo httpd ( Apache HTTP Server ) ou autônomo (embora as versões beta estejam sob a Licença Artística Perl 2.0).

Veja também

• Programação do conjunto de respostas
• Consulta conjuntiva
• DLV
• Flix
• SWRL
• Dependência geradora de tupla (TGD), uma linguagem para restrições de integridade em bancos de dados relacionais com uma sintaxe semelhante ao Datalog

Referências

Bibliografia

Leitura adicional

• Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007), Teoria dos modelos finitos e suas aplicações , Textos em Ciência da Computação Teórica. An EATCS Series, Berlin: Springer-Verlag , ISBN 978-3-540-00428-8, Zbl  1133.03001