UNIVERSIDADE FEDERAL DE
UBERLÂNDIA
Programa de Mestrado em Ciência da
Computação
Disciplina : Sistema de Bancos de Dados - 10 Semestre 2009
Professora : Sandra Aparecida de Amo
Lista de Exercı́cios no 2
Algumas definições que serão utilizadas nesta lista
Ordem Parcial e Relação de Preferência Seja R(A1, ..., An) um esquema relacional e T up(R)
o conjunto de todas as tuplas sobre R, isto é, T up(R) = dom(A1) × dom(A2) × ... ×
dom(An). Uma relação de preferência sobre T up(R) é uma relação de ordem estrita
sobre T up(R), isto é, uma relação < ⊆ T up(R) × T up(R) satisfazendo as seguintes propriedades:
• Irreflexividade: para todo t ∈ T up(R), t 6< t, isto é, (t, t) 6∈<
• Transitividade :para quaisquer t1, t2, t3 ∈ T up(R), se t1 < t2 e t2 < t3 então
t1 < t3.
Ordem Total . Uma relação de preferência é dita total se para todo t1, t2 ∈ T up(R) temos
uma das duas alternativas: t1 < t2 ou t2 < t1, isto é, duas tuplas quaisquer sempre são
comparáveis, não existe indiferença. Uma ordem que não é total é dita parcial.
Ordem Anti-transitiva (ou Ordem Fraca) . Uma relação de preferência é dita anti-transitiva
se a seguinte propriedade é verificada:
Antitransitividade :para quaisquer t1, t2, t3 ∈ T up(R), se t1 6< t2 e t2 6< t3 então
t1 6< t3.
Composição Pareto de Ordens locais . Para cada i = 1, ..., n, seja <i uma ordem de
preferência parcial sobre os elementos de dom(Ai). Definimos a composição pareto de
<1 , ..., <n como sendo uma relação < sobre T up(R) tal que
Se t = (a1,...,an) e s = (b1,...,bn), então t < s se e somente se as duas condições abaixo
são verificadas:
• existe i = 1, ..., n tal que ai < bi .
• para todo j = 1, ..., n, j 6= i, temos que: bj 6< aj .
1
Exercı́cios sobre CP-Nets, TCP-Nets e Fórmulas de Preferências
1. Considere as preferências apresentadas pelo usuário que vai participar de uma conferência
nos US:
(a) Como sou muito ocupado, prefiro partir um dia antes da conferência.
(b) Prefiro a British Airways pois minha bagagem já foi extraviada com a KML !
(c) Entre os voos partindo dois dias antes da conferência, prefiro um voo noturno, pois
isto vai me permitir trabalhar durante o dia do voo. Entre os voos partindo um dia
antes, prefiro viajar de dia para poder passar a noite descansando no hotel
(d) Em voos diurnos, estou acordado o tempo todo, e como sou fumante, prefiro fazer
conexões. Em voos noturnos, entretanto, prefiro voos diretos.
(e) Em voos noturnos, prefiro a classe econômica, ja que não me incomodo onde vou
dormir, e o preço compensa. Entretanto, num voo diurno já prefiro a business class
pois, assim, posso apreciar melhor a boa comida, vinho, etc.
(f) Para mim, a hora da partida é mais importante do que a companhia aérea.
(g) Num voo diurno da KLM, uma parada intermediária em Amsterdam é mais importante do que viajar de classe executiva (acho que a classe executiva da KLM não
tem uma boa taxa custo-beneficio, vale mais a pena poder visitar um cassino no
aeroporto de Amsterdam.
(h) Num voo noturno da BA, o fato do voo ser direto é mais importante para mim do
que viajar na classe econômica. Estou disposto a pagar pela business class para não
passar um minuto no aeroporto de Heathrow à noite !!
(i) Num voo diurno da BA, a classe executiva é mais importante para mim do que
poder fazer uma parada (já que é super dificil encontrar uma área de fumantes no
aeroporto de Heathrow!)
Pede-se:
(a) Modele esta situação através de uma TCP-Net.
(b) Dê o grafo de ordenação induzido por esta TCP-Net, onde os vértices são as tuplas de
T up(R(Companhia, Conexao, Class, Hora − P artida, Dia − P artida) e uma aresta
de t1 para t2 significa que t1 é preferido a t2.
(c) A ordem de preferência induzida por esta TCP-Net é total ? Por que ?
2. Um cliente de um restaurante descreve ao garçon suas preferências como segue:
• Prefiro um prato principal a base de carne do que um prato a base de peixe.
• Caso o prato principal for a base de carne, prefiro um vinho tinto a um vinho branco.
Caso for peixe, prefiro vinho branco a vinho tinto.
• Quanto à entrada, se o vinho escolhido for tinto, prefiro um patê de fı́gado acompanhado de alface. Se o vinho for branco, prefiro uma mousse de salmão.
• Quanto a sobremesa, se o prato principal é a base de carne, prefiro como sobremesa
uma taça de frutas com sorvete de baunilha. Se for a base de peixe, prefiro como
sobremesa um bolo de chocolate.
2
• O prato principal é muito mais importante do que a sobremesa ou a entrada.
• Caso o prato principal for a base de carne e o vinho for tinto, a entrada é mais
importante do que a sobremesa. Entretanto, caso o prato principal for peixe e o
vinho for branco, a sobremesa é bem mais importante do que a entrada.
Pede-se:
(a) Construa o modelo que melhor representa estas preferências.
(b) Dê o grafo de ordenação induzido por este modelo de preferências, onde os vértices
são as tuplas de T up(R(PratoPrincipal,Entrada,Vinho,Sobremesa)) e uma aresta de
t1 para t2 significa que t1 é preferido a t2.
(c) Este modelo é consistente ? Justifique sua resposta.
(d) Qual o menu preferido pelo cliente ? É único ?
(e) Caso a única sobremesa disponı́vel seja bolo de chocolate e não tenha vinho branco
no estoque do restaurante, qual seria o menu que mais teria chance de agradar o
cliente ?
(f) Dados os dois menus abaixo:
m1 = (carne, mousse de salmão, vinho tinto, bolo de chocolate) e
m2 = (carne, patê, vinho branco, frutas)
seria possı́vel compará-los através da TCP-Net ? Em caso positivo, explique como
a ordem de preferência entre estes dois menus seria deduzida da TCP-Net. Em
caso negativo, justifique por que os dois menus seriam indiferentes ao cliente. Neste
caso, seria possı́vel o garçon propor um dos menus, sem que esta proposta fosse
inconsistente com as outras preferências estabelecidas pelo cliente ?
3. Considere um sistema inteligente para organizar a apresentação de documentos multimidia satisfazendo certas preferências especificadas pelo médico usuário do sistema. O
funcionamento do sistema, bem como as preferências são descritas nas 3 últimas páginas
desta lista de exercı́cios.
(a) Dê a cp-teoria correspondente à CP-Net da Figura 7.
(b) Qual a apresentação preferida pelo médico ?
(c) Suponha que o médico decida que quer ver a parte do topo à direita da tomografia
computadorizada. Qual a apresentação do conjunto de documentos que melhor se
adequa a suas preferências neste caso ?
(d) Suponha agora que em cima desta apresentação o médico decida esconder o raio
X. Qual a apresentação do conjunto de documentos que melhor se adequa a suas
preferências neste caso ?
(e) Suponha agora que em cima desta última apresentação (sem o raio X) ele decida que
quer ver a tomografia computadorizada completa (as 4 facetas). Qual a apresentação
do conjunto de documentos que melhor se adequa a suas preferências neste caso ?
4. Se uma CP-Net é consistente, então podemos concluir que seu grafo de dependência é acı́
clico ? Justifique A reciproca é verdadeira ? Justifique.
3
5. Considere a seguinte CP-Net:
A
a > a’
B
a: b > b’
a’ : b’ > b
C
b: c > c’
b’ : c’ > c
Pede-se:
(a) Dê o grafo de ordenação induzido por este modelo de preferências, onde os vértices
são as tuplas possiveis de dom(A) × dom(B) × dom(C), e uma aresta de t1 para t2
significa que t1 é preferido a t2.
(b) Esta CP-Net é consistente ?
(c) Caso for consistente, apresente a ordem induzida pela CP-net sobre as tuplas.
(d) Esta ordem é total ? Em caso negativo, é possivel completá-la de modo a obter uma
ordem total compativel ? Esta ordem total é única ? (isto é, existe apenas uma
maneira de completar a ordem induzida pela CP-Net ?)
6. Seja CARRO(MARCA,CATEGORIA,PREÇO,COR,POTENCIA,KM) um esquema relacional que estoca dados de uma revendedora de carros usados. Um cliente da revendora
expressa as seguintes preferências relativas à aquisição de um carro usado.
(a) Prefiro a marca Chevrolet à marca VOLKSWAGEN.
(b) Se for uma caminhonete Chevrolet, prefiro que seja preto do que vermelha. Entretanto, se for um carro de passeio da Volkswagen, prefiro que seja branco.
(c) Gostaria de gastar no máximo 40 mil reais nesta compra. Suponha que os preços dos
carros da agência se dividem em três categorias: a primeira, vai de 10000 a 20000, a
segunda vai de 21000 a 40000, e a terceira vai de 41000 a 80000.
(d) Entre dois carros da mesma marca, prefiro aquele que é mais potente.
(e) Se o carro for Chevrolet e uma caminhonete, prefiro aquele com a menor quilometragem. (Suponha que as quilometragens disponı́veis na agência se dividem em duas
categorias: as maiores do que 50.000km e as abaixo de 50.000Km).
4
(a) Dê a teoria de preferência condicional correspondente.
(b) Esta teoria é localmente consistente ?
(c) Esta teoria é consistente ?
(d) Dê a opção ideal de compra.
(e) Considere as seguintes opções apresentadas pelo vendedor:
• Carro 1: (chevrolet, carro de passeio, 20000 reais, branco, 2.0, 80000)
• Carro 2: (Volkswagen, carro de passeio, 30000 reais, branco, 2.0, 105.000)
Qual delas o cliente preferiria ? (Pode ser que o cliente seja indiferente ás duas
opções).
Exercı́cios sobre propriedades das relações de ordem
7. Pede-se:
(a) Dê exemplo de uma ordem que é antitransitiva.
(b) Dê exemplo de uma ordem que não é antitransitiva.
8. Mostre que toda ordem total é anti-transitiva, mas que a recı́proca não é verdadeira.
9. Mostre que:
(a) toda ordem antitransitiva pode ser representada por uma função score.
(b) se uma ordem pode ser representada por uma função score, então é anti-transitiva.
(c) se f é uma função score associada a uma ordem então f (a) = f (b) se e somente se
a e b são indiferentes.
10. Mostre que a composição pareto de ordens parciais anti-transitivas é uma ordem parcial,
isto é, satisfaz as propriedades de irreflexividade e transitividade.
11. Mostre que a composição pareto de ordens parciais anti-transitivas nem sempre é uma
ordem anti-transitiva (dê um contra-exemplo).
12. Mostre que a composição pareto de ordens totais nem sempre é uma ordem total (dê um
contra-exemplo).
13. Mostre que a composição pareto de ordens parciais nem sempre é uma ordem parcial
(dê um contra-exemplo onde a propriedade da transitividade não é satisfeita pela ordem
composta).
14. Mostre que a composição ”cascade” (que atribui graus de importância a atributos) de
ordens anti-transitivas é uma ordem anti-transitiva.
15. Mostre que a composição ”cascade” de ordens totais é uma ordem total.
16. Mostre que a composição ”cascade” de ordens parciais nem sempre é uma ordem parcial
(não satisfaz a transitividade, por exemplo).
5
Exercı́ıcios sobre as linguagens de consultas PrefSQL e CPrefSQL
17. Considere o esquema de banco de dados da revendora de carros usados CARROS(MARCA,CAT,
PREÇO, COR, POTENCIA, KM).
(a) Dê a expressão da linguagem CPref-SQL correspondente à seguinte consulta do
cliente do exercicio anterior: Quais os carros de passeio com quilometragem abaixo
de 50.000km que mais se adequam às minhas preferências ?
(b) Calcule a resposta desta
MARCA
CAT
chevrolet
passeio
chevrolet Caminh.
volkswagen passeio
volkswagen Caminh
chevrolet
passeio
consulta sobre o seguinte banco de dados:
PREÇO
COR
POTÊNCIA
KM
10.000 Vermelho
2.0
30.000
10.000 Vermelho
2.0
105.000
20.000
branco
1.0
40.000
30.000
preto
2.0
70.000
50.000
preto
1.0
10.000
(c) Apresente um plano de execução que calcula a resposta esperada.
18. Os operadores de seleção da álgebra relacional e o Select-Best de CPrefSQL comutam ?
Em caso afirmativo, prove sua afirmação, em caso negativo dê um contra-exemplo.
19. Considere o esquema relacional CARRO(MARCA,CATEGORIA,PREÇO,COR,POTENCIA,KM).
Considere as seguintes preferências de um cliente:
• Prefiro um carro da marca Chevrolet, mas se não tiver, poderia ser um Ford.
• Prefiro um carro de passeio, mas se não tiver, posso aceitar outro tipo de carro,
menos uma van.
• Quanto á cor, aceito qualquer uma menos vermelho.
• Prefiro um carro com quilometragem em torno de 30.000 Km
• Estou disposto a pagar entre 20.000 e 30.000 reais, embora a questão do preço seja
menos importante do que a quilometragem.
• Quanto à potência, gostaria que fosse a máxima possı́vel, embora esta questão de
potência seja menos importante do que o preço.
• Se não for possı́vel atender às minhas preferências de forma ideal, posso aceitar o
que tiver na agência que mais se adequa às minhas preferências só que não posso
pagar mais do que 35000 reais.
Pede-se:
(a) Dê a expressão da linguagem Pref-SQL desta consulta.
(b) Calcule a resposta sobre o seguinte banco de dados:
6
MARCA
chevrolet
chevrolet
ford
chevrolet
volkswagen
ford
chevrolet
ford
chevrolet
CAT
passeio
Caminh.
passeio
van
passeio
van
Caminh.
passeio
passeio
PREÇO
40.000
10.000
20.000
30.000
50.000
40.000
50.000
20.000
35.000
COR
Vermelho
Vermelho
branco
preto
preto
preto
preto
verm
Vermelho
POTÊNCIA
2.0
2.0
1.0
2.0
1.0
2.0
1.0
1.0
2.0
KM
30.000
105.000
40.000
45.000
10.000
45.000
10.000
28.000
30.000
(c) Suponha que o usuário deseje, além de saber quais são suas opções de carro preferidas,
ter uma idéia da qualidade de cada opção no que se refere a quilometragem e a
cor. Qual seria a expressão de PrefSQL que seria adequada para responder a sua
consulta ? Exiba a resposta desta consulta quando aplicada ao banco de dados do
item anterior.
20. Mostre que todos os operadores da linguagem PrefSQL definem ordens parciais antitransitivas sobre os domı́nios dos atributos.
21. A linguagem de preferências PrefSQL utiliza a composição pareto e ”cascade” como ordem
de preferência entre as tuplas. Quais as diferenças conceituais entre a ordem de preferência
utilizada por PrefSQL e a ordem de preferência de CPrefSQL ? Quais as propriedades
satisfeitas por uma que não são satisfeitas pela outra ?
7
An Example Application
We now turn to an illustration of the use of CP-nets in the context of a CP-net based system
for adaptive multimedia document presentation. Applications based on this system for the
presentation of web-based content and multi-media medical data were recently presented
by Domshlak et al. (2001) and Gudes et al. (2002). Through this example we demonstrate
the simplicity of preference specification using CP-nets, the utility of acyclic networks, and
the use of the optimization algorithm described above.
The system consists of two tools—the authoring tool, and the viewing tool. The central
part of the authoring tool is a module for the specification of a CP-net corresponding to
the created and/or edited multimedia document. Using this CP-net, a content provider
express her preferences regarding the presentation of the document content. For example,
the content provider may prefer that some material be presented if and only if some other
material is not presented. The result of such preference-based multimedia document design
is a meta-document specifying both what to present and how to present it.
The description of the content provider’s preferences, as captured by an acyclic CP-net,
becomes a static part of the document, and sets the parameters for its initial presentation.
Given such a document, the viewing tool is responsible for reasoning about these preferences;
specifically, it must determine an optimal reconfiguration of the document context after
interaction of the viewer with the document. In this process, the user’s k most recent
content choices are viewed as constraints of the form “these items must appear as I specified”.
Subject to these constraints, an optimal document presentation with respect to the content
provider’s CP-net must then be generated. Thus, for each particular session, the actual
presentation changes dynamically based on the user’s choices. More precisely, whenever
new user input is obtained, the optimization algorithm constructs the best presentation of
all document components with respect to the content provider’s preferences among those
presentations that conform to the user’s recent viewing choices. This process uses the
forward sweep procedure described above.
Example (Multimedia Document) Consider a medical record that consists of six components: two components correspond to a set of medical tests conducted in 2001—an X-ray
image and textual notes of a physician—and four components correspond to a set of medical
tests from 2002—a CT (computerized tomography) image, an X-ray image, a graph illustrating results of electromyography, and textual notes of a physician. For the purposes of
illustration, we assume the preferences of a content provider (e.g., the latter physician) over
the presentation options of these components can be captured using the CP-net shown in
Figure 7. The specific details of the preferences—the nature of the preferential dependencies
and the precise details of the CPTs are summarized as follows:
• CT-image [CT image, 2002] consist of four CT images of different parts of the body,
and it is shown in Figure 6(a). There are six presentation options for CT-image: it can
be either completely presented (ctplain ), or completely hidden (cthide ), or presented by
(a)
(b)
(c)
(d)
Figure 6: Document components in Multimedia Document example.
CT−image
GG GG
GG
GG
GG
GG
#
X−ray
ww
ww
w
w
ww
ww
w
{w
Graph
X−ray−old
Notes
Notes−old
Figure 7: Multimedia Document CP-net.
a zoom-in on one of its four parts (ctlt , ctrt , ctlb , and ctrb , standing for left-top, righttop, left-bottom, and right-bottom parts, respectively). The physician’s preference
over the presentation options of CT-image is unconditional:
cthide ctlt ctrt ctlb ctrb ctplain
• X-ray [X-ray, 2002] can be either hidden (xrayhide ), or presented as is (xrayplain ), or
presented after a segmentation (xraysegm ); the image and its segmentation are depicted
in Figures 6(b) and 6(c), respectively. The preference over the presentation options
of X-ray depends on the presentation of CT-image:
ctplain
¬(ctplain ∨ cthide )
cthide
xrayhide xrayplain xraysegm
xrayplain xraysegm xrayhide
xraysegm xrayplain xrayhide
• Graph [Electromyography, 2002] is shown in Figure 6(d), and it can be either presented
(graphplain ), or hidden (graphhide ). The preference over the presentation options of
Graph depends on the presentation of both CT-image and X-ray:
(ctlt ∨ ctrt ∨ ctlb ∨ ctrb ) ∨ xraysegm
otherwise
graphplain graphhide
graphhide graphplain
• Notes [Textual notes, 2002] can be either fully presented (notesplain ), or summarized
(notessumm ), or omitted all together (noteshide ). The preference over the presentation
options of Notes depends on the presentation of both CT-image and Graph:
cthide
¬(cthide ) ∧ graphplain
otherwise
noteshide notessumm notesplain
notessumm notesplain noteshide
noteshide notessumm graphplain
• X-ray-old [X-ray, 2001] can be either hidden (xray−oldhide ), or presented as is (xray−oldplain );
the image is depicted below. The preference over the presentation options of X-ray-old
depends on the presentation of X-ray:
xrayhide
¬(xrayhide )
xray−oldhide xray−oldplain
xray−oldplain xray−oldhide
• Notes-old [Textual notes, 2001] can be either presented (notes−oldplain ), or omitted
all together (notes−oldhide ). The preference over the presentation options of Notes-old
depends on the presentation of X-ray-old:
xray−oldhide
xray−oldplain
notes−oldplain notes−oldhide
notes−oldhide notes−oldplain