29
Lógica e Bases de Dados Prof. Elaine Faria e Hiran Nonato Programação Lógica UFU - 2012

Lógica e Bases de Dados - facom.ufu.bralbertini/2sem2012/curso-prolog/slides/aula12.pdfBases de Dados Relacionais • Modelo relacional – os dados são definidos por meio de relações

  • Upload
    ngonhi

  • View
    220

  • Download
    0

Embed Size (px)

Citation preview

Lógica e Bases de Dados

Prof. Elaine Faria e Hiran NonatoProgramação Lógica

UFU ­ 2012

Bases de Dados Relacionais• "Base de dados" 

– Coleção de dados interrelacionados, armazenada de modo independente do programa  que  a  utiliza,  permitindo  a  recuperação,  inserção,  remoção  e modificação de forma controlada. 

– A quantidade de dados é tipicamente grande e o conteúdo muda ao longo do tempo

• Prolog  uma base de dados é definida como um conjunto de fatos• Prolog  possui  características  que  a  tornam  um  excelente  interface 

para lidar com bases de dados relacionais

Bases de Dados Relacionais

• Modelo relacional – os  dados  são  definidos  por  meio  de  relações  sobre 

domínios – os  fatos  individuais  são  representados  como  tuplas 

de valores sobre tais domínios– uma relação com um conjunto de tuplas é chamada 

de “tabela”– associação  entre  diferentes  tabelas  é  feita  através  da 

identidade explícita de valores de atributos

Bases de Dados Relacionais

• Exemplo– Relações

• pessoa/4, contendo nome, sexo, pai e mãe• carro/4, contendo placa, fabricante, proprietário e cor

• Essas relações podem originar tabelas

Bases de Dados Relacionais

• Base de dados Prolog para a tabela pessoapessoa(marcelo, m, luiz, gilda).pessoa(luiz, m, alfredo, lina).pessoa(gilda, f, miguel, ana).pessoa(lúcia, f, luiz, gilda).pessoa(paulo, m, miguel, ana).pessoa(lina, f, francisco, júlia).

Bases de Dados Relacionais

• Base de dados Prolog para a tabela carrocarro(abc­4590, vw, alfredo, azul).carro(xyz­1211, ford, lina, branco).carro(rtc­9004, fiat, luiz, vermelho).carro(llz­7533, gm, gilda, prata).

Bases de Dados Relacionais

• Uma  situação  de  exceção  ocorre  quando  é  necessário manipular informação incompleta no modelo relacional

•  O símbolo especial  "nil" é empregado para  representar a informação incompleta

– Ex: carro(ajk­6712, honda, nil, verde)• Proprietário inexistente

Bases de Dados Relacionais

• Chaves– Um ou mais atributos em cada relação que possui a propriedade 

de serem únicos na tabela– Identificam  os  objetos  acerca  dos  quais  armazena­se 

informações

Usualmente sublinha­se os atributos chaves. Exemplo:pessoa:

nome sexo pai mãe

Bases de Dados Relacionais• Chave simples: 

– representada por um único argumento– ocupando a primeira posição da relação.–  Ex: carro(ajk­6712, honda, jose, preta)

chave: ajk­6712

• Chave Composta– Representada como uma lista de argumentos– Ex: carro(gpr­6214, ford, maria, vermelho)                chave: [ajk­6712, ford]

Recuperação de Informações• Recuperar  informações  significa  combinar  e  apresentar  o  conteúdo 

da base de dados Em bases de dados convencionais 

– A  recuperação é  executada por um programa que atua sobre a base de dados 

• Em Prolog – A  recuperação  é  feita  através  da  definição  das  condições  de 

solução em lógica. – Ex:  Quem possui um fiat?

?­ carro(_, fiat, Proprietario, _).Proprietario = luiz

Recuperação de Informações

• Exemplos de recuperação– Quem fabrica os carros preferidos pelas mulheres?

pessoa(marcelo, m, luiz, gilda).pessoa(luiz, m, alfredo, lina).pessoa(gilda, f, miguel, ana).pessoa(lúcia, f, luiz, gilda).pessoa(paulo, m, miguel, ana).pessoa(lina, f, francisco, júlia).

carro(abc­4590,vw, alfredo, azul).carro(xyz­1211,ford, lina,branco).carro(rtc­9004,fiat, luiz,vermelho).carro(llz­7533,gm,gilda,prata).

?­ pessoa(N, f, _, _),     carro(_, Fabr, N, _).

Recuperação de Informações

pessoa(marcelo, m, luiz, gilda).pessoa(luiz, m, alfredo, lina).pessoa(gilda, f, miguel, ana).pessoa(lúcia, f, luiz, gilda).pessoa(paulo, m, miguel, ana).pessoa(lina, f, francisco, júlia).

carro(abc­4590,vw, alfredo, azul).carro(xyz­1211,ford, lina,branco).carro(rtc­9004,fiat, luiz,vermelho).carro(llz­7533,gm,gilda,prata).

?­ pessoa(N, f, _, _),     carro(_, Fabr, N, _).    N = lina, Fabr = ford;

Recuperação de Informações

pessoa(marcelo, m, luiz, gilda).pessoa(luiz, m, alfredo, lina).pessoa(gilda, f, miguel, ana).pessoa(lúcia, f, luiz, gilda).pessoa(paulo, m, miguel, ana).pessoa(lina, f, francisco, júlia).

carro(abc­4590,vw, alfredo, azul).carro(xyz­1211,ford, lina,branco).carro(rtc­9004,fiat, luiz,vermelho).carro(llz­7533,gm,gilda,prata).

?­ pessoa(N, f, _, _),     carro(_, Fabr, N, _).    N = lina, Fabr = ford;    N = gilda, Fabr = gm;

Recuperação de Informações

