Capítulo 5: Outras linguagens
 Query-by-Example (QBE)
 Datalog
5.2.1
Datalog
 Estrutura de Base
 Sintaxe de regras Datalog
 Semântica de programas não recursivos
 Operações relacionais em Datalog
 Recursão em Datalog (programas definidos e estratificados)
 Expressividade de Datalog
 Recursão sobre negação (modelo bem-fundado)
 Answer-set programming
5.2.2
Estrutura de Base
 Programas em lógica sem predicados de controlo (e.g. !, var),





sem “side-effects” (e.g. write, read) nem uso de símbolos
funcionais.
Permite recursão.
Um programa Datalog é um conjunto de regras, que definem
“views”.
Exemplo: definir relação (view) v1 com todos os números de
conta e respectivos saldos, para as contas de Perryridge com
saldo superior a 700.
v1(A, B) :– account(A, “Perryridge”, B), B > 700.
Qual o saldo da conta “A-217” na view v1?
?- v1(“A-217”, B).
Quais as contas com saldo superior a 800?
?- account(A,_,B), B > 800
5.2.3
Exemplos de perguntas
 Cada regra define um conjunto de tuplos que pertencem à view
 E.g. v1(A, B) :– account(A, “Perryridge”, B), B > 700
lê-se como
para todo A, B
se (A, “Perryridge”, B)  account e B > 700
então (A, B)  v1
 O conjunto de tuplos duma view é definido como a união dos
conjuntos de tuplos de cada uma das suas regras.
 Exemplo:
interest-rate(N, 5) :– account(N,A, B), B < 10000
interest-rate(N, 6) :– account(N,A, B), B >= 10000
5.2.4
Negação em Datalog
 Definir a view c contendo os nomes de todos os clientes que
têm pelo menos um depósito mas não têm empréstimos:
c(N) :– depositor(N, A), not is-borrower(N).
is-borrower(N) :–borrower (N,L).
 NOTA: usando directamente not borrower (N, L) na 1ª regra
dava resultado diferente: clientes N que têm pelo menos um
depósito e existe algum empréstimo L que não é de N
 Para evitar confusão (e problemas de implementação), é usual
exigir-se que as variáveis em literais negados apareçam na cabeça
da regra ou em algum literal positivo do corpo da regra
 Problema de floundering. Considere:
p(X) :- not q(X).
q(a).
e as perguntas ?- p(X). e ?- p(b).
5.2.5
Regras por camadas (views sobre views)
 Quais os juros de cada uma das contas de Perryridge
interest(A, l) :– perryridge-account(A,B),
interest-rate(A,R), l is B * R/100.
perryridge-account(A,B) :–account(A, “Perryridge”, B).
interest-rate(N,0) :–account(N, A, B), B < 2000.
interest-rate(N,5) :–account(N, A, B), B >= 2000.
 Camadas das várias views:
5.2.6
Recursão em Datalog
 Considere a relação:
precedencia(X, Y)
contendo pares X, Y de cadeiras onde X dá precedência directa
para Y.
 Cada cadeira pode dar precedência para outras, directa ou
indirectamente
 Uma cadeira X dá precedência indirectamente a Y, se dá
precedência directa a uma cadeira Z, que por sua vez dá
precedência para Y
 Encontrar todas as cadeiras que dão precedência (directa ou
indirecta) a Bases de Dados 1. Podemos escrever o seguinte
programa Datalog recursivo:
precBD1(X) :- precedencia(X, ‘BD1’).
precBD1(X) :- precedencia(X, Y), precBD1(Y).
5.2.7
Recursão em Datalog (Cont.)
 De forma mais geral: criar view precs com todos os pares (X,
Y) onde X dá precedência directa ou indirecta para Y:
precs(X, Y) :– precedencia(X, Y).
precs(X, Z) :– precs(X,Y), precs(Y,Z).
 Quais as cadeiras que dão precedência a BD1
?- precs(X, ‘BD1’).
 E qual o significado preciso disto?
 É mesmo igual a Prolog?
 Que views é que são definidas assim?
 A sintaxe é parecida com a do Prolog. Mas qual é, exactamente?
5.2.8
Exemplo de pergunta complexa
 Questão 28 da 1ª ficha de problema SQL:
 Quais os nomes dos alunos que não seguiram pelo menos uma das
precedências (directas) aconselhadas, e em que cadeiras não as seguiram?
nao_fez(NAluno,CCurso,CCadeira) :curso_cadeira(CCurso,CCadeira,_Semestre),
not(esta_inscrito(NAluno,CCurso,CCadeira) ).
esta_inscrito(NA,CCr,CCd) :- inscricoes(NA,CCr,CCd,_DIn,_DAv,_Nt)
query(Nome,Cadeira) :alunos(Num,Nome,_L,_Dt,_Sx,_Cr),
inscricoes(Num,CCurso,CCadeira,_DIn,_DAv,Nt),
precedencias(CCurso,CCadeira,CadP), nao_fez(Num,CCurso,CadP),
cadeiras(CCadeira,Cadeira,_C,_D).
query(Nome,Cadeira) :alunos(Num,Nome,_L,_Dt,_Sx,_Cr),
inscricoes(Num,CCurso,CCadeira,DIn,_DAv,_Nt),
precedencias(CCurso,CCadeira,CadP),
inscricoes(Num,CCurso,CadP,_DIn,DAv,_Nt), DAv > Din,
cadeiras(CCadeira,Cadeira,_C,_D).
 E se fossem precedências indirectas, bastava substituir precedencias
por precs.
5.2.9
Sintaxe de regras Datalog
 Um literal positivo (ou átomo) tem a forma
p(t1, t2 ..., tn)
 p é o nome da relação, com n atributos
 cada ti é uma constante ou uma variável
 Um literal negativo (ou por default) tem a forma
not p(t1, t2 ..., tn)
 Operadores de comparação são entendidos como predicados
 E.g. X > Y é entendido como o átomo >(X,Y)
 Conceptualmente “>” define uma relação (infinita) contendo todos
os pares (X,Y) onde X é maior que Y.
 Operações aritméticas são entendidas como predicados
 E.g. A is B + C é entendido como +(B, C, A), onde a relação
(infinita) “+” tem todos os triplos em que o 3º valor é igual à soma
dos primeiros 2.
5.2.10
Sintaxe de regras Datalog (Cont.)
 Regras são da forma:
p(t1, t2, ..., tn) :– L1, L2, ..., Lm.
 cada Li é um literal (positivo ou negativo)
 cabeça – átomo p(t1, t2, ..., tn)
 corpo – literais L1, L2, ..., Lm
 A uma regra com corpo vazio chama-se um facto:
p(v1, v2, ..., vn).
 afirma que o tuplo (v1, v2, ..., vn) pertence à relação p
 Um programa Datalog é um conjunto (finito) de regras
 Um programa diz-se definido, se nenhuma das suas regras
contém literais negativos (i.e. se not não aparece no programa).
5.2.11
Operações Relacionais em Datalog
 Projecção do atributo account-name de account:
query(A) :–account(A, N, B).
 Produto cartesiano das relações r1 e r2.
query(X1, X2, ..., Xn, Y1, Y2, ..., Ym) :–
r1(X1, X2, ..., Xn), r2(Y1, Y2, ..., Ym).
 União das relações r1 e r2.
query(X1, X2, ..., Xn) :– r1(X1, X2, ..., Xn).
query(X1, X2, ..., Xn) :– r2(X1, X2, ..., Xn).
 Selecção de tuplos de r1 que obedecem a condição cond.
query(X1, ..., Xn) :– r1(X1, ..., Xn), cond(X1,..., Xn).
 Diferença entre r1 e r2.
query(X1, X2, ..., Xn) :– r1(X1, X2, ..., Xn),
not r2(X1, X2, ..., Xn).
5.2.12
Semântica duma regra
 Uma instância duma regra é o resultado de substituir cada uma
das variáveis da regra por alguma constante.
 Eg. Sendo v1
v1(A,B) :– account (A,“Perryridge”, B), B > 700.
 Uma instância de v1 é:
v1(“A-217”, 750) :–account(“A-217”, “Perryridge”, 750),
750 > 700.
 O corpo duma instância duma regra R’ é satisfeito num conjunto
I de factos (interpretação, ou instância da base de dados) sse
1. Para cada átomo qi(vi,1, ..., vi,ni )  R’, l contem qi(vi,1, ..., vj,ni).
2. Para cada literal not qj(vj,1, ..., vj,ni)  R’, l não contem qj(vi,1, ..., vj,ni).
5.2.13
Semântica de Programas Definidos
 Seja I uma interpretação (conjunto de factos). Define-se, para
um programa definido P:
TP(I) = {p(t1, t2, ..., tn) : existe uma instância R’ duma regra R de P
com cabeça p(t1, t2, ..., tn) cujo corpo está satisfeito em I}
 A semântica (significado) de um programa definido P sobre uma
instância duma base de dados I é o resultado do menor pontofixo da sequência:
 I0 = I
(sendo P definido, esta sequência é não decrescente)
 In+1 = TP(In)
 O resultado duma view v com k argumentos, num programa P e
base de dados I é o conjunto de todos os factos v(t1, t2, ..., tk)
pertencentes ao ponto-fixo.
 Claro que não é assim que está implementado!!!
5.2.14
Datalog vs Prolog (em programas definidos)
 Datalog não é muito útil para implementar algoritmos:
 não é possível controlar a execução do programa.
 não se podem usar estruturas de dados (infinitas) recursivas.
 Em Prolog não nos podemos verdadeiramente abstrair do
modelo de execução. Exemplo:
p(X) :- p(X).
?- p(R).
p(a).
(em Prolog – loop; em Datalog {p(a)})
 Prolog: apropriado para implementar algoritmos (na linha de
outras linguagens de programação, e.g. C)
 Datalog: apropriado para descrever relações e perguntas a
bases de dados (na linha de outras linguagens de perguntas,
e.g. SQL)
5.2.15
Restrições nas variáveis
 É possível escrever regras com um nº infinito de soluções.
maior(X, Y) :– X > Y
not-in-loan(B, L) :– not loan(B, L)
 Em Prolog isto não era problema (tuple-at-a-time). Mas agora é,
se quisermos saber o resultado duma pergunta (set-at-a-time)
 Para evitar este problema, em Datalog:
 Toda a variável que apareça na cabeça duma regra tem que
aparecer também no corpo dessa regra, e num átomo que não seja
expressão aritmética.
 Esta condição pode ser tornada mais fraca para permitir regras
como:
p(A) :- q(B), A is B + 1
 Toda a variável que apareça num literal negativo no corpo duma
regra tem que aparecer também num átomo do corpo dessa mesma
regra.
5.2.16
Monotonicidade
 Uma view V é monotónica se para qualquer par de conjunto de
factos I1 e I2 tais que l1  I2, se tem Ev(I1)  Ev(I2), onde Ev é a
expressão que define V.
 Um programa Datalog P é monotónico sse:
l1  I2 implica TP(I1)  TP(I2),
 Views de álgebra relacional que usem os operadores  ,
 e  (bem como outros – e.g. joins – definidos à custa destes)
são monotónicas.
 Views de álgebra relacional com – podem não ser monotónicas.
 Da mesma forma, programas Datalog definidos são monotónicos,
mas programas Datalog com negação podem não o ser.
5.2.17
Não-monotonicidade
 A semântica à custa do operador TP só funciona em programas
monotónicos.
 Algumas conclusões numa iteração, podem deixar de o ser numa
iteração posterior – possibilidade de não convergência para um
ponto fixo. E.g.
other_accounts(Num) :- not perryridge_account(Num).
perryridge_account(N) :–account(Num, “Perryridge”, _B).
Na 1ª iteração uma conta doutra sucursal aparece na view
other_accounts mas desaparece na 2ª iteração.
 Pode-se estender a iteração do TP para lidar com negação em
programas estratificados (i.e. sem recursão sobre negação)
5.2.18
Programas Estratificados
 Um programa Datalog é estratificado se cada um dos seus
predicados pode ser colocado num estrato de tal forma que:
1. Para cada literal positivo q no corpo duma regra com cabeça p
p(..) :- …., q(..), …
o estrato de p é maior ou igual do que o estrato de q
2. Dada uma regra com um literal negativo no corpo
p(..) :- …, not q(..), …
o estrato de p é estritamente maior que o estrato de q
 Por outras palavras, recursão e negação não se misturam
5.2.19
Perfect Model
 A semântica dum programa estratificado é definida estrato a
estrato, começando pelo menor deles (que não tem negação).
 Em cada estrato usa-se a iteração TP
 Calculado o resultado da iteração de TP num estrato n, usa-se
esse resultado para nos “livrar-mos” da negação no estrato n+1:
 Seja not q um literal negativo que aparece no corpo duma instância
duma regra do estrato n+1:
 Se q  TP dum estrato anterior → apague-se a instância
 Caso contrário → apague-se o not q do corpo dessa instância
 Como os estratos inferiores são calculados antes, os seus factos
não mudam. Logo, os resultados de cada estrato são
monotónicos, se fixados os resultados dos estratos anteriores.
5.2.20
Datalog vs SQL
 Tudo o que se consegue exprimir em SQL (sem agregação) consegue
exprimir-se em Datalog (e nem é preciso recursão).
 É fácil introduzir agregação em Datalog. Mas não há uma forma standard,
aceite por todos.
 Também é possível definir formas de actualização de relações em Datalog
(mas também não há forma standard).
 Há muitas view úteis, que exigem recursão, que não se conseguem
exprimir em SQL e se conseguem em Datalog.
 Com SQL é mais vezes necessário passar parte da interrogação para uma
linguagem (embedded) imperativa.
 O SQL é (de longe) mais conhecido e usado.
 Datalog exige conhecimentos de programação em lógica, que nem todos
têm.
 É usual dizer-se que as implementações de SQL são bem mais eficientes
e robustas. Mas isto é cada vez menos verdade:
 Há hoje implementações eficientes e robustas de Datalog (e.g. XSB-Prolog)
 Essas implementações permitem ligações via ODBC, permitindo até ter partes
em SQL
 Usa-se SQL nas partes em que este serve
 Usa-se Datalog nas partes em que o SQL não chega (ou é pior)
5.2.21
O poder expressivo da recursão
 Views recursivas permitem especificar perguntas, tal como fechos
transitivos, que não podem ser especificadas sem recursão ou
iteração.
 Intuição: Sem recursão só se podem fazer um número fixo de junções
entre relações (e.g. de precedencias com precedencias)
 Isto só nos dá as precedências com indirecção até esse número
fixo.
 Dado um programa é sempre possível construir uma base de dados
em que o nível de indirecção é maior, e na qual o programa sem
recursão não funciona.
 A complexidade de cálculo de programas sem recursão é constante
 A complexidade de cálculo do modelo perfeito é linear no número
de instâncias de regras
 Se um problema é de complexidade linear, é impossível descrevê-lo
numa linguagem com complexidade inferior a linear (i.e. constante)
5.2.22
Para além de programas estratificados
 E se a complexidade do problema for maior que linear? Aí os
Programas Estratificados já não são úteis:
 Problemas NP-completo: E.g.
 caminhos Hamiltonianos em grafos: que passam por todos os nós,
sem nunca repetir um nó;
 caminhos de custo mínimo: problema de caixeiro viajante
 Nestes problemas seria necessário um nº exponencial de regras para
os exprimir em programas estratificados (a não ser que P = NP!!).
 Há perguntas que não se exprimem com programas estratificados.
 Considere a relação movimento(P1,P2) que guarda movimentos
possíveis dum jogo.
 Um posição é ganhante se é possível fazer um movimento para uma
outra posição que é perdedora.
 Uma posição é perdedora se não se pode concluir que é ganhante.
5.2.23
Para além de estratificados (Cont.)
 Um posição é ganhante se é possível fazer um movimento para
uma outra posição que é perdedora.
 Uma posição é perdedora se não se pode concluir que é
ganhante.
ganhante(X) :- movimento(X,Y), perdedora(Y)
perdedora(X) :- not ganhante(X)
b
c
e
f
d
a
 a e c são posições ganhantes. d e b são posições perdedoras.
e e f não são uma coisa nem outra (empates).
5.2.24
Modelo bem fundado
 Ideias de base:
 Uma interpretação a 3 –valores tem factos verdadeiros, factos
falsos e factos desconhecidos.
 Parte-se da instância da base de dados:
 tudo o que lá está é verdadeiro
 tudo o resto é desconhecido
 (nada é falso à partida)
 Dada um interpretação a 3 valores, calcular-se novos factos que
são garantidamente falsos e, com base nestes, novos factos que
são garantidamente verdadeiros.
 Itera-se o processo até que não hajam mais factos garantidamente
falsos, nem mais factos garantidamente verdadeiros.
 No final podem haver factos se mantêm desconhecidos (não são
verdadeiros nem falsos).
5.2.25
Modelo bem-fundado (Cont.)
 Dado uma interpretação a 3-valores I, calculam-se os factos que
garantidamente falsos com base em I da seguinte forma:
 Apagam-se todas as instâncias de regras contendo not q se q é
verdadeiro em I
 Apagam os restantes literais negativos (i.e. literais not q, onde q é falso
ou desconhecido)
 Calcula-se o menor ponto fixo de TP sobre o programa (definido)
resultante
 São garantidamente falso os factos que não estão lá.
 Calculados os garantidamente falso com base em I, calculam-se os
novos garantidamente verdadeiros da seguinte forma:
 Apagam-se todas as instâncias de regras contendo not q se q é não é
garantidamente falso em I (nem no que se acabou de calcular, já agora)
 Apagam os restantes literais negativos (i.e. literais not q, onde q é
garantidamente falso)
 Calcula-se o menor ponto fixo de TP sobre o programa (definido)
resultante
 São também garantidamente verdadeiros os factos que lá estão.
5.2.26
Bem fundado vs Perfect
 O modelo bem-fundado permite exprimir perguntas que
combinam negação com recursão.
 É mais expressivo que programas estratificados.
 A complexidade de cálculo do modelo bem-fundado é quadrática
no número de instâncias de regras.
 XSB-Prolog implementa o modelo bem-fundado
 Pode-se usar, ligando com programas em linguagens imperativas, e
com partes em SQL, via ODBC.
 É eficiente e robusto.
 Ganha-se bastante em expressividade.
 Mantém-se o problema de expressividade para o caso de
problemas NP-completo!!
5.2.27
Answer-Set Programming
 Semântica de Datalog com complexidade (e expressividade)
NP-completo.
 Define views não-deterministicas
 Existem implementações recentes, também com interface ODBC
(e via XSB Prolog): smodels e dlv
 Estas implementações são bastante robustas.
 São eficientes (mas tendo em conta a complexidade, nunca
podem ser muito eficientes para problemas grandes).
 Não faz muito sentido usar para exprimir problemas que não
sejam NP-completo.
 Mas para problemas NP-completo, faz todo o sentido!!!
5.2.28
Answer-sets
 Uma interpretação é um conjunto de factos verdadeiros
 Um facto é falso numa interpretação I, sse não pertence a I
 I é um answer-set sse é o menor ponto fixo de TP, sobre o
programa definido obtido da seguinte forma:
 Apagam-se de P todas as instâncias de regras que contêm not q,
para algum q  I
 Apagam-se os restantes literais negativos em corpos de instâncias
regras (i.e. literais not q onde q é falso em I)
 Um programa pode ter vários (ou nenhum) answer-sets
 Geração e teste: gera-se aleatoriamente um I; testa-se depois
para ver se é answer-set.
 Claro que não é assim que está implementado!!!
 Cada answer-set define uma hipótese para as várias views
5.2.29
Exemplo ASP
 Dadas as relação voo(De,Para) e cidade(Nome), definir view
vooCam com os voos que fazem parte dum caminho que passa
por todas as cidades, sem passar duas vezes por nenhuma delas
(este é um problema NP-Completo – caminhos Hamiltonianos):
vooCam(X,Y) :- voo(X,Y), not vooFora(X,Y).
vooFora(X,Y) :- voo(X,Y), not vooCam(X,Y).
passaPor(C) :- vooCam(C,_).
passaPor(C) :- vooCam(_,C).
repete(C) :- vooCam(C1,C), vooCam(C2,C), C1 \= C2.
saidaErrada(C) :- vooCam(C,C1), vooCam(C,C2), C1 \= C2.
problema(C) :- cidade(C), not passaPor(C), not problema(C).
problema(C) :- repete(C), not problema(C).
problema(C) :- saidaErrada(C), not problema(C).
 Podem haver vários answer-sets. Cada um deles contem na view
vooCam um conjunto de voos que satisfazem a pergunta (i.e. um
caminho Hamiltoniano do grafo de voos)
 Se não houverem caminhos Hamiltonianos, então não há answersets
5.2.30