ejemplo de TABLEAUX ALGORITMO, solo ejemplo.pptx

tableaux explicacion

1. DESCOMPOSICION SPI y SPDF

2. Introducción Sin pérdida de información Preservación de Dependencias Funcionales Bi b lio gr afía Dos Características de una Buena Descomposición Sin Pérdida de Información Preservación de Dependencias Funcionales

3. Esquema General 1 Introducción 2 Sin pérdida de información 3 Preservación de Dependencias Funcionales

4. Sin pérdida de información Esquema General 2 Sin pérdida de información Introducción Descomposición binaria Algoritmo del Tableau

5. Definición Si R es un esquema de relación descompuesto en los esquemas R 1 , R 2 , ..., R k y F es un conjunto de dependencias, decimos que la descomposición es sin pérdida de información (SPI) con respecto a F , si pa r a toda relación r pa r a R que satisfaga F : r = π R 1 ( r ) * π R 2 ( r ) * . . . * π R k ( r ) Es decir, no debe perderse información en el proceso de descomposición, de manera tal que r es la junta natural de sus proyecciones sobre los R i

6. Estrategias para comprobar SPI Descomposiciones de dos esquemas Descomposición binaria Descomposiciones en más de dos esquemas Algoritmo del Tableau

7. Esquema General 2 Sin pérdida de información Introducción Descomposición binaria Algoritmo del Tableau

8. Descomposición binaria Teorema de la Descomposición Binaria (HEATH) La descomposición ρ de R, ρ = ( R 1 , R 2 ) es SPI respecto a un conjunto de dependencias funcionales F sí y sólo sí: F + contiene la DF: R 1 ∩ R 2 → ( R 1 - R 2 ) o F + contiene la DF: R 1 ∩ R 2 → ( R 2 - R 1 )

9. Descomposición binaria Ejemplo Sea R = ABC y F = { A → B } . Pregunta: La descomposición de R en AB y AC es SPI ? Resp: Sí . AB ∩ A C = A , AB - A C = B , y A → B está en F + .

10. Descomposición binaria Ejemplo No todas las descomposiciones son sin pérdida, dado que existen proyecciones cuya reunión no dan exactamente la relación original. Ejemplo: N_Empleado Funcion N_Proyecto Lopez diseñador Nueva España Lopez programador Emprendedor Lopez diseñador Emprendedor Perez diseñador Emprendedor Se puede descomponer en dos tablas: N_Empleado Funcion Lopez diseñador Lopez programador Perez diseñador Funcion N_Proyecto diseñador Nueva España programador Emprendedor diseñador Emprendedor

11. Descomposición binaria Ejemplo Sin embargo, cuando se reunen las dos tablas, se obtienen tuplas adicionales que no estaban en la original. Estas tuplas se llaman espúreas creadas por los procesos de proyección y reunión. Ya que sin la tabla original, no hay forma de identificar cuáles tuplas son genuinas y cuáles espúreas, se puede perder información (aún cuando se tienen más tuplas) si se sustituyen las proyecciones para la relación original: N_Empleado Funcion N_Proyecto Lopez diseñador Nueva España Lopez programador Emprendedor Lopez diseñador Emprendedor Perez diseñador Nueva España Perez diseñador Emprendedor

12. Algoritmo del Tableau Esquema General 2 Sin pérdida de información Introducción Descomposición binaria Algoritmo del Tableau

13. Algoritmo del Tableau Definición de Tableau Dado R = ( A 1 , . . . , A n ), un tableau T para una descomposición ρ = ( R 1 ,... , R k ) de R se define de la siguiente f o r ma: T tiene n columnas, una para cada atributo de R T tiene k filas, una para cada esquema de ρ Dadas la fila i y la columna j (esquema R i y atributo A j ), el contenido del tableau será: a j si A j ∈ R i a(columna) o b ij si A j ∈ / R i b( fila,columna ) Los a j se denominan símbolos distinguidos, y los b ij no distinguidos.