pessoa(marcelo, m, luiz, gilda).pessoa(luiz, m, alfredo, lina).pessoa(gilda, f, miguel, ana).pessoa(lúcia, f, luiz, gilda).pessoa(paulo, m, miguel, ana).pessoa(lina, f, francisco, júlia).

carro(abc­4590,vw, alfredo, azul).carro(xyz­1211,ford, lina,branco).carro(rtc­9004,fiat, luiz,vermelho).carro(llz­7533,gm,gilda,prata).

?­ pessoa(N, f, _, _),     carro(_, Fabr, N, _).    N = lina, Fabr = ford;    N = gilda, Fabr = gm;    false.

Recuperação de Informações

Recuperação Eficiente• Em grandes bases de dados, devemos ter cuidado:

– Quando há combinação de tuplas distribuídas em duas ou mais tabelas

• Sistemas Prolog devem possuir um “otimizador de consultas”

• Exemplo– Suponha que um crime tenha sido cometido e está sendo procurado um 

homem em um ford azul– A base de dados da polícia possui duas tabelas: uma com 3000 carros e 

outra com 10000 pessoas suspeitas– Uma pessoa pode possuir mais de um carro– Suponha que haja dez fords azuis e que metade das pessoas na base de 

dados sejam homens

Recuperação EficienteSoluções:

?­ carro(Placa, ford, X, azul), pessoa(X, m, _, _).

ou

?­ pessoa(X, m, _, _), carro(Placa, ford, X, azul).

Recuperação EficienteSoluções:

• No primeiro caso – 3000 tentativas de unificação na tabela de carros– Dessas, apenas 10 serão bem sucedidas (só há 10 fords azuis) – 10 acessos diretos à tabela de pessoas para verificar o sexo, num total de 

3010 unificações

• No segundo caso– 10000 tentativas de unificação na tabela de pessoas, das quais 5000 serão 

bem sucedidas – Para cada uma dessas unificações bem sucedidas, 3000 acessos deverão ser 

feitos à tabela de carros, uma vez que não se dispõe da chave, que é “placa”

Atualização da Base de Dados• O modelo relacional impõe a restrição de que certos campos devem ser 

campos chaves, cujo valor deve ser único em uma tabela

• Em  Prolog,  um  sistema  para  o  gerenciamento  de  bases  de  dados relacionais pode ser implementado de forma muito natural

• Operações básicas– remove(T)          % Remove a tupla T– insere(T)           % Insere a tupla T, se já não estiver lá– atualiza(VT, NT)           % Remove a velha e insere a nova tupla

Atualização da Base de Dados

• Exemplos?­ remove(carro(_, _, gilda, _)).

irá remover da base de dados todos os carros que pertencem a Gilda

?­ insere(carro(flt­5455, honda, gilda, cor­de­rosa)).irá introduzir o novo ­ e único ­ carro de Gilda na base de dados.

Atualização da Base de Dadosremove(X) :­             

  removeAux(X), fail.    remove(X).

removeAux(X) :­  retract(X).

removeAux(X).

insere(X) :­  remove(X), assert(X).

insere(X) :­  assert(X).

Formas Normais Relacionais

• Um  dos  princípios  da  boa  modelagem  é  evitar redundâncias

• Em  bases  de  dados  relacionais  esse  princípio  é modelado através das formas normais– 1FN, 2FN, 3FN, ...

Formas Normais Relacionais

• Exemplo de uso da 1FN– Evitar repetir grupos

empregador empregado1, empregado2, ..., empregadon

– Não usar a representaçãoempregados(joão, [josé, júlia, jorge, josefina, jane]).

– Usar a representaçãoempr(josé, joão).empr(júlia, joão).empr(jorge, joão).empr(josefina, joão).empr(jane, joão).

Formas Normais Relacionais

• Exemplo de uso da 1FN – cont.– o benefício acontece quando um novo empregado (por exemplo, 

jonas) é contratado 

?­ insere(empr(jonas, joão)).

– O programador não necessita(1) Selecionar a lista de empregados de joão(2) Adicionar Jonas(3) Produzir uma nova lista(4) Apagar a tupla corrente, com a velha lista(5) Produzir uma nova tupla, com a nova lista

Formas Normais Relacionais

• Exemplo de uso da 2FN– Identificar/remover atributos não dependentes da chave primária– Regra aplicada apenas à chaves compostas

empregado nomeEmpregado     (tabela empregado)empregado projeto nomeProjeto horas   (tabela alocação)

– nomeProjeto não depende funcionalmente da chave:[empregado, projeto]

Formas Normais Relacionais

• Exemplo de uso da 2FN ­ cont– Identificar/remover atributos não dependentes da chave primária (nova 

tabela criada, ok)

Solução:empregado nomeEmpregado     (tabela empregado)

empregado projeto horas    (tabela alocação)projeto nomeProjeto (tabela projeto) 

– Dessa  forma,  caso  o  atributo  nomeProjeto  mude,  a  alteração  se  dará apenas na tabela ‘projeto’.

Formas Normais Relacionais

• Exemplo de uso da 3FN– Identificar/remover atributos não dependentes de atributos não chave

empregado empregador endereçoEmpregador   (tabela empregado)

– ‘endereçoEmpregador’ não é dependente da chave ‘empregado’

Formas Normais Relacionais

• Exemplo de uso da 3FN ­ cont– Identificar/remover atributos não dependentes de atributos não chave 

(nova tabela criada, ok)

Solução:empregado empregador          (tabela empregado)

empregador endereçoEmpregador      (tabela empregador)

– Assim como na 2FN, problemas de redundância e múltiplas atualização justificam a aplicação dessa normalização.

Referências

• Luis,  A.  M.  Palazzo,    Introdução  à  Programação Prolog, Educat, 1997.