Aspectos de Diseño de BDs - Facultad de Cienciashp.fciencias.unam.mx/~alg/bd/df.pdf ·...

Aspectos de Diseno de BDs

Dra. Amparo Lopez Gaona

Posgrado en Ciencia e Ingenierıa de la ComputacionFac. Ciencias, UNAM

Marzo 2012

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 1

/ 14

Motivacion

nombre suc delegacion activo nombre cte nPrestamo importe

Centro Cuauhtemoc 1,800 M Santos P-17 200,000Copilco Coyoacan 420 M Gomez P-23 400,000Viveros Coyoacan 340 M Lopez P-15 300,000Centro Cuauhtemoc 1,800 M Toledo P-14 300,000Eugenia Benito Juarez 80 M Santos P-93 100,000Zapata Benito Juarez 1,600 M Abril P-11 180,000

San Angel Alvaro Obregon 60 M Vazquez P-29 240,000Tlalpan Tlalpan 740 M Lopez P-16 260,000Centro Cuauhtemoc 1,800 M Gonzalez P-23 400,000Viveros Coyoacan 340 M Rodrıguez P-25 500,000Las Fuentes Tlalpan 1,420 M Amor P-10 440,000

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 2

/ 14

Problemas con un diseno incorrecto

Redundancia de informacion.Problemas de actualizacion:

Agregar el prestamo P-31 realizado en la sucursal San Angel al clienteMendoza por $300,000.{San Angel, Alvaro Obregon, 60 000 000, Mendoza, P-31,300 000}Cambiar la direccion de una sucursal

Incapacidad para representar cierta informacion.

¿Como dar de alta una nueva sucursal?¿Que sucede si no hay prestamos?

Las dependencias funcionales ayudan a especificar formalmente cuando undiseno es correcto.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 3

/ 14

Dependencias Funcionales

Una DF, denotada por X → Y , entre dos conjuntos de atributos X y Y deuna relacion R es una restriccion sobre las tuplas de R.La restriccion establece que X determina funcionalmente a Y en unesquema de relacion si y solo si, cuando dos tuplas t y u de R coinciden ensu valor en X, ellas necesariamente coinciden sus valores en Y.

������������������������

������������������������

������������������������

������������������������

����������������

����������������

����������������

����������������

��������������������������������

��������������������������������

��������������������������������

��������������������������������

X’s

t

u

Si t y u coincidenaqui,

Y’s

coincidenaquí

entonces

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 4

/ 14

Ejemplo

En la relacion:prestamo (nombre sucursal, num prestamo, nombre cliente, importe)

Se espera quenum prestamo → importenum prestamo → nombre sucursal

No se espera quenum prestamo → nombre clienteLas DFs se utilizan para:

Especificar restricciones sobre el conjunto de relaciones.

Examinar las relaciones y determinar si son legales bajo un conjuntode DFs dado.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 5

/ 14

Ejemplo

En la relacion:prestamo (nombre sucursal, num prestamo, nombre cliente, importe)

Se espera quenum prestamo → importenum prestamo → nombre sucursalNo se espera quenum prestamo → nombre cliente

Las DFs se utilizan para:

Especificar restricciones sobre el conjunto de relaciones.

Examinar las relaciones y determinar si son legales bajo un conjuntode DFs dado.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 5

/ 14

Ejemplo

En la relacion:prestamo (nombre sucursal, num prestamo, nombre cliente, importe)

Se espera quenum prestamo → importenum prestamo → nombre sucursalNo se espera quenum prestamo → nombre clienteLas DFs se utilizan para:

Especificar restricciones sobre el conjunto de relaciones.

Examinar las relaciones y determinar si son legales bajo un conjuntode DFs dado.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 5

/ 14

Definiciones

Una extension legal es aquella que satisface las restricciones de DFs.

Una DF A1, A2, ...,An → B1, B2, ...,Bm es trivial si los atributos dellado derecho son un subconjunto de los atributos del lado izquierdo.

