Cierre Unidad III

investigar:

*Algebra relacional   aplicada a bases de datos distribuidas ( definición y ejemplos)

*¿Qué es Parsing?

* heurísticas 
* acceso concurrente 
* Como se crea un arbol de consulta  y ejemplos


Algebra Relacional Aplicada a Bases de datos distribuidas

Algebra Relacional from Blanca Parra Hernandez

La complejidad de las operaciones del álgebra relacional afectan directamente su tiempo de ejecución y establecen algunos principios útiles al procesador de consultas. Esos principios pueden ayudar en

elegir la estrategia de ejecución final. La forma más simple de definir la complejidad es en términos de la cardinalidad de las relaciones independientemente de los detalles de implementación tales como

fragmentación y estructuras de almacenamiento. La Figura 4.3 presenta la complejidad de las operaciones unarias y binarias en el orden creciente de complejidad.

Operación	Complejidad
Selección Proyección (sin eliminación de duplicados)	O(n)
Proyección (con eliminación de duplicados) Agrupación	O(n*log n)
Junta Semijunta División Operadores sobre conjuntos	O(n*log n)
Producto Cartesiano	O(n2)

Figura 4.3. Complejidad de las operaciones del álgebra relacional.

Esta simple mirada a la complejidad de las operaciones sugiere dos principios:

1. Dado que la complejidad es con base en las cardinalidades de las relaciones, las operaciones más selectivas que reducen las cardinalidades deben ser ejecutadas primero.
2. Las operaciones deben ser ordenadas en el orden de complejidad creciente de manera que el producto Cartesiano puede ser evitado o, al menos, ejecutado al final de la estrategia

Como se Crea un arbol de consultas y ejemplos

La transformación de una consulta en el cálculo relacional en un árbol del álgebra relacional se puede hacer como sigue. Primero, se crea una hoja diferente para cada variable de tuplo diferente. En SQL, las hojas están disponibles de forma inmediata en la cláusula FROM. Segundo, el nodo raíz se crea como una operación de proyección involucrando a los atributos resultantes. Estos se encuentran en la cláusula SELECT de una consulta en SQL. Tercero, la calificación (WHERE) de una consulta se traduce a una secuencia apropiada de operaciones relacionales (select, join, union, etc.) yendo de las hojas a la raíz. La secuencia se puede dar directamente por el orden de aparición de los predicados y operadores.

Ejemplo 4.7. La consulta

"Encuentre los nombres de empleados diferentes de "J. Doe" que trabajaron en el proyecto de CAD/CAM por uno o dos años"

se puede expresar en SQL como sigue:

SELECT ENAME

FROM J, E, G

WHERE E.ENO = G.ENO

AND G.JNO = J.JNO

AND ENAME ¹ "J. Doe"

AND JNAME = "CAD/CAM"

AND (DUR = 12 OR DUR = 24)

Se puede mapear de manera directa al árbol del álgebra relacional de la Figura 4.7.

Figura 4.7. Ejemplo de un árbol del álgebra relacional.

Aplicando las reglas de transformación que se verán a continuación, muchos árboles diferentes se pueden encontrar por el procedimiento descrito antes. Las seis reglas de equivalencia más útiles, las cuales están relacionadas a las operaciones del álgebra relacional se presentan a continuación. En lo que sigue, R, S y T son relaciones donde R se define sobre los atributosA = { A₁, A₂, ..., A_n } y S se define sobre los atributos B = { B₁, B₂, ..., B_n }.

1. Conmutatividad de operaciones binarias:
   R ´ S = S ´ R
   R > < S = S > < R
   R È S = S È R
2. Asociatividad de operaciones binarias:
   R ´ (S ´ T) Û (R ´ S) ´ T
   R > < (S > < T) Û (R > < S) > < T
3. Idempotencia de operaciones unarias:
   P _A’ (P _A’’ (R)) Û P _A’ (R)
   s _p1(A1) (s _p2(A2) (R)) Û s _{p1(A1) Ù p2(A2)} (R)
   donde R[A] y A’ Í A, A’’ Í A y A’ Í A.
4. Conmutando selección con proyección
   P _{A1, ..., An} (s _p(Ap) (R)) Û P _{A1, ..., An} (s _p(Ap) (P _{A1, ..., An, Ap} (R)))
   
   
5. Conmutando selección con operaciones binarias
   s _p(A) (R ´ S) Û (s _p(A) (R)) ´ S
   s _p(Ai) (R > < _(Aj, Bk) S) Û (s _p(Ai) R) > < _(Aj, Bk) S
   s _p(Ai) (R È T) Û s _p(Ai) (R) È s _p(Ai) (T)
   donde A_i pertenece a R y a T.
6. Conmutando proyección con operaciones binarias

P _C (R ´ S) Û P _A’ (R) ´ P _B’ (S)

P _C (R > < _(Aj, Bk) S) Û P _A’ (R) > < _(Aj, Bk) P _B’ (S)

P _C (R È S) Û P _C (R) È P _C (T)

donde R[A] y S[B]; C = A’ È B’ donde A’ Í A y B’ Í B.

Ejemplo 4.8. En la Figura 4.8 se presenta un árbol equivalente al mostrado en la Figura 4.7. La reestructuración del árbol de la Figura 4.7 se presenta en la Figura 4.9. El resultado es bueno en el sentido de que se evita el acceso repetido a la misma relación y las operaciones más selectivas se hacen primero. Sin embargo, este árbol aún no es óptimo. Por ejemplo, la operación de selección E no es muy útil antes de la junta dado que no reduce grandemente el tamaño de la relación intermedia.

Figura 4.8. Arbol equivalente al de la Figura 4.7.

Figura 4.9. Arbol reestructura a partir del de la Figura 4.7.