14. Introducción Sin pérdida de información Preservación de Dependencias Funcionales Bi b lio gr afía Algoritmo del Tableau Algoritmo del Tableau INPUT: Un esquema de relación R, un conjunto de dependencias funcionales F , y una descomposición ρ . OUTPUT: Una decisión de si ρ es SPI. Construir el Tableau T mientras haya cambios sobre T para cada df X → Y ∈ F buscar filas que coincidan en todos los símbolos de X Si se encontrasen dos filas, igualar los simbolos pa r a los at r i b utos de Y . Cuando se igualan 2 símbolos, si alguno de ellos es a j , asignarle al otro a j . Si ellos son b ij y b lj , asignarle a ambos b ij o b lj . Si hay una fila con todos símbolos distinguidos, retornar Sí end (mientras) Retornar No

15. Verificación SPI - Ejercicio 1 Sea R = ABCDE, F = { A → B , D → C } . Decidir si la descomposición ρ = { AB C , CD E , ADE } es SPI.

16. Sin pérdida de información Verificación SPI - Ejercicio 1 - Tableau Inicial R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 b 32 b 33 a 4 a 5

17. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 1 - Tableau Intermedio R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } A → B A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 b 32 b 33 a 4 a 5

18. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 1 - Tableau Intermedio R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } A → B A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 a 2 b 33 a 4 a 5

19. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 1 - Tableau Intermedio R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } D → C A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 a 2 b 33 a 4 a 5

20. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 1 - Tableau Final R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } D → C A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 a 2 a 3 a 4 a 5

21. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 1 - Tableau Final R = ABCDE, F = { A → B , D → C } , ρ = { ABC , CDE , ADE } A B C D E ABC a 1 a 2 a 3 b 14 b 15 CDE b 21 b 22 a 3 a 4 a 5 ADE a 1 a 2 a 3 a 4 a 5 Como hay una fila con todos símbolos distinguidos, ρ es SPI.

22. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 Sea R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } . Decidir si la descomposición ρ = { AB D , DE F , FG C , CH I } es SPI.

23. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Inicial R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF b 21 b 22 b 23 a 4 a 5 a 6 b 27 b 28 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

24. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } D → H A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF b 21 b 22 b 23 a 4 a 5 a 6 b 27 b 28 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

25. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } D → H A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF b 21 b 22 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

26. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } H → AD A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF b 21 b 22 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

27. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } H → AD A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF a 1 b 22 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

28. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } A → B A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF a 1 b 22 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

29. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Intermedio R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } A → B A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF a 1 a 2 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9

30. Sin pérdida de información Algoritmo del Tableau Verificación SPI - Ejercicio 2 - Tableau Final R = ABCDEFGHI, F = { A → B , CD → F , H → A D , I → C , D → H } , ρ = { AB D , DE F , FG C , CH I } A B C D E F G H I ABD a 1 a 2 b 13 a 4 b 15 b 16 b 17 b 18 b 19 DEF a 1 a 2 b 23 a 4 a 5 a 6 b 27 b 18 b 29 FGC b 31 b 32 a 3 b 34 b 35 a 6 a 7 b 38 b 39 CHI b 41 b 42 a 3 b 44 b 45 b 46 b 47 a 8 a 9 Como no hay ninguna fila con todos símbolos distinguidos, y aunque sigamos iterando nuevamente por todas las dependencias, ninguna alterará el tableau, ρ NO es SPI.

31. Preservación de Dependencias Funcionales Esquema General Introducción Sin pérdida de información 3 Preservación de Dependencias Funcionales

32. Introducción Sin pérdida de información Preservación de Dependencias Funcionales Bi b lio gr afía Introducción Esquema General 3 Preservación de Dependencias Funcionales Introducción Ejercitación

33. Introducción Preservación de Dependencias Funcionales Dados un esquema de relación R, una descomposición ρ = ( R 1 , . . . , R k ), y un conjunto F de dependencias funcionales. π z ( F ) : proyección de F sobre un conjunto de atributos Z Conjunto de dependencias X → Y en F + tal que XY ⊆ Z Testeo (orden exponencial) + S k i = 1 i La descomposición ρ prese r v a F si F = ( π R ( F )) + Es decir, la descomposición ρ preserva el conjunto de dependencias F si la unión de todas las dependencias en π R i ( F ) implica lógicamente a todas las dependencias en F