Si X → Y en R, esto no implica que Y → XA B C D

a1 b1 c1 d1

a1 b2 c1 d2

a2 b2 c2 d2

a2 b3 c2 d3

a3 b3 c2 d4

Una DF es una propiedad de la semantica de los atributos que sedebe cumplir para la extension una relacion.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 6

/ 14

Definiciones

Una extension legal es aquella que satisface las restricciones de DFs.

Una DF A1, A2, ...,An → B1, B2, ...,Bm es trivial si los atributos dellado derecho son un subconjunto de los atributos del lado izquierdo.

Si X → Y en R, esto no implica que Y → XA B C D

a1 b1 c1 d1

a1 b2 c1 d2

a2 b2 c2 d2

a2 b3 c2 d3

a3 b3 c2 d4

Una DF es una propiedad de la semantica de los atributos que sedebe cumplir para la extension una relacion.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 6

/ 14

Definiciones

Una extension legal es aquella que satisface las restricciones de DFs.

Una DF A1, A2, ...,An → B1, B2, ...,Bm es trivial si los atributos dellado derecho son un subconjunto de los atributos del lado izquierdo.

Si X → Y en R, esto no implica que Y → XA B C D

a1 b1 c1 d1

a1 b2 c1 d2

a2 b2 c2 d2

a2 b3 c2 d3

a3 b3 c2 d4

Una DF es una propiedad de la semantica de los atributos que sedebe cumplir para la extension una relacion.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 6

/ 14

Definiciones

Una extension legal es aquella que satisface las restricciones de DFs.

Una DF A1, A2, ...,An → B1, B2, ...,Bm es trivial si los atributos dellado derecho son un subconjunto de los atributos del lado izquierdo.

Si X → Y en R, esto no implica que Y → XA B C D

a1 b1 c1 d1

a1 b2 c1 d2

a2 b2 c2 d2

a2 b3 c2 d3

a3 b3 c2 d4

Una DF es una propiedad de la semantica de los atributos que sedebe cumplir para la extension una relacion.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 6

/ 14

Llaves de las relaciones

Una llave puede definirse como un conjunto de atributos {A1, A2, ...,An}tales que:

Determinan funcionalmente cualquier otro atributo de la relacion. Esdecir, es imposible para dos tuplas distintas de R coincidir en todos{A1, A2, ...,An}Ningun subconjunto propio de {A1, A2, ...,An} determinafuncionalmente los otros atributos de R, es decir, debe ser mınimo.

Una superllave es un conjunto de atributos que contienen una llave.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 7

/ 14

Llaves de las relaciones

Una llave puede definirse como un conjunto de atributos {A1, A2, ...,An}tales que:

Determinan funcionalmente cualquier otro atributo de la relacion. Esdecir, es imposible para dos tuplas distintas de R coincidir en todos{A1, A2, ...,An}

Ningun subconjunto propio de {A1, A2, ...,An} determinafuncionalmente los otros atributos de R, es decir, debe ser mınimo.

Una superllave es un conjunto de atributos que contienen una llave.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 7

/ 14

Llaves de las relaciones

Una llave puede definirse como un conjunto de atributos {A1, A2, ...,An}tales que:

Determinan funcionalmente cualquier otro atributo de la relacion. Esdecir, es imposible para dos tuplas distintas de R coincidir en todos{A1, A2, ...,An}Ningun subconjunto propio de {A1, A2, ...,An} determinafuncionalmente los otros atributos de R, es decir, debe ser mınimo.

Una superllave es un conjunto de atributos que contienen una llave.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 7

/ 14

Llaves de las relaciones

Una llave puede definirse como un conjunto de atributos {A1, A2, ...,An}tales que:

Determinan funcionalmente cualquier otro atributo de la relacion. Esdecir, es imposible para dos tuplas distintas de R coincidir en todos{A1, A2, ...,An}Ningun subconjunto propio de {A1, A2, ...,An} determinafuncionalmente los otros atributos de R, es decir, debe ser mınimo.

