Linguagem de Consultas
com suporte a Preferências
AULA 10
PPG107 - 2012
SISTEMAS DE BANCO DE DADOS –
Pós-graduação em CC - UFU
Modelo de Preferência
 R(A1,...,An) : esquema relacional
 Operadores de Preferências locais:
 Atuam sobre os valores dos atributos.
 Permitem obter os melhores valores de acordo com
algum critério.
 Operadores de Preferências globais
 Atuam sobre as tuplas
 Resultam de uma combinação de operadores locais
 Permitem obter as melhores tuplas de R(A1,...,An),
satisfazendo de acordo com algum critério.
Operadores Locais : Aproximação
 AROUND <valor alvo>


Favorece valores próximos de um valor alvo.
Caso o valor alvo existe no banco de dados, este é
retornado. Caso contrário, o mais próximo deste valor
é retornado.
 BETWEEN [low,up]



Favorece valores dentro do intervalo [low,up]
Caso valores dentro do intervalo [low, up] existem, tais
valores são retornados.
Caso contrário, os valores mais próximos de low ou up
são retornados.
Exemplo
SELECT * FROM VIAGENS
PREFERRING DURATION AROUND 14
SELECT * FROM VIAGENS
PREFERRING
START-DAY BETWEEN [1/9, 5/9]
Operadores Locais:
Minimização, Maximização
 LOWEST (atributo)

Valores mínimos são privilegiados
 HIGHEST(atributo)

Valores máximos são privilegiados
 Versão SQL (agregados MIN e MAX)

Em PrefSQL é possivel aplicar LOWEST e
HIGHEST sobre uma expressão aritmética
envolvendo diversos atributos ou mesmo
sobre o resultado de uma store procedure.
Exemplo
SELECT * FROM APART
PREFERRING HIGHEST(Area)
SELECT * FROM APART
PREFERRING LOWEST(Preço/Area)
Operadores Locais
Favoritos / não-desejados
 POS(Atributo,Pos-set)
x < y se x não está em Pos-set e y ɛ Pos-set
 NEG(Atributo,Neg-set)
 x < y se x ɛ Neg-set e y ε Neg-set
 POS/NEG(Atributo,Pos-set,Neg-set)
 x < y se (x ɛ Neg-set e y ε Neg-set) ou
(x ɛ Neg-set e x ɛ Pos-set e y ε Pos-set )
 POS/POS(Atributo,Pos1-set,Pos2-set)


x < y se (x ɛ Pos1-set e y ɛ Pos2-set) ou
(x ɛ Pos1-set e x ɛ Pos2-set e y ɛ Pos1-set) ou
(x ɛ Pos1-set e x ɛ Pos2-set e y ɛ Pos2-set)
Exemplo
 SELECT * FROM HOTELS
PREFERRING
POS/NEG (LOCAL,{centro,lidice},{umuarama})
Prefiro um hotel no centro ou no bairro lidice. Caso
não tenha nenhum disponível, pode ser qualquer um
menos no umuarama.
Composição de Preferências Locais
 Composição Pareto = todos os atributos tem
igual importância


t = (a1,…,an)
t > s se


s=(b1,…,bn)
Existe i talque ai > bi e
Para todo j ≠ i, bj não é melhor do que aj (ou
ambos são indiferentes, ou aj > bj)
Exemplo
 SELECT * FROM HOTELS
PREFERRING
POS/NEG (LOCAL,{centro,lidice},{umuarama})
AND
Preço BETWEEN [110, 150]
Introduzindo ordem de importância
entre os atributos
 CASCADE



Associa diferentes níveis de importância às
preferências locais
Aplica uma preferência após a outra.
A ordem em que são apresentadas as
preferências é igual à ordem de importância
entre os atributos
Exemplo
 SELECT * FROM HOTELS