34. Preservación de Dependencias Funcionales Introducción Testeo Polinomial de Preservación de Dependencias Funcionales Dados un esquema de relación R, una descomposición ρ = ( R 1 , . . . , R k ), y un conjunto F de dependencias funcionales. P a r a toda dependencia funcional X → Y ∈ F : V e r ificar que se prese r v a X → Y : Z = X while Z cambia for i = 1 to k do /* clausura con respecto a F */ Z = Z ∪ (( Z ∩ R i ) + ∩ R i ) Si Y ¢ Z retornar No Retornar Sí

35. Preservación de Dependencias Funcionales Ejercitación Esquema General 3 Preservación de Dependencias Funcionales Introducción Ejercitación

36. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Ejercicio Sean R = ABCDE y F = { AB → C , A → D , D → E , E → C } . Decidir si la descomposición ρ = { A D , D E , EC B } es sin pérdida de dependencias funcionales (SPDF).

37. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , D E , EC B } Estrategia de Resolución:

38. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , D E , EC B } Estrategia de Resolución: Las dependencias A → D , D → E , E → C se prese r v an trivialmente (por qué?), y no es necesario aplicarles el algoritmo. Le aplicaremos el algoritmo a la dependencia AB → C para ver si se preserva.

39. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , D E , EC B } Queremos verificar que se preserva AB → C V e r ificar que se prese r v a X → Y : Z = X while Z cambia for i = 1 to k do Z = Z ∪ (( Z ∩ R i ) + ∩ R i ) Si Y ¢ Z retornar No Z = AB

40. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , DE , EC B } Queremos verificar que se preserva AB → C V e r ificar que se prese r v a X → Y : Z = X while Z cambia for i = 1 to k do Z = Z ∪ (( Z ∩ R i ) + ∩ R i ) Si Y ¢ Z retornar No Z = Z ∪ (( Z ∩ R 1 ) + ∩ R 1 ) = { A , B }∪ (( { A , B }∩{ A , D } ) + ∩{ A , D } ) = { A , B } ∪ (( A ) + ∩ { A , D } ) = { A , B } ∪ ( { A , D , E , C } ∩ { A , D } ) = { A , B , D } C no está incluido en Z; seguimos...

41. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , DE , EC B } Queremos verificar que se preserva AB → C V e r ificar que se prese r v a X → Y : Z = X while Z cambia for i = 1 to k do Z = Z ∪ (( Z ∩ R i ) + ∩ R i ) Si Y ¢ Z retornar No Z = Z ∪ (( Z ∩ R 2 ) + ∩ R 2 ) = { A , B , D } ∪ (( { A , B , D } ∩{ D , E } ) + ∩{ D , E } ) = { A , B , D } ∪ (( D ) + ∩ { D , E } ) = { A , B , D } ∪ ( { D , E , C } ∩ { D , E } ) = { A , B , D , E } C no está incluido en Z; seguimos...

42. Preservación de Dependencias Funcionales Ejercitación Preservación de Dependencias Funcionales: Resolución Ejercicio R = ABCDE F = { AB → C , A → D , D → E , E → C } ρ = { A D , DE , EC B } Queremos verificar que se preserva AB → C V e r ificar que se prese r v a X → Y : Z = X while Z cambia for i = 1 to k do Z = Z ∪ (( Z ∩ R i ) + ∩ R i ) Si Y ¢ Z retornar No Z = Z ∪ (( Z ∩ R 3 ) + ∩ R 3 ) = { A , B , D , E } ∪ (( { A , B , D , E } ∩ { E , C , B } ) + ∩ { E , C , B } ) = { A , B , D , E } ∪ (( E B ) + ∩ { E , C , B } ) = { A , B , D , E } ∪ ( { E , B , C } ∩ { E , C , B } ) = { A , B , D , E , C } Ahora sí C está incluido en Z: la dependencia AB → C se preserva