Transcript
Pauta Certamen 2 de Bases de Datos II Primer Semestre 2013 Profesora: Loreto Bravo La prueba tiene un total de 30 puntos m´ as 5 puntos bonus. 1. Diga cuales son las relaciones de poder expresivo entre los lenguajes dados en cada una de las partes de esta pregunta. Diga si son equivalentes, si uno domina al otro o si no hay relaci´on de dominancia entre ellos y justifique sus respuestas. En todas las preguntas puede asumir que los lenguajes est´an escritos en forma normal: Π1 . . . Πn σ1 . . . σm (R1 × . . . × Rl ). Lo u ´nico que var´ıa entre los ejemplos son las condiciones de selecci´on. (a) [10 puntos] Asuma que el dominio de los atributos es infinito, ordenado y que, por lo tanto las comparaciones =, 6=, ≤ y ≥ est´an definidos. 1. S= PC: donde las operaciones de selecci´on son solo de dos formas: σA=c y σA=B donde A y B son atributos y c es una constante. 2. S6= PC: S= PC, m´as σA6=c y σA6=B donde A y B son atributos y c es una constante. 3. S≤ PC: S= PC, m´as σA≤c , σA≥c , σA≤B y σA≥B donde A y B son atributos y c es una constante. 4. S6=,≤ PC: S= PC, m´as σA6=c , σA6=B , σA≤c , σA≥c , σA≤B y σA≥B donde A y B son atributos y c es una constante. Soluci´ on: Esta es la soluci´on para las partes (a) y (b) donde la posici´on (Li , Lj ) contiene v si Li v Lj y 6v si Li 6v Lj : S= PC S6= PC S≤ PC S6=≤ PC S=∨ PC S6=∨ PC S≤∨ PC S6=≤∨ PC S= PC v v v v v v v S6= PC 6v(Q1) 6v(Q2) v 6v(Q1) v 6v(Q2) v S≤ PC 6v(Q3) 6v(Q3) v 6v(Q3) 6v(Q3) v v S6=≤ PC 6v(Q1) 6v(Q3) 6v(Q2) 6v(Q1) 6v(Q3) 6v(Q2) v S=∨ PC 6v(Q4) 6v(Q4) 6v(Q4) 6v(Q4) v v v S6=∨ PC 6v(Q1) 6v(Q4) 6v(Q2) 6v(Q4) 6v(Q1) 6v(Q2) v S≤∨ PC 6v(Q3) 6v(Q3) 6v(Q4) 6v(Q4) 6v(Q3) 6v(Q3) v S6=≤∨ PC 6v(Q1) 6v(Q3) 6v(Q2) 6v(Q4) 6v(Q1) 6v(Q3) 6v(Q2) Todas las relaciones v se demuestran en forma trivial. Por lo tanto s´olo es necesario justificar las relaciones 6v dando un ejemplo de una consulta que no puede ser reescrita. A continuaci´on se dan algunos ejemplos de consultas que justifican las relaciones. Q1: σA6=c R, donde A es un atributo y c es una constante en dom. Esta consulta pertenece a los lenguajes S6= PC, S6=≤ PC, S6=∨ PC y S6=≤∨ PC y no puede ser reescrita en S= PC ni en S=∨ PC ya que puede requerir infinitas disyunciones de igualdades.
1
Certamen 2
11 de julio, 2013 Q2: σA6=B R donde A y B son atributos en R. Esta consulta pertenece a los lenguajes S6= PC, S6=≤ PC, S6=∨ PC y S6=≤∨ PC; y no puede ser reescrita en una consulta de S≤ PC o S≤∨ PC ya que se requerir´ıan infinitas disyunciones asignando todos los posibles valores a A y B de dom que hacen que se cumpla la condici´on de desigualdad. Q3: σA≥c R, donde A es un atributo y c es una constante en dom. Esta consulta pertenece a los lenguajes S≤ PC, S6=≤ PC, S≤∨ PC y S6=≤∨ PC; y no puede ser reescrita en S= PC, S6= PC, S=∨ PC, ni en S6=∨ PC ya que puede requerir infinitas disyunciones de igualdades. Q4: σA=c∨B=d R donde A, B son atributos y c, d constantes en dom. Esta consulta pertenece a los lenguajes S=∨ PC, S6=∨ PC, S≤∨ PC y S6=≤∨ PC; y no puede ser reescrita en S= PC, S6= PC, S≤ PC, ni en S6=≤ PC ya que puede requerir infinitas selecciones en S= PC, o puede requerir infinitas disyunciones de igualdades.
(b) [10 puntos] Asuma que el dominio de los atributos es infinito, ordenado y que, por lo tanto las comparaciones =, 6=, ≤ y ≥ est´an definidos. 1. S= PC 2. S6= PC 3. S≤ PC 4. S6=,≤ PC 5. S= PC∨ : S= PC m´as ∨ en la selecci´on. 6. S6= PC∨ : S6= PC m´as ∨ en la selecci´on. 7. S≤ PC∨ : S≤ PC m´as ∨ en la selecci´on. 8. S6=,≤ PC∨ : S6=,≤ PC m´as ∨ en la selecci´on. Soluci´ on: Ver la soluci´on a la parte (a). (c) [5 puntos (bonus)] Si consideramos que el dominio de cada atributo es finito, algunas de las relaciones de poder expresivo de la parte (1a) cambian. De un ejemplo de una relaci´on que cambia, diga cu´al es la nueva relaci´on y explique por qu´e. Soluci´ on: Considere, por ejemplo, el dominio finitio {1, 2, 3, 4}. La consulta σA6=1 R puede ser reescrita como σA=2∨A=3∨A=4 R. Si generalizamos, toda consulta en S6= PC puede ser reescrita como una consulta en S= PC by replacing in a query Π1 . . . Πn σ1 . . . σm (R1 × . . . × Rl ) in S6= PC, every σA6=c by σ(W A=d) d∈(dom\{c})
and σA6=B by
σ(W
c∈dom
(
W d∈(dom\{c})
A=c∧B=d))
Luego, las conjunciones pueden ser reemplazadas distribuyendo las disyunciones y considerando que σA=c∧B=d ≡ σA=c σB=d
P´agina 2 de 3
Pase a la siguiente p´agina. . .
Certamen 2 11 de julio, 2013 2. Una red social almacena informaci´on de colaboraci´on entre grupos de investigaci´on. Para esto utiliza una tabla Rel con sort(Rel) = [Ins1, Ins2] contiene una tupla (x, y) si los institutos de investigaci´on x e y colaboran entre ellos. Es com´ un que cuando un instituto desea contactar a otro instituto, busque una cadena de contacto a trav´es de otros institutos con los que colabora y las colaboraciones que ellos tienen. (a) [5 puntos] Escriba en Datalog un programa que calcule en forma recursiva para toda instituci´on las instituciones con las que se puede colaborar utilizando la red de contactos que ya tienen las instituciones RedContacto(x, y). Tambi´en tome en cuenta que si (x, y) ∈ Rel entonces tambi´en es necesario considerar que (y, x) ∈ Rel. Soluci´ on: Rel(y,x) :- Rel(x,y). Rel(x,x) :- Rel(x,y). RedContacto(x,y) :- Rel(x,y). RedContacto(x,z) :- Rel(x,y), RedContacto(y,z).
(b) [5 puntos] ¿Que contiene RedContacto para la siguiente tabla Rel: Ins1 Ins2 UdeC PUC PUC UChile UChile UFRO UBB UChile UChile UBB Soluci´ on: La tabla contiene todas las combinaciones de {UdeC, PUC, UChile, UFRO, UBB}
P´agina 3 de 3
Fin del certamen.