PREFERRING
POS/NEG (LOCAL,{centro,lidice},{umuarama})
CASCADE
Preço BETWEEN [110, 150]
CASCADE
Dog-Accepted = ‘sim’
Combinando composição Pareto com
Cascade
Exemplo: cliente comprando um carro usado.
CARRO(MARCA,CATEGORIA,PREÇO,COR,POTENCIA,KM)
(1) Meu carro favorito deve ser da marca Chevrolet.
Não admito outra marca de carro.
Restrição forte sobre MARCA – não se trata de uma
preferência, mas de uma exigência.
(2) Prefiro que seja uma caminhonete, mas se não tiver,
prefiro que não seja van.
Preferência POS/NEG sobre CATEGORIA
Combinando composição Pareto com
Cascade - continuação
(3) Igualmente importante, quero gastar em torno de 40
mil reais e o carro deve ser tão potente quanto
possível.
Preferência AROUND sobre PREÇO e HIGHEST
sobre POTENCIA
(4) Menos importante para mim é a cor, embora se for
para escolher, prefiro vermelho.
Preferência POS sobre COR
(5) Se houver muitas opções possiveis, decido pelo que
tem menos quilômetros rodados.
Preferência LOWEST sobre KM
Combinando composição Pareto com
Cascade - continuação
SELECT * FROM CARRO
WHERE MARCA = ‘Chevrolet’
PREFERING
POS-NEG(CATEGORIA,{Caminhonete},{Van})
AND PREÇO AROUND 40000
AND HIGHEST(POTENCIA)
CASCADE POS(COR,{Vermelho})
CASCADE LOWEST(KM)
Funções de Qualidade
 Tuplas selecionadas ou rejeitadas pela
cláusula WHERE:

razão da aceitação ou rejeição é clara – não
satisfaz a condição especificada.
 Tuplas selecionadas ou rejeitadas pela
cláusula PREFERRING :

Razão da aceitação ou rejeição não é clara –
não depende somente da tupla, mas também
de seus competidores.
As Funções de Qualidade

TOP(A) : verdadeiro se o valor para o atributo
A é o melhor.

LEVEL(A) = n se o valor do atributo A dista do
valor optimal de n unidades. O valor optimal
está no nível 1.

DISTANCE(A) : para atributos numéricos.
DISTANCE(A) = n se
| valor(A) – valor optimal | = n
Exemplo
Carro MARCA
t1
t2
t3
t4
Alfa Ro
Honda
Jaguar
Audi
t5 Mercedes
t6 Toyota
COR
KM
Branco 19
Verde 19
Amar. 35
Verm. 40
Verm 43
Amar. 51
t1
t2
t6
t3
t4
t5
SELECT MARCA, COR, KM, LEVEL(COR), DISTANCE(KM)
FROM CARRO
PREFERRING POS-POS(COR, {branco}, {Amarelo})
AND KM AROUND 40
Exemplo - continuação
RESULTADO
MARCA
COR
KM L(COR) DIST(KM)
t4
Audi
Verm.
40
t3
Jaguar
Amar.
t1
Alfa Ro
Branco
35
19
3
2
1
0
5
21
Controle de Qualidade
 Utilizado para retornar melhores alternativas,
quando as preferências não podem ser
totalmente satisfeitas.
 Utilizada também quando o usuário
estabelece um certo grau de qualidade para
as respostas.
Exemplo
Um cliente de uma agência de viagens procura um
“pacote” que tenha início por volta do dia 3 de Julho
e dure aproximadamente 2 semanas. Mas não aceita
variações acima de dois dias para cada critério.
SELECT *
FROM VIAGEM
PREFERRING start_day AROUND ‘3/7/2009’
AND DURATION AROUND 14
BUT ONLY DISTANCE(start_day) <= 2
AND DISTANCE(duration) <= 2
Bloco básico de PrefSQL
SELECT <Lista atributos, funções de qualidade>
FROM < tabelas>
WHERE <condições>
PREFERRING <condições de preferência>
GROUPING <lista de atributos>
BUT ONLY <condições but_only>
ORDER BY <lista de atributos>
Semântica de PrefSQL
 Executa as operações de junção da cláusula FROM
e seleciona as tuplas verificando as condições da
cláusula WHERE. Obtém-se assim uma relação R.
 Encontra as tuplas optimais com relação às
preferências da cláusula PREFERRING.
 As tuplas optimais pertencentes à relação R são
retornadas caso exista alguma nestas condições.
 Caso contrário: considera todas as tuplas de R
