Producto Cartesiano

Dadas dos relaciones:

- R de grado n, cardinalidad x

- S de grado m, cardinalidad y

Grado: Es el número de atributos.

Cardinalidad: Es el número de tuplas.

El producto cartesiano se define como:

(RXS)={t[A₁,…,An,B1,…,Bm]|t[A1,…,An] Є R^t[B1,…,Bm] Є S}

El resultado de RX2 es una relación de grado (m+n) y consiste de todas las tuplas (x*y) – tuplas, en donde cada tupla es la concatenación de una tupla de R con cada una de las tuplas de S.

Ejemplo:

Alumno

noBoleta, nombre, carrera, idEscuela

200566119 Rocio Ing. S.C. 05

200472266 Carlos Ing Civil 04

200722633 Raul Lic. Inf. 03

Grado=4

Cardinalidad=3

Escuela

idEscuela, nombre

05 ESCOM

04 ESIA

03 UPIICSA

Grado=2

Cardinalidad=3

Alumno X Escuela

noBoleta, nombre, carrera, idEscuela idEscuela, nombre

200566119 Rocio Ing. S.C. 05 05 ESCOM

200566119 Rocio Ing. S.C. 05 04 ESIA

200566119 Rocio Ing. S.C. 05 03 UPIICSA

200472266 Carlos Ing Civil 04 05 ESCOM

200472266 Carlos Ing Civil 04 04 ESIA

200472266 Carlos Ing Civil 04 03 UPIICSA

200722633 Raul Lic. Inf. 03 05 ESCOM

200722633 Raul Lic. Inf. 03 04 ESIA

200722633 Raul Lic. Inf. 03 03 UPIICSA

m + n = 4 + 2 = (x * y) – 3 = 6

Reunión (|X|)

Tipos de reunión

a) Ѳ-reunión

- La fórmula F usa el operador Ѳ (>,>=,<,<=, ≠)

b) Equi-reunión

- La fórmula F contiene el operador de igualdad (=)

R|X|_R.A=S.BS

c) Reunión Natural

- Equi-reunión de dos relaciones R y S sobre un atributo (o atributos) comunes a R y S y proyectando solo una copia de estos atributos.

R|X|S=π_RUSσ_F(RxS)

Forma General (Reunión)

R|X|_F(R.Ai,S.Bj)S={t[A₁,…,A_n,B₁,…,B_m]|t[A₁,…,A_n] Є R^t[B₁,…,B_m] Є S ^ F(R.A_i, S.B_j) sea verdadero }

Donde:

R, S son relaciones

t es una variable tupla

F(R.Ai, S.Bj) es una fórmula definida como una selección.

- Una derivación del Producto Cartesiano.

R|X|_FS=σ_F(RxS)

Ejemplo:

Empleado

noEmp nombre noDepto

1 A 1

2 B 3

3 C 2

4 D 3

Depto

noDepto nombre

1 A1

2 A2

3 A3

Empleado |X|_{Empleado.noDepto>Depto.noDepto}Depto

Es una Ѳ-reunión.

Efectuamos el producto cartesiano y aplicamos la condición pedida, quedando:

noEmp nombre noDepto noDepto nombre

2 B 3 1 A1

2 B 3 2 A2

3 C 2 1 A1

4 D 3 1 A1

4 D 3 2 A2

Empleado |X|_{Empleado.noDepto=Depto.noDepto}Depto

Es una equi-reunión.

Efectuamos el producto cartesiano y aplicamos la condición pedida, quedando:

noEmp nombre noDepto noDepto nombre

1 A 1 1 A1

2 B 3 3 A3

3 C 2 2 A2

4 D 3 3 A3

En la reunión natural se elimina uno de los atributos repetidos de la equi-reunión (solo se puede usar reunión natural en una equi-reunión).

Quedando:

noEmp nombre noDepto nombre

1 A 1 A1

2 B 3 A3

3 C 2 A2

4 D 3 A3

Implementación de la operación de Reunión (|x|)

- Es la operación que consume más tiempo de procesamiento.

- Se aplica la reunión de la forma:

R|x|_A=BS

Donde:

A y B son atributos con dominio compatible de R y S respectivamente.

Ejemplo:

Empleado|x|_{noDepto=noDepto}Depto

Depto|x|_{noEmpGerente=noEmpleado}Empleado

Aunque noEmpGerente y noEmpleado tengan diferente nombre, siguen siendo el mismo dato por lo que la igualdad se sigue cumpliendo.

Métodos para implementar la |x|

a) Enfoque ciclo anidado (interior-exterior) por fuerza bruta.

- Para cada registro t de R (ciclo exterior) obtener todos los registros de s de S (ciclo interior).

- Verificar si los dos registros satisfacen la condición de reunión t[A]=s[B].

Lee un registro R y lo compara con cada uno de los registros de S hasta que cumpla la condición.

b) Empleo de una estructura de acceso para obtener registros coincidentes.

- Si existe un índice (clave de dispersión) para cada uno de los atributos de reunión, leer todos los registros t de R, uno por uno y usar la estructura de acceso para obtener directamente todos los registros coincidentes s de S (los que satisfacen s[B]=t [A]).