Una superllave es un conjunto de atributos que contienen una llave.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 7

/ 14

Reglas de Inferencia para DFs

Dado un conjunto F de DFs, existen otras DFs que pueden inferirse oimplicarse logicamente de F .

Ejemplo: R = (A, B, C , G , H, I )y F = {A→ B,

A→ C ,CG → H,CG → I ,B → H}

La dependencia funcional A→ H se implica logicamente.

Sean t1, t2 son tuplas tales que t1[A] = t2[A]

Por la primera dependencia, t1[B] = t2[B],

Por la ultima dependencia, t1[H] = t2[H],

por tanto ∀t1, t2 tales que t1[A] = t2[A] entonces t1[H] = t2[H] quees la definicion de A→ H.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 8

/ 14

Reglas de Inferencia para DFs

Dado un conjunto F de DFs, existen otras DFs que pueden inferirse oimplicarse logicamente de F .Ejemplo: R = (A, B, C , G , H, I )y F = {A→ B,

A→ C ,CG → H,CG → I ,B → H}

La dependencia funcional A→ H se implica logicamente.

Sean t1, t2 son tuplas tales que t1[A] = t2[A]

Por la primera dependencia, t1[B] = t2[B],

Por la ultima dependencia, t1[H] = t2[H],

por tanto ∀t1, t2 tales que t1[A] = t2[A] entonces t1[H] = t2[H] quees la definicion de A→ H.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 8

/ 14

Reglas de Inferencia para DFs

Dado un conjunto F de DFs, existen otras DFs que pueden inferirse oimplicarse logicamente de F .Ejemplo: R = (A, B, C , G , H, I )y F = {A→ B,

A→ C ,CG → H,CG → I ,B → H}

La dependencia funcional A→ H se implica logicamente.

Sean t1, t2 son tuplas tales que t1[A] = t2[A]

Por la primera dependencia, t1[B] = t2[B],

Por la ultima dependencia, t1[H] = t2[H],

por tanto ∀t1, t2 tales que t1[A] = t2[A] entonces t1[H] = t2[H] quees la definicion de A→ H.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 8

/ 14

Reglas de Inferencia para DFs

Dado un conjunto F de DFs, existen otras DFs que pueden inferirse oimplicarse logicamente de F .Ejemplo: R = (A, B, C , G , H, I )y F = {A→ B,

A→ C ,CG → H,CG → I ,B → H}

La dependencia funcional A→ H se implica logicamente.

Sean t1, t2 son tuplas tales que t1[A] = t2[A]

Por la primera dependencia, t1[B] = t2[B],

Por la ultima dependencia, t1[H] = t2[H],

por tanto ∀t1, t2 tales que t1[A] = t2[A] entonces t1[H] = t2[H] quees la definicion de A→ H.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 8

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .

X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .

Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Cerradura de F

F + = conjunto DFs que son logicamente implicadas o inferidas por F .X → Y es inferida de un conjunto F de DF sobre R (F |= X → Y ), si entodo estado r de la relacion se satisfacen todas las dependencias en F ytambien X → Y .Reglas de inferencia de Armstrong’s:

R1.Regla de la reflexividad. Si X ⊇ Y , entonces X → Y .

R2. Regla del aumento. { X → Y } |= XZ → YZ .

R3. Regla de la transitividad. { X → Y , Y → Z} |= X → Z .

Aunque completo, para simplificar el calculo de F + se tienen reglasadicionales:

R4. Regla de la descomposicion. {X → YZ} |= X → Y y que X → Z .

R5. Regla de la union. {X → Y , X → Z} |= X → YZ .

R6. Regla de la pseudo-transitividad.{X → Y , WY → Z} |= WX → Z .

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 9

/ 14

Prueba de las reglas

Prueba de R4.

1 X → YZ (Dado).2 YZ → Y Usando R1 y sabiendo que YZ ⊇ Y .3 X → Y Usando R3 sobre 1 y 2.

