Formalismo Lógico
Modelagem de
Preferências
AULA 9
PPG107 - 2012
SISTEMAS DE BANCO DE DADOS –
Pós-graduação em CC - UFU
Fórmulas de Preferência Condicional
TCP-NETS
Fórmulas de Preferência Condicional
CP-NETS
Fórmulas de Preferência Condicional
R (Y1,…,Yn,….,X,…)
 Conditional Preference Rules (cp-rules)
φ : Y1 = a1 ˄ … ˄ Yn = an
Conditions over Attributes Y1,…,Yn
X = x > X = x’
[Z]
Preference over Attribute X
 Conditional Preference Theory = a finite set of cp-rules
Atributos que são excluídos da exigência Ceteris Paribus
Exemplo
φ : D = Hitchcock
G = thriller > G = drama
ρ : Year = 1960
D = Hitchcock > D = D.Lynch [ Actor ]
[ Actor ]
Toda CP-Net é uma teoria de
preferência condicional
G
D
c>d
t >c
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
G= c > G = d
G=t>G=c
[ø]
[ø]
G = d  D=b > D=w
G = d  D=w > D=h
G = t  D=h > D=w
G = t  D=w > D=b
G = c  D=w > D=b
G = c  D=b > D=h
[ø]
[ø]
[ø]
[ø]
[ø]
[ø]
Ordem de Preferência induzida por
uma Teoria de Pref. Condicional
 Cada cp-rule φ induz uma ordem de preferência >φ
Usa a semântica ceteris paribus para os atributos que não estão em
Z U Y e que são diferentes de X
 Exemplo: BD(Category, Director, Year, Actor)
φ : Category = comedy
Director = F. Capra >Director = Hitchcock [Year]
O1 = (Cat=comedy, Dir = F.Capra, Year = 1960, Actor = J.Stewart)
O2 = (Cat=comedy, Dir = Hitchcock,Year = 1954, Actor = J.Stewart)
O1 >φ O2
Ceteris paribus
Ordem de Preferência
 Uma cp-theoria Ψ induz uma ordem de preferência >Ψ
Para cada fórmula φ de Ψ considera-se a ordem induzida > φ
Considera-se a união de todas estas ordens U>φ,
para φ em Ψ
A ordem de preferência induzida pela teoria =
fecho transitivo de U>φ, para φ em Ψ
>Ψ = fecho transitivo de U>φ, para φ em Ψ
Ordem de Preferência
Teoria Ψ = { φ , ρ }
 Considera-se todos os pares de tuplas que podese ordenar diretamente utilizando a regra φ
 Considera-se todos os pares de tuplas que podese ordenar diretamente utilizando a regra ρ
 Considera-se a união destes dois conjuntos de
pares de tuplas.
 Inclui-se neste conjunto todos os pares de tuplas
obtidos por transitividade.
Ordem de Preferência
R(A,B,C)
Tuplas ordenadas diretamente
pela regra φ
abc
Tuplas ordenadas diretamente
pela regra ρ
ab’c
ab’c’
a’b’c
a’bc
a’b’c’
abc’
Primeira iteração da transitividade
Segunda iteração da transitividade
a’bc’
Exemplo
Teoria Ψ = { φ , ρ }
φ : Dir = Hitchcock
ρ : Year = 1960
Cat. = thriller > Cat. = drama
[ Actor ]
Dir. = Hitchcock > Dir. = D.Lynch [ Actor ]
O1 = (Cat=thriller, Dir = Hitchcock, Year = 1960, Actor = J.Stewart)
O2 = (Cat=drama, Dir = Hitchcock, Year = 1960, Actor = P. Newman)
O3 = (Cat=drama, Dir = D.Lynch, Year = 1960, Actor = A. Hopkins)
O1 > φ O2
O1 >Ψ O3
O2 > ρ O3
Grafo de Dependência
Grafo associado a uma teoria Ψ


Vértices: atributos que aparecem em Ψ
Arcos:
 a)
