Banco de Dados de Restrições,
Multimídia e GIS
Jairo Coutinho (jco)
CIn-UFPE
Programação por restrições:
definição e origens
Paradigma criado para problemas de busca difícil
 incorpora técnicas de matemática, inteligência artificial e
pesquisa operacional
 permite rápido desenvolvimento de programas, economia
de manutenção e eficiência
 pioneiro: Sketchpad system (1963, Sutherland),
linguagem por restrições para interações gráficas
 modelagem declarativa e garantia de satisfação eficiente

• Algoritmo = Lógica + Controle
• Restrições para programação multidirecional
• Programação em Lógica por restrição
Programação por restrições:
definição e origens

Problemas de satisfação de restrições (CSP)
• investigados em busca e IA desde muito tempo
• jogos (ex, n-rainhas) e problemas benchmark (ex, coloração de
mapa)
• resolução de tais problemas recentemente incorporadas a
linguagens de programação

Buscas inteligentes e flexíveis
• permitir que o usuário final possa controlar a busca
• combinando técnicas genéricas de busca cega
• com heurísticas para problemas específicos
Programação por restrições:
exemplo, coloração de mapa
Simulação passo a passo...
A= green
B = green (falha c/ A)
B=red
C=green (falha c/ A)
C= red
D=green
E= green (falha c/ A)
E= red (falha c/ B)
E= blue
F=green (falha c/ D)
F=red (falha c/ C)
F = blue (falha c/ E)
F backtracking
E backtracking
D=red
E=green (falha c/ A)
E= red (falha c/ B)
E= blue
F=green
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={green,red,blue}
restrições:
A  B; A  C; A  E; B  E; B
 F; C  E; C  F; D  F; E 
F
A
B
C
E
F
D
Programação por restrições:
aplicações práticas
alocação de recursos, agendamento
 planejamento financeiro, manutenção, localização,
gerenciamento de investimento.
 projeto e implementação de interface gráfica (ex,
Object Technology International).
 escalonamento baseado em restrições, com aplicação na
indústria pesada (ex, NASA, forças armadas)
 projeto e integração de circuitos digitais, e controle
tempo real.
 banco de dados e comércio eletrônico

Programação por restrições:
paradigmas, linguagens e sistemas

Paradigmas:
•
•
•
•
Imperativo x Restrições
Funcional
Lógico
OO
3 paradigmas básicos: imperativo, funcional, lógico
 OO e Restrições são meta-paradigmas que podem ser
implementados como camada acima de cada dos básicos
 Constraint Logic Programming (CLP):

• CLP(R), Prolog III, ECLiPSe, LIFE

Constraint Functional Programming:
• Oz

Constraint Imperative Programming:
• 2LP(C++), CHIP(C++)
Programação por restrições:
domínios e operadores

Domínios Finitos (FD)
• Domínios: , , strings, f(a, ...,b) com a,... b constantes simbólicas
• Operadores: +, -, *. /, <, >, <=, => etc..