Prueba de R5.

1 X → Y (Dado).2 X → Z (Dado).3 X → XY Usando R2 sobre 1; notar que XX = X .4 XY → YZ Usando R2 sobre 2 aumentando con Y.5 X → YZ Usando R3 sobre 3 y 4.

Prueba de R6.1 X → Y (Dado).2 WY → Z (Dado).3 WX →WY R2 sobre 1 aumentando con W.4 WX → Z R3 sobre 3 y 2.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 10

/ 14

Prueba de las reglas

Prueba de R4.

1 X → YZ (Dado).2 YZ → Y Usando R1 y sabiendo que YZ ⊇ Y .3 X → Y Usando R3 sobre 1 y 2.

Prueba de R5.

1 X → Y (Dado).2 X → Z (Dado).3 X → XY Usando R2 sobre 1; notar que XX = X .4 XY → YZ Usando R2 sobre 2 aumentando con Y.5 X → YZ Usando R3 sobre 3 y 4.

Prueba de R6.1 X → Y (Dado).2 WY → Z (Dado).3 WX →WY R2 sobre 1 aumentando con W.4 WX → Z R3 sobre 3 y 2.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 10

/ 14

Prueba de las reglas

Prueba de R4.

1 X → YZ (Dado).2 YZ → Y Usando R1 y sabiendo que YZ ⊇ Y .3 X → Y Usando R3 sobre 1 y 2.

Prueba de R5.

1 X → Y (Dado).2 X → Z (Dado).3 X → XY Usando R2 sobre 1; notar que XX = X .4 XY → YZ Usando R2 sobre 2 aumentando con Y.5 X → YZ Usando R3 sobre 3 y 4.

Prueba de R6.1 X → Y (Dado).2 WY → Z (Dado).3 WX →WY R2 sobre 1 aumentando con W.4 WX → Z R3 sobre 3 y 2.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 10

/ 14

Prueba de las reglas

Prueba de R4.

1 X → YZ (Dado).2 YZ → Y Usando R1 y sabiendo que YZ ⊇ Y .3 X → Y Usando R3 sobre 1 y 2.

Prueba de R5.

1 X → Y (Dado).2 X → Z (Dado).3 X → XY Usando R2 sobre 1; notar que XX = X .4 XY → YZ Usando R2 sobre 2 aumentando con Y.5 X → YZ Usando R3 sobre 3 y 4.

Prueba de R6.

1 X → Y (Dado).2 WY → Z (Dado).3 WX →WY R2 sobre 1 aumentando con W.4 WX → Z R3 sobre 3 y 2.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 10

/ 14

Prueba de las reglas

Prueba de R4.

1 X → YZ (Dado).2 YZ → Y Usando R1 y sabiendo que YZ ⊇ Y .3 X → Y Usando R3 sobre 1 y 2.

Prueba de R5.

1 X → Y (Dado).2 X → Z (Dado).3 X → XY Usando R2 sobre 1; notar que XX = X .4 XY → YZ Usando R2 sobre 2 aumentando con Y.5 X → YZ Usando R3 sobre 3 y 4.

Prueba de R6.1 X → Y (Dado).2 WY → Z (Dado).3 WX →WY R2 sobre 1 aumentando con W.4 WX → Z R3 sobre 3 y 2.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 10

/ 14

Ejemplo

Sean R = (A, B, C, G, H, I) yF = { A → B, A → C, CG → H, CG → I, B → H }Algunos miembros de F + serıan:

A → H,AG → I,CG → HI,

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 11

/ 14

Ejemplo

Sean R = (A, B, C, G, H, I) yF = { A → B, A → C, CG → H, CG → I, B → H }Algunos miembros de F + serıan:A → H,

AG → I,CG → HI,

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 11

/ 14

Ejemplo

Sean R = (A, B, C, G, H, I) yF = { A → B, A → C, CG → H, CG → I, B → H }Algunos miembros de F + serıan:A → H,AG → I,

CG → HI,

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 11