(Y,X) onde Y aparece do lado esquerdo da regra e
X do lado direito da regra na parte da ordenação.
 (Y,X) onde Y aparece do lado direito da regra na
parte de ordenação e X aparece dentro de colchetes
do lado direito da regra
Exemplo
φ1 : Dir = Lynch
[Y]
[C]
φ3 : Year = 1954
Cat. = thriller > Cat. = drama
Dir. = Hitchcock > Dir. = D.Lynch
Dir. = D.Lynch > Dir. = Hitchcock
φ4 : Cat = drama
Dir = D.Lynch > Dir = Hitchcock
[Y]
φ2 : Year = 1960
D
Y
C
Ordens Locais

ordem sobre o domínio dos atributos:
 Sejam A1,…,An
= atributos que aparecem na
parte esquerda das regras
 Sejam B1, …, Bk = atributos que aparecem na
parte direita das regras (parte da ordenação)
 Cada tupla t sobre os atributos (A1,…,An)
determina uma ordem local sobre o domínio do
atributo Bj, ( 1 ≤ j ≤ k )
Consistência Local

Uma teoria é localmente consistente se as
ordens locais produzidas em cada atributo
do lado direito são irreflexivas.
Teoria Consistente

A cp-theoria Ψ é consistente se >Ψ é irreflexiva
Não se pode deduzir o1 >Ψ o2 e o2 >Ψ o1

Teste de Consistência (Wilson 2004)
Ψ é consistente se
seu grafo de dependência é acíclio e
Ψ é localmente consistente
Exemplo
φ1 : Dir = Lynch
Cat = thriller > Cat = drama
[Y]
φ2 : Year = 1960
[C]
φ3 : Year = 1954
Dir = Hitchcock > Dir = D.Lynch
Dir = D.Lynch > Dir = Hitchcock
φ4 : G = drama
Dir = D.Lynch > Dir = Hitchcock
[Y]
D
Attributes = Y, D, C
Y
C
Database:
O1 = (1960, Lynch, thriller)
O2 = (1960, Hitch, drama)
O3 = (1954, Lynch, drama)
O2 > O1 > O3 > O2
Dom(Y) = {1960, 1954}
Dom(D) = {Hitch, Lynch}
Dom(C) = {t, d}
O1: hitch>lynch
dom(D)
thriller>drama
dom(C)
O2: hitch >lynch
dom(D)
O3: lynch > hitch
dom(D)
Ordem local sobre dom(D)
não é irreflexiva !
Tuplas Preferidas
Lista os atributos (X1,…,Xn) na ordem
compatível com o grafo de dependência
graph(Ψ)
 Pega o melhor valor x1 de dom(X1)
 Pega o melhor valor x2 de dom(X2) conditionado
a x1
 …
Observação:
como a ordem não é total, pode haver
diversas tuplas preferidas