satisfazendo a condição BUT ONLY e retorna
aquelas que não são dominadas.
Plano de Execução básico
SELECT ------: PROJEÇÃO
BUT-ONLY
≠ø
SelectBest ---:
=ø
BEST-:
TUPLAS
OPTIMAIS
satisfazendo
condição do
Where
SELECIONA TUPLAS
NÃO-DOMINADAS
WHERE ----: SELEÇÃO
FROM ----: OPERADOR DE JUNÇÃO
R1
…
Rn
Exemplo
Tupla
ideal
t7
t1
t4
t2
Não satisfaz a restrição “hard”
da cláusula where
t2 e t4 são as melhores
satisfazendo as preferências
t5
t3
Banco de dados só contém
t2, t4, t5, t7
t2 satisfaz a restrição but-only
t4 não satisfaz a restrição but-only
t6
Resposta: t2
Características da versão 1.3
 Consultas de PREFSQL podem ser
invocadas como sub-consulta do comando
INSERT.
 Sub-consultas da cláusula WHERE não
podem conter a cláusula PREFERRING.
 A cláusula ORDER BY não aceita ordenação
por valores de uma função de qualidade.
 Ordenação por função de qualidade deve ser
codificada de forma ad-hoc.
Implementação de PrefSQL
 Implementação iniciou em 1997- grupo alemão da Universidade
de Augsburg. Primeira versão comercial em 1999.
 Consultas com preferências são traduzidas em consultas SQL.
 Um driver JDBC de Preferências se responsabiliza por esta
tradução e otimização.
 Em seguida o driver JDBC standard de SQL envia a consulta
para o SGBD.
 O otimizador SQL do SGBD otimiza a consulta mais uma vez.
 O plano de execução mais adequado é executado pelo SGBD.
Esquema Geral
Aplicação (ex. e-comércio)
Driver JDBC de Preferências
Otimizador de Preferências
SQL do SGBD
Driver JDBC standard do SQL
Procedimento Geral para encontrar as
melhores tuplas
1. Max:= ø
2. Seleciona uma tupla t1 em R
3. Insere t1 em Max se não existe nenhuma
tupla t2 em R que é melhor do que t1.
4. Repete passos (2) e (3) até que todas as
tuplas foram selecionadas.
5. Retorna Max = tuplas não-dominadas.
Otimizador de Preferências
 Pode invocar algoritmos específicos
(bibliotecas) para encontrar as melhores
tuplas.
OU
 Pode invocar um tradutor que transforma a
consulta com preferência em uma consulta
SQL normal.
 Cabe ao otimizador de preferências analisar
qual a melhor política.
Exemplo
Select * FROM CARROS
PREFERRING MARCA = ‘Audi’ AND
DIESEL = ‘sim’
Semântica Pareto: t1 > t2 se
t1(MARCA) = ‘Audi’ E t2(MARCA) ≠ ‘Audi’ E t1(DIESEL) = t2(DIESEL)
t1(MARCA) = ‘Audi’ E t2(MARCA) ≠ ‘Audi’ E t2(DIESEL) = ‘não’
t1(DIESEL) = ‘sim’ E t2(DIESEL) = ‘não’ E t1(MARCA) = t2(MARCA)
t1(DIESEL) = ‘sim’ E t2(DIESEL) = ‘não’ E t2(MARCA) ≠ ‘Audi’
Tradução em SQL
Create View Aux AS
SELECT *, CASE WHEN MARCA = ‘Audi’ THEN 1 ELSE 2 END AS MARCALEVEL,
CASE WHEN DIESEL = ‘Sim’ THEN 1 ELSE 2 END AS DIESEL-LEVEL
FROM CARROS;
AUX
MARCA MODELO KM DIESEL MARCA-LEVEL DIESEL-LEVEL
1
1
1
2
2
1
2
2
Tradução em SQL
INSERT INTO MAX
SELECT MARCA, MODELO, KM, DIESEL FROM AUX A1
WHERE NOT EXISTS
(SELECT * FROM AUX A2
WHERE (A2.MARCA-LEVEL < A1.MARCA-LEVEL AND
A2.DIESEL-LEVEL <= A1.DIESEL-LEVEL)
OR
(A2.DIESEL-LEVEL < A1.DIESEL-LEVEL AND
A2.MARCA-LEVEL <= A1.MARCA-LEVEL)
Discussão
 PrefSQL não é uma extensão de SQL standard.
 Não tem um poder de expressão maior.
 SQL3 é mais expressivo do que SQL standard
 SQL3 permite consultas recursivas
 É provado que não é possivel realizar consultas
recursivas somente com os operadores do SQL
standard.
 Qualquer operador de otimalidade que tem a
semântica BMO (Best Matches Only) pode ser
expresso com os operadores do SQL standard.