/ 14

Ejemplo

Sean R = (A, B, C, G, H, I) yF = { A → B, A → C, CG → H, CG → I, B → H }Algunos miembros de F + serıan:A → H,AG → I,CG → HI,

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 11

/ 14

Cerradura de conjuntos de atributos

Para crear las DF’s de un esquema, el disenador:

1 Especifica, a partir de la semantica de los atributos de R, el conjuntoF de DFs.

2 Usando las reglas de inferencia de Armstrong obtiene otras DFs.

Para obtener todas las DFs de manera sistematica:

1 Determinar el conjunto de atributos X del lado izquierdo de algunaDF en F.

2 Determinar el conjunto X + de todos los atributos que sondependientes de X.Dado {A1, A2, ...,An} un conjunto de atributos y F un conjunto deDFs, la cerradura del conjunto de atributos ( {A1, A2, ...,An}+ )bajo las dependencias en F es el conjunto de atributos B tales quecada relacion que satisface todas las dependencias en F tambiensatisface A1, A2, ...An → B.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 12

/ 14

Cerradura de conjuntos de atributos

Para crear las DF’s de un esquema, el disenador:

1 Especifica, a partir de la semantica de los atributos de R, el conjuntoF de DFs.

2 Usando las reglas de inferencia de Armstrong obtiene otras DFs.

Para obtener todas las DFs de manera sistematica:

1 Determinar el conjunto de atributos X del lado izquierdo de algunaDF en F.

2 Determinar el conjunto X + de todos los atributos que sondependientes de X.Dado {A1, A2, ...,An} un conjunto de atributos y F un conjunto deDFs, la cerradura del conjunto de atributos ( {A1, A2, ...,An}+ )bajo las dependencias en F es el conjunto de atributos B tales quecada relacion que satisface todas las dependencias en F tambiensatisface A1, A2, ...An → B.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 12

/ 14

Cerradura de conjuntos de atributos

Para crear las DF’s de un esquema, el disenador:

1 Especifica, a partir de la semantica de los atributos de R, el conjuntoF de DFs.

2 Usando las reglas de inferencia de Armstrong obtiene otras DFs.

Para obtener todas las DFs de manera sistematica:

1 Determinar el conjunto de atributos X del lado izquierdo de algunaDF en F.

2 Determinar el conjunto X + de todos los atributos que sondependientes de X.

Dado {A1, A2, ...,An} un conjunto de atributos y F un conjunto deDFs, la cerradura del conjunto de atributos ( {A1, A2, ...,An}+ )bajo las dependencias en F es el conjunto de atributos B tales quecada relacion que satisface todas las dependencias en F tambiensatisface A1, A2, ...An → B.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 12

/ 14

Cerradura de conjuntos de atributos

Para crear las DF’s de un esquema, el disenador:

1 Especifica, a partir de la semantica de los atributos de R, el conjuntoF de DFs.

2 Usando las reglas de inferencia de Armstrong obtiene otras DFs.

Para obtener todas las DFs de manera sistematica:

1 Determinar el conjunto de atributos X del lado izquierdo de algunaDF en F.

2 Determinar el conjunto X + de todos los atributos que sondependientes de X.Dado {A1, A2, ...,An} un conjunto de atributos y F un conjunto deDFs, la cerradura del conjunto de atributos ( {A1, A2, ...,An}+ )bajo las dependencias en F es el conjunto de atributos B tales quecada relacion que satisface todas las dependencias en F tambiensatisface A1, A2, ...An → B.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 12

/ 14

Algoritmo para calcular X+ bajo F

X+ := X;Repetir

oldX+ := X+;Para cada Y → Z en F hacer

si Y ⊆ X+ entonces X+ := X+∪ Z;hasta que oldX+ = X+;

Ejemplos:1 Sean R = (A, B, C, G, H, I) y F las dependencias definidas antes

como { A → B, A → C, CG → H, CG → I, B → H }, se tiene que(AG )+ = {ABCGHI}