Exemplo
φ1 : Dir = Hitchcock
φ2 : Year = 1960
Cat. = thriller > Cat. = drama
Dir. = Hitchcock > Dir. = D.Lynch
φ3 : Year = 1954
Dir. = D.Lynch > Dir. = Hitchcock
φ3 : Year = 1954
Cat = drama > Cat = comedy
D
Y>D>C
Y
C
Melhor valor para Y : qualquer um
Y = 1960
Best D = Hitch
D = Hitch
Best C = thriller
O = (1960, Hitch, thriller) é uma tupla
preferida.
Y = 1954
Best D = Lynch
D = Lynch
Best C = drama
O = (1954, Lynch, drama)
é outra tupla preferida
Exercício
Considere a relação R(A,B,C,D) e as seguintes regras de preferências:
A = a  B=b1 > B = b2 [D]
B = b1  C=c1 > C=c2 [D]
A = a  C = c2 > C=c3 [D]
C = c1  D = d1 > D=d2 [A]
a)
Esta cp-teoria é consistente ?
a)
Dê o grafo BTG associado a esta cp-teoria, sabendo que dom(A) = {a,a1},
dom(B) = {b1,b2}, dom(C) = {c1,c2,c3}, dom(D) = {d1,d2}
CPref-SQL: A query
language supporting
conditional preferences
Fabiola Pereira
Sandra de Amo – [email protected]
Marcos Roberto Ribeiro
Federal University of Uberlandia- Brazil
Motivação
Movies(Title, Director, Genre, Year)
My preferences:
(1)
(2)
(3)
For Woody Allen’s films: I prefer comedies better than
thrillers.
For Robert Altman’s films: I prefer thrillers to comedies.
For comedies: I prefer the more recent ones, produced
after 1990.
Query: Give the titles of the films which most fulfill my
wishes among those stored in the database,
produced after 1975.
CPref-SQL Query
CREATE PREFERENCES MyPrefs AS
If D = wa then (G=c) > (G=t) AND
If D = ra then (G=t) > (G=c) AND
If G = c then (Y ≥ 1990) > (Y < 1990)
SELECT MOVIES.Titles
FROM MOVIES
Hard Constraint
WHERE Year > 1975
ACCORDING TO PREFERENCES MyPrefs
A Conditional
Preference Theory
(cp-theory) =
Set of Preference
Rules
Soft Constraint
CPref-SQL

SQL + SelectBest F(R)
F = cp-teoria sobre a relação R

Semântica( “Best Match Only” semantics)
SelectBest (R) = { t ε R | não existe t’ ε R, t’ > t }
Bloco básico de CPref-SQL
SELECT <attribute-list>
FROM <tables>
WHERE <hard conditions>
ACCORDING TO PREFERENCES
<cp-rules (soft conditions)>
GROUP BY <attribute-list>
ORDER BY <attribute-list>
Plano de Execução básico
SELECT ------: OPERADOR DE PROJEÇÃO
SelectBest (PREFERENCES) ---:
NOVO OPERADOR BEST
WHERE (hard constraints) ----: OPERADOR DE SELEÇÃO
FROM ----: OPERADOR DE JUNÇÃO
R1
…
Rn
CPrefSQL não é mais expressiva que SQL !!
CPrefSQL pode ser convertida em SQL
CREATE OR REPLACE VIEW Rules
(title,genre,years,director,actor,tit,gen,yea,dir,act) AS
CREATE PREFERENCES mypref
FROM movies AS
genre = ‘drama > genre =
‘musical’ [1,5]
AND
years = 90 > years = 80 [1,4,5]
AND
IF years = 80 THEN genre =
‘drama’ > genre = ‘comedy’
[1]
(SELECT *
FROM movies M, movies M1
WHERE M.genre = ‘drama' AND M1.genre = ‘musical'
AND M.director = M1.director AND M.years =
M1.years)
UNION
(SELECT *
FROM movies M, movies M1
WHERE M.years = 90 AND M1.years = 80 and M.genre
= M1.genre)
UNION
(SELECT *
FROM movies M, movies M1
WHERE M.years = 80 and M1.years = 80 and M.genre =
‘drama’ and M1.genre = ‘comedy’ and
M.director = M1.director and M.actor =
M1.actor);
CPrefSQL não é mais expressiva que SQL !!
CPrefSQL pode ser convertida em SQL
WITH RECURSIVE Recursion
( tit, gen, yea, dir, act, title, genre, years, director, actor ) AS (
SELECT *
FROM movies
WHERE genre <> ‘romance’
ACCORDING TO PREFERENCES
mypref
( SELECT * FROM Rules )
UNION
( SELECT M.title, M.genre, M.years, M.director, M.actor,
R.title, R.genre, R.years, R.director, R.actor
FROM Rules M, Recursion R
WHERE M.tit = R.tit AND
M.gen = R.gen AND
M.yea = R.yea
M.dir = R.dir AND
M.act = R.act ) )
SELECT *
FROM movies
WHERE genre <> ‘romance’
EXCEPT
SELECT R.title, R.genre, R.years, R.director, R.actor
FROM Recursion R;