Lee todos los registros R y después toma uno a uno los registros R y busca en el índice la ubicación de los registros S que cumplen la condición.

c) Reunión por ordenamiento-combinación.

- Si los registros de R y S se encuentran ordenados físicamente según el valor de los atributos de reunión A y B respectivamente.

- Se examinan ambos archivos en orden según los atributos de reunión buscando registros que tienen los mismos valores A y B.

- Se examinan los registros de cada archivo una sola vez para compararlos con los del otro.

-Se lleva a cabo la combinación de las tuplas donde el atributo de reunión coincida.

Se busca de forma paralela en R y S combinando las tuplas conforme la condición se cumple.

d) Dispersión-reunión

- Los registros de losa rchivos R como de S se dispersan al mismo archivo (de dispersión) con los atributos de reunión A de R y B de S como claves de dispersión.

- Una sola pasada por el archivo con el menor número de registros (digamos R) dispersa sus registros a las cubetas del archivo de dispersión.

Dispersión

- Se establece como una condición de búsqueda sobre una condición de igualdad sobre un campo (campo de dispersión).

- Se basa en establecer una función h, llamada función de dispersión, se aplica al valor de un campo de dispersión de un archivo y produce la dirección del bloque de disco en el que está almacenado el registro.

Dispersión interna: Se implementa con arreglo de registros.

h(k)=KmodH : el residuo se utiliza como dirección del registro.

Dispersión externa: Se efectúa en archivos de disco.

- El espacio de direcciones es dividido en cubetas. Una cubeta es un bloque de disco o un grupo de bloques continuos.

Enfoque de ciclo anidado

- Importante considerar cual es el archivo que se elija para el ciclo exterior e interior.

Ejemplo:

a) Empleado |X|_{noDepto=noDepto}Depto

b) Depto|X|_{noDepto=noDepto}Empleado

Suponemos que:

Depto	Empleado
rD=50 registros almacenados en bD=10 bloques	rE=5000 registros almacenados en bE=2000 bloques

Se dispone de:

n_B= 6 (bloques de almacenamiento “buffers”) para llevar a cabo la operación de reunión.

Ideal:

- Leer en una sola operación tantos bloques como pueden caber en la memoria dese el archivo cuyos registros se emplean en el ciclo exterior (n_B-1 bloques) y un bloque del ciclo interior.

- Reducir el número total de accesos a bloque.

1. Considerando a Empleado como ciclo exterior. Tenemos que:

- No. total de bloques de archivo exterior = b_E

- No. de veces que se leen (n_B-1 bloques) del archivo exterior = [b_E/(n_B-1)]

- No. total de bloques del archivo interior leídos = b_D*[b_C/(n_B-1)]

Total de accesos a bloque:

Empleado -> ciclo exterior

a) b_E + [b_E/(n_B-1)* b_D] = 6000 accesos a bloque

Depto -> ciclo exterior

b) b_D + [b_D/(n_B-1)* b_E] = 4010 accesos a bloque

Por lo tanto, Depto debe ser el ciclo exterior. Como podemos ver, Depto es también el que tiene menor número de registros, siempre debemos tratar de considerar como ciclo exterior al que tenga menor número de registros.

Ejemplo:

Depto|X|_{noEmpGerente=noEmpleado}Empleado (1.7)

- Suponemos que existen índices secundarios sobre estos atributos.

Atributo	Tabla	Nivel de índice
noEmpleado	Empleado	λnoEmpleado = 4
noEmpGerente	Depto	λnoEmpGerente = 2

- Tenemos dos opciones para implementar el método (estructura de acceso)

a) Leer cada uno de los registros de Empleado y usar el índice sobre el atributo noEmpGerente(Depto) para encontrar un registro coincidente.

No. de accesos a bloques:

b_E + [r_E * (λ_noEmpGerente+1)] = 17000

b) Leer los registros de Depto.

- Usar el índice de noEmpleado para encontrar un registro de empelado coincidente.

No. de accesos a bloque:

B_D + [r_D * (λ_noEmp+1)] = 260

Implementación de la operación de Proyección ()

(Relación)

Ejemplo:

Alumno

noBoleta	Nombre	Carrera	idEsc
200811	PP	ISC	001
200812	LL	LI	002
200813	JL	ISC	001

_{noBoleta,carrera}(Alumno)

noBoleta	Carrera
200811	ISC
200812	LI
200813	ISC

_{noBoleta,nombre}(σ_carrera=ISC(Alumno))

noBoleta	Nombre
200811	PP
200813	JL

_idEsc (Alumno)

idEsc

001

002

Si no se incluye una clave de R en la lista de atributos, es necesario eliminar tuplas repetidas.

- Ordenar el resultado de la operación.

- Eliminar tuplas repetidas.

Usa la dispersión para eliminar duplicados, es decir, al dispersarse cada registro e insertarse a la cubeta del archivo de dispersión, se compara con las que ya están en la cubeta; si es un duplicado no se inserta.

Si incluye una clave de la relación R, el resultado de la operación tendrá el mismo número de tuplas de R, pero solo con los valores de los atributos en cada tupla.