2 Sea una relacion con atributos A, B, C , D, E , F y las DF’s{AB → C , BC → AD, D → E , CF → B}. Encontrar {AB}+.Resultado = {A,B,C,D,E} lo que implica que AB → ABCDE.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 13

/ 14

Algoritmo para calcular X+ bajo F

X+ := X;Repetir

oldX+ := X+;Para cada Y → Z en F hacer

si Y ⊆ X+ entonces X+ := X+∪ Z;hasta que oldX+ = X+;

Ejemplos:1 Sean R = (A, B, C, G, H, I) y F las dependencias definidas antes

como { A → B, A → C, CG → H, CG → I, B → H }, se tiene que(AG )+ =

{ABCGHI}2 Sea una relacion con atributos A, B, C , D, E , F y las DF’s{AB → C , BC → AD, D → E , CF → B}. Encontrar {AB}+.Resultado = {A,B,C,D,E} lo que implica que AB → ABCDE.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 13

/ 14

Algoritmo para calcular X+ bajo F

X+ := X;Repetir

oldX+ := X+;Para cada Y → Z en F hacer

si Y ⊆ X+ entonces X+ := X+∪ Z;hasta que oldX+ = X+;

Ejemplos:1 Sean R = (A, B, C, G, H, I) y F las dependencias definidas antes

como { A → B, A → C, CG → H, CG → I, B → H }, se tiene que(AG )+ = {ABCGHI}

2 Sea una relacion con atributos A, B, C , D, E , F y las DF’s{AB → C , BC → AD, D → E , CF → B}. Encontrar {AB}+.Resultado = {A,B,C,D,E} lo que implica que AB → ABCDE.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 13

/ 14

Algoritmo para calcular X+ bajo F

X+ := X;Repetir

oldX+ := X+;Para cada Y → Z en F hacer

si Y ⊆ X+ entonces X+ := X+∪ Z;hasta que oldX+ = X+;

Ejemplos:1 Sean R = (A, B, C, G, H, I) y F las dependencias definidas antes

como { A → B, A → C, CG → H, CG → I, B → H }, se tiene que(AG )+ = {ABCGHI}

2 Sea una relacion con atributos A, B, C , D, E , F y las DF’s{AB → C , BC → AD, D → E , CF → B}. Encontrar {AB}+.

Resultado = {A,B,C,D,E} lo que implica que AB → ABCDE.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 13

/ 14

Algoritmo para calcular X+ bajo F

X+ := X;Repetir

oldX+ := X+;Para cada Y → Z en F hacer

si Y ⊆ X+ entonces X+ := X+∪ Z;hasta que oldX+ = X+;

Ejemplos:1 Sean R = (A, B, C, G, H, I) y F las dependencias definidas antes

como { A → B, A → C, CG → H, CG → I, B → H }, se tiene que(AG )+ = {ABCGHI}

2 Sea una relacion con atributos A, B, C , D, E , F y las DF’s{AB → C , BC → AD, D → E , CF → B}. Encontrar {AB}+.Resultado = {A,B,C,D,E} lo que implica que AB → ABCDE.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 13

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.

Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ =

{A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E}

como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A.

Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ =

{D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E}

como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14

Dependencias deducidas

Para probar si una dependencia funcional A1, A2, ...,An → B, se deduce deun conjunto de dependencias F. Se calcula {A1, A2, ...,An}+ si Besta ahı entonces la DF si es deducida del conjunto F en caso contrario noes deducida de F.Ejercicios:

Probar que AB → D.Se empieza por calcular {A, B}+ = {A, B, C , D, E} como D ∈ {A,B}+ entonces esta si es deducida.

Probar que D → A. Se tiene que D+ = {D, E} como A no esta enD+ entonces la DF no se deduce de F.

Dra. Amparo Lopez Gaona () Aspectos de Diseno de BDsPosgrado en Ciencia e Ingenierıa de la Computacion Fac. Ciencias, UNAMMarzo 2012 14

/ 14