Conjuntos
• Domínios: (), (), ..., ({f(a, ...,b) / a, ..., b  , }
• Operadores: inter, union, set-diff, etc

Intervalos
• Domínios: [ ] Implementa variáveis que variam sobre Inteiros e
Reais. Baseados resolvedores aritméticos.

Reais (RIA - Real Number Interval Arithmetic)
• Capaz de resolver problemas sobre os reais.
• Funções Reais já implementados
Programação em lógica com restrições (CLP)

clausulas de Horn proposicionais:

• C  P1  ...  PN


• estender equações entre termos
da PL
• com inequações e outras
restrições
em lógica de predicados,
necessidade de tratar das
variáveis
• p(a)  q(b,Z), r(Z)
•  p(X)
Unificação: dois termos podem
ser unificados se há valores na
consulta que façam os termos
iguais.
• P(X)  X = a, Y = b, q(Y,Z), r(Z)
Idéia da CLP:

ex, P(X)  X > 1, Y = b, q(Y,Z), r(Z)
Programação em lógica com restrições
CLP admite somente clausulas de Horn
 Programas CLP podem ser explicitamente escritos,
exceto que no lugar de equações existem restrições mais

gerais
CLP(X) com sua semântica define domínio de restrições
 Resolvedor é necessário para garantir a corretude e
completude para o algoritmo CLP(X)

Exemplo de CLP:
dieta em ECLIPSE

Programa
•
•
•
•
•
•
•
•
•
•
•
dieta(A,M,D) :- I>0, J>0, K>0, I+J+K
 10, entrada(A,I), principal(M,J),
sobremesa(D,K).
principal(M,I) :- carne(M,I).
principal(M,I) :- peixe(M,I).
entrada(rabanete,1).
entrada(massa,6).
carne(filé,5)
carne(porco,7)
peixe(solha,2)
peixe(atum,4)
sobremesa(fruta,2)
sobremesa(sorvete,6)

Resolução
•
•
•
•
•
•
@dieta(X,Y,Z)
X=A, Y=M, Z=D , I+J+K  10 ,I>0,
J>0, K>0 @ entrada(A,I),
principal(M,J), sobremesa(D,K)
X=rabanete, Y=M, Z=D , 1+J+K  10
, J>0, K>0 @ principal(M,J),
sobremesa(D,K)
X=rabanete, Y=M, Z=D , 1+J+K  10
, J>0, K>0 @ carne(M,J),
sobremesa(D,K)
X=rabanete, Y=filé, Z=D, 1+5+K  10
K>0 @ sobremesa(D,K)
X=rabanete, Y=filé, Z=fruta@
BD de restrições: motivação e agenda
Programação por restrição






Alta declaratividade com equações e
inequações entre variáveis lógicas
Dedução em lógica da 1a ordem
Completude computacional
Resolução de restrições eficiente
em domínios predefinidos
Codificação direta e bem
fundamentada das restrições de
integridade
Fornece modelos de dados relacional
e dedutivo como casos particulares
Banco de dados









Persistência
Otimização de acesso a memória
segundaria
Acesso concorrente
Recuperação
Linguagem de manipulação
Visões e dados derivados
Restrições de integridades
Manipulação dinâmica de esquema
Utilitários administrativos
BD de restições
Tupla generalizada: visão dos BD relacionais
no paradigma de programação por restrições
Idéia de BD de restrições: ver uma tupla como conjunto
de restrições sobre um dado domínio de restrições
 Tupla generalizada = tupla anotada com restrições entre
valores dos seus elementos: pj(X1, ... , Xk) | C
 Ex, tupla pessoa simples:

• Em relacional: (‘Bruce’,’Willis’,’GroupLeader’,01/05/90)
• Como restrições: {(FN,LN,Pos,Date)| FN=‘Bruce’  LN=‘Willis’ 
Pos=‘GroupLeader’  Date=01/05/90}
• Generalizada com inequação: {(FN,LN,Pos,Date)| FN=‘Bruce’ 
LN=‘Willis’  Pos=‘GroupLeader’ 
01/01/95  Date  Date  01/05/90}

Numero finito de tuplas generalizadas podem
representar infinidade de tuplas relacionais
Agentes, armazém e
resolvedores de restrições

Armazém:
• aplica informação parcial sobre uma variável, expressa como uma
restrição da mesma
• um modelo que trate das restrições primitivas de um domínio
• aproximação da uma solução intermediária da consulta corrente

Resolvedor (computação global centralizada):
• verifica automaticamente a consistência de cada nova primitiva
passada com as existentes no armazém

Agentes (computação local distribuída):
•
•
•
•
•
daemons tratando de um conjunto dado variáveis
disparados por alteração da faixa de uma dessas no armazém
propagada efeito dessa alteração nas suas outras variáveis
manda novas faixas para a armazém e suspende-se
o estado corrente da computação distribuído entre armazém e
agentes
Exemplo de resolução de restrições por meio
de agentes, armazém e resolvedores
Quatro agentes trabalhando no problema:
• 3  X, X  1, X  Y, Y X
• A1 aplica 3  X, A2 aplica X  1, A3 aplica X  Y, A4 aplica Y X
A1
=3
A2
X=1
A3
A4
Y=3 Y=2
X=2 =2
Y=2 Y=3
X
Step
1
2
3
4
X

Arquiteturas de BD de restrições

Acoplamento fraco:
• idéia: armazenar restrições persistentemente num BD relacional
+ reaproveita serviços de BD como indexação e otimização de
acesso a memória secundária e de gerenciamento de transações
+ desenvolvimento rápido
- overhead de conversão de restrição para relação
- ineficiência e perda de significado

Acoplamento forte:
•
+
+
idéia: tornar restrições persistentes
sem perda de significado, nem overhead de conversão
reimplementação no novo paradigma de todos os serviços de BD
desenvolvimento custoso
conceitualmente bem fundamentada
 escalabilidade, extensibilidade, etc.
BD de restrições: sistemas implementados

ECLIPSE/MegaLog
• ECLiPSe: linguagem de programação em lógica por restrições
implementando CLP(R), CLP(FD), CLP(Intervalos), CLP(Conjuntos),
CLP(Estruturais)
• Megalog pode armazenar variáveis de restrição e suporta
indexação multidimensional
• Falta uma linguagem de consulta de restrições integrada,
indexação e otimização

DISCO
• implementadas: intervalos ordenados de inteiros e conjuntos
ordenados
• linguagem de consulta baseada na lógica e não-procedimental
• usuários pode representar entradas na base usando restrições
• incorpora vários métodos de otimização
BD de restrições sistemas implementados

C3
• modelo de dados e linguagem de consulta: LiriC
• baseada no paradigma de OO
• incorpora restrições para a descrição de informações espaçotemporal em BD de restrições
• trata cada objeto de restrição separadamente
• expressividade e eficiência
BD de restrições:
limitações do estado da arte
Técnicas de otimização ainda não madura para grande
massas de dados
 Abordagem de restrições puras ainda não fornecem
todas os serviços de BD (segurança, transações etc.)
 Pouca integração com sintaxe e formalismos de massa
 Paradigma de programação por restrições pouco
divulgado e ensinado
 Falta de um padrão
 Porém:

• conceitualmente muito elegante, expressivo, versátil e otimizável
e então promissor
• já usada para BD temporais, espaciais, multimídia e distribuídas
heterogêneas
BD multimídia: definição e questões

Novos tipos de dados:
• imagens, gráficos, texto, áudio, discurso, vídeo, mídia gerada

Dificuldades de tratar desses separadamente:
• não suportados como built-in por linguagens de programação de
propósito gerais ou por linguagens de consulta de BD

produção, manipulação e apresentação requer dispositivos e
ferramentas especiais
• tamanho (de MB a TB no mínimo)
• estrutura e semântica interna complexa


novas linguagens de consultas expressivas
consultas aproximativas (reconhecimento de padrão)
• dependência do tempo (ex, áudio)

Inter-relacionamento entre:
• informações representadas por diferentes mídias (ex, legenda de
uma imagem, imagem de texto escaneado)
• sincronização de dados em várias mídias temporais (ex,
animações, vídeo)
BD multimídia: definição e questões

Armazenamento de informações
•
•
•
•

referências externas
campos longos
uso de funções externas
sistemas extensíveis e orientados a objetos
Modelagem dos dados multimídia
• diferentes técnicas de compressão (áudio e vídeo)

Recuperação de informação
• trechos específicos, composição de novas mídias
• metaconhecimento

Arquitetura
• protocolo de transporte
BD espaciais e GIS: definição e questões
Armazenamento compacto de grande massas de dados
espaciais (representações baseadas em pontos não viáveis
para muitas aplicações)
 Raciocínio geométrico sofisticado e eficiente

• ex, interseção, opacidade, navegação, alocação de espaço., etc.
Ontologia espacial
 Indexação multidimensional dos objetos geométricos
 Linguagem de consulta especializada

BD espaciais e GIS: abordagens

Abordagens principais:
• BDOO: retângulos, polígonos e objetos espaciais mais complexos
são naturalmente representados
• BD de restrições
• representação conjunto de pontos e polígonos de modo natural.
• permite a avaliação de predicados consulta espacial como
interseção e distância.
• Otimização de técnicas de indexação multidimencional
BD espaço temporal: definição e questões

Ausência de uma padrão
• proliferação de diferentes:


modelos lógicos e físicos de dados
linguagens de consulta
• variedade das necessidades das aplicações dificulta padronização
• necessidade de interoperabilidade

BD de restrições
• muitos modelos espaciais, temporais e espaço temporais são
casos particulares do modelo abstrato das tuplas generalizadas
 Linguagens de restrições excelente candidata como língua franca
para interoperabilidade entre diferentes bancos espaciais,
temporais e espaço-temporal
Integração de dados e
interoperabilidade em BD distribuídos

BD de restrições generaliza:
•
•
•
•
BD relacionais
BD dedutivas
BD espaciais
BD temporais
Fornece serviços e capacidade de modelagem ortogonal
às fornecidas pelos BDOO
 BDOO de restrições excelente candidato para tornar-se
padrão universal de interoperabilidade entre aplicações
avançadas
 Porém, não sub-estima SQL:2999 ! :)

Exemplo interoperabilidade via restrições:
BD Temporal

Relação dos pesquisadores
Nom e

Com pany
F ro m
To
A n d e rs o n
A T& T
1980
1993
B ro w n
IB M
1985
1996
C la rk
Lotus
1990
1991
Representando como tupla generalizada
reseacher(name,comp,t) :- name=“Anderson”, comp = “AT&T”,
1980t, t 1993
reseacher(name,comp,t) :- name=“Brown”, comp = “IBM”,
1985t, t 1996
reseacher(name,comp,t) :- name=“Clark”, comp = “AT&T”,
1990t, t 1991
Exemplo interoperabilidade via restrições:
BD Espacial
11
10
9
8
7
6
5
4
3
2
1
Representação em tupla
generalizada
r1
l1
p2
object(p1,x,y) :- x=10, y=4
object(l1,x,y) :- 5x, x9, y = -x+15
p1
t1
object(l1,x,y) :- x=9, 3y, y6
1
2
3
4
5
6
7
8
9
10
11
12
ID
x
y
x'
y'
x ''
y ''
p1
10
4
10
4
10
4
l1
5
10
9
6
9
6
l1
9
6
9
3
9
3
t1
2
3
2
7
6
3
r1
1
2
1
11
11.5
11
r1
11.5
11
11.5
2
1
2
p2
3
5
3
8
4
9
p2
4
9
7
6
3
8
p2
3
5
7
6
3
8
object(t1,x,y) :- 2x, x6, 3y, y7,
y  -x+9
object(r1,x,y) :- 1x, x11.5, 2y11
object(p2,x,y) :- x3, y5, yx-1,
yx+5, y  -x+13
Exemplo interoperabilidade via restrições:
BD Espaço-Temporal
Representação em tupla
generalizada
1994-1996
11
10
9
8
7
6
5
4
3
2
1
r1
1995-1996
l1
p2
1991-1996
t1
p1
1975-1990
1
2
3
4
5
1980-1986
6
7
8
9
10
11
12
ID
x
y
x'
y'
x ''
y ''
F ro m
To
p1
10
4
10
4
10
4
1980
1986
l1
5
10
9
6
9
6
1995
1996
l1
9
6
9
3
9
3
1995
1996
t1
2
3
2
7
6
3
1975
1990
r1
1
2
1
11
11.5
11
1994
1996
r1
1 1 .5
11
1 1 .5
2
1
2
1994
1996
p2
3
5
3
8
4
9
1991
1996
p2
4
9
7
6
3
8
1991
1996
p2
3
5
7
6
3
8
1991
1996
object(p1,x,y) :- x=10, y=4,
1980t, t1996
object(l1,x,y) :- 5x, x9, y = -x+15,
1995t, t1996
object(l1,x,y) :- x=9, 3y, y6,
1995t, t1996
object(t1,x,y) :- 2x, x6, 3y, y7,
y  -x+9, 1975t, t1990
object(r1,x,y) :- 1x, x11.5, 2y11,
1994t, t1996
object(p2,x,y) :- x3, y5, yx-1,
yx+5, y  -x+13,
1991t, t1996
BD de restrições: conclusão
Estende BD relacionais e dedutivas
 Permite implementar elegantemente BD espaciais,
temporais, multimídia e interoperabilidade em BD
distribuídas heterogêneas
 Resolve impedance-mismatch (já que programação por
restrições é computacionalmente completa)
 Reaproveita de técnicas de IA (busca heurística),
pesquisa operacional e matemática para conseguir
eficiência
 Vasto leque de aplicações práticas e industriais
 Apenas na fase inicial em termos de:

• Implementação de SGBD
• Divulgação e ensino do formalismo
• Padronização