Tecnológico Nacional De México.

Instituto tecnológico de Tlalnepantla.

Ingeniería en tecnologías de la información y comunicaciones.

Evidencia a entregar: Presentación del proyecto y Equipo promotor y empresas.

Integrantes del Equipo:

Espino Horta María José 17251067

Morán Evaristo Kassandra 19250054

Hernández Abundis Edgar Adrián 17251057

Gonzalo Ulises Martínez Vázquez 17251051

López Damián Noé Santiago 18251071

Téllez Rojo Oscar Fidel 18250041

Grupo: T-52

Docente: JORGE ARTURO RIVERO MARBAN

Horario:

Martes 11-13hrs

Jueves 11-13hrs

Viernes 11-12hrs
 Introducción

El procesamiento de consultas es de gran importancia en bases de datos centralizadas. La

finalidad es convertir transacciones de usuario en instrucciones para manipulación de datos.
Aunque, el orden en que se realizan las transacciones afecta grandemente la velocidad de
respuesta del sistema. Así, el procesamiento de consultas presenta un problema de optimización
en el cual se determina el orden en el cual se hace la menor cantidad de operaciones. En BDD se
tiene que considerar el procesamiento local de una consulta junto con el costo de transmisión de
información al lugar en donde se solicitó la consulta. En BDD se tiene que considerar el
procesamiento local de una consulta junto con el costo de transmisión de información al lugar en
donde se solicitó la consulta. El éxito creciente de la tecnología de bases de datos relacionales en
el procesamiento de datos se debe, en parte, a la disponibilidad de lenguajes los cuales pueden
mejorar significativamente el desarrollo de aplicaciones y la productividad del usuario final. Los
diferentes factores pueden tener pesos diferentes dependiendo del ambiente distribuido en el que
se trabaje. Por ejemplo, en las redes de área amplia (WAN), normalmente el costo de
comunicación domina dado que hay una velocidad de comunicación relativamente baja, los
canales están saturados y el trabajo adicional requerido por los protocolos de comunicación es
considerable. Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los
costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan
dominante, así que se consideran los tres factores con pesos variables.

Una consulta tiene muchas posibles estrategias de ejecución, a la selección de la más adecuada
se le denomina Optimización De Consulta . El término “OPTIMIZACIÓN” puede no ser el más
adecuado, pues el plan de ejecución posiblemente no es el mejor, es solo Una Estrategia
Razonablemente Eficiente.
 Objetivo General

El objetivo general es investigar los puntos a desarrollar en nuestro proyecto referente a la tercera
unidad el cuál trata de procesamiento de consultas distribuidas donde conoceremos cuáles son las
estrategias de optimización de procesamiento de consultas distribuidas para la recuperación de
datos. Así mismo, el objetivo es que podamos tener las habilidades para buscar, procesar y
analizar información procedente de diversas fuentes. Obtener la capacidad de abstracción, análisis
y síntesis, mismo que hay que aplicar en nuestro proyecto así mismo para identificar, plantear y
resolver problemas.
3.1 Metodología del procesamiento de consultas distribuidas

Las consultas distribuidas se encargan de detener el acceso a datos de varios orígenes de datos
heterogéneos. Estos orígenes de datos pueden estar almacenados en el mismo equipo o en
equipos diferentes.  

SQL Server proporciona características, como IntegrationServices y PowerPivot, que pueden

ayudarle a integrar datos heterogéneos. Otra manera de integrar datos es utilizando las
características de replicación de SQL Server, para replicar los datos entre los servidores. Sql
Server admite la replicación de datos heterogéneos con ciertas bases de datos de IBM y Oracle.  

La función principal de un procesador de consultas relacionales es transformar una consulta en una

especificación de alto nivel, típicamente en cálculo relacional, a una consulta equivalente en una
especificación de bajo nivel.  Hablando más claro para realizar una consulta se debe contar con
heterogenidad (ya mencionado anteriormente) de los datos, para que puedan ser usados para
formular consultar.

Tenemos los siguientes ejemplos:

Base de Datos Centralizada

Base de Datos Distribuidas

Así como también necesitamos contar con:

Localización de los datos para generar reglas heurísticas.

Descomposición de consultas en paralelo en cada nodo.
Reducir la cantidad de datos a transferir en la red.
3.2 Estrategias de procesamiento de consultas distribuidas

El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta SQL, las
características del modelo relacional permiten que cada motor de base de datos elija su propia
representación que, comúnmente, resulta ser el álgebra relacional. La optimización de consultas
es, entonces, una de estas etapas.
Existen distintos métodos para optimizar consultas relacionales, sin embargo el enfoque de
optimización basada en costos combinado con heurísticas que permitan reducir el espacio de
búsqueda de la solución es el método mayormente utilizado por los motores de base de datos
relaciones de la actualidad, en todo caso, independiente del método elegido para optimizar la
consulta, la salida de este proceso debe ser un plan de ejecución, el cual comúnmente es
representado en su forma de árbol relacional.

Contamos con la estrategia de Reformulación de consultas, que nos sirve para encontrar que la
información que nos va a proveer sea solo la que se le pidió por la fuente. También se cuenta con
la estrategia de descomposición de las fuentes, que consiste en que según las fuentes que pidan
cierto tipo de datos sean las atendidas con mayor velocidad.

Para poder optimizar una consulta necesitamos tener claras las propiedades del algebra relacional
para asegurar la reformulación de la consulta, al optimizar una consulta obtenemos los siguientes
beneficios:

Minimizar costos
Reducir espacios de comunicaciones
Seguridad en envíos de información
Árboles de consultas.

Árbol de consulta que es una estructura de árbol que corresponde a una expresión del álgebra
relacional en el que las tablas se representan como nodos hojas y las operaciones del álgebra
relacional como nodos intermedios.
Transformaciones equivalentes 
1.-El servidor recibe una petición de un nodo
2.-El servidor es atacado por el acceso concurrente a la base de datos cargada localmente
3.-El servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local.

Una base de datos es acezada de esta manera la técnica que se utiliza es la de fragmentación de
datos que puede ser hibrida, horizontal y vertical.
En esta fragmentación lo que no se quiere es perder la consistencia de los datos, por lo tanto se
respetan las formas normales de la base de datos ok.
Bueno para realizar una transformación en la consulta primero desfragmentamos siguiendo los
estándares marcados por las reglas formales y posteriormente realizamos el envió y la máquina
que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una
copia que será la equivalente a la original.

Join

La sentencia join en SQL permite combinar registros de dos o más tablas en una base de datos
relacional. En el Lenguaje de Consultas Estructurado (SQL), hay tres tipos de JOIN: interno,
externo, y cruzado.

En casos especiales una tabla puede unirse a sí misma, produciendo una auto-combinación,
SELF-JOIN.
Matemáticamente, JOIN es composición relacional, la operación fundamental en el álgebra
relacional, y generalizando es una función de composición.

Sean (R) y s(S) dos relaciones:

Si R S= entonces r s es lo mismo que r x s, y por lo tanto se puede utilizar la estimación del

producto cartesiano.

Si R S es una clave de R entonces el número de tuplas en r s no es mayor que el número de tuplas

en S. Si R S es una clave externa de R entonces el número de tuplas de r s es exactamente el
número de tuplas de S.

Si R S no es clave de R ni de S entonces se supone que cada valor aparece con la misma

probabilidad, por lo tanto, sea t una tupla de r y sea R S=Ā, entonces se estima que la tupla t
produce:

Tuplas en s, por lo tanto se estima el tamaño de r s = (a) al cambiar los papeles de r y s se tiene (b)

Estos valores serán distintos si y sólo si V(A,r) V(A,s), si este es el caso, la más baja estimación de
ambas será la más conveniente.

Join en bucles anidados.

Si z = r s, r recibirá el nombre de relación externa y s se llamará relación interna, el algoritmo de

bucles anidados se puede presentar como sigue para cada tupla tr en r

Para cada tupla ts en ssi (tr,ts) satisface la condición entonces añadir tr ts al resultado Algoritmo 5–
1 - Join en bucles anidados.

Donde tr ts será la concatenación de las tuplas tr y ts .

Como para cada registro de r se tiene que realizar una exploración completa de s, y suponiendo el
peor caso, en el cual la memoria intermedia sólo puede concatenar un bloque de cada relación,
entonces el número de bloques a acceder es de . Por otro lado, en el mejor de los casos si se
pueden contener ambas relaciones en la memoria intermedia entonces sólo se necesitarían
accesos a bloques.
Ahora bien, si la más pequeña de ambas relaciones cabe completamente en la memoria, es
conveniente utilizar esta relación como la relación interna, utilizando así sólo accesos a bloques.
Join en bucles anidados por bloques.

Una variante del algoritmo anterior puede lograr un ahorro en el acceso a bloques si se procesan
las relaciones por bloques en vez de por tuplas.

Para cada bloque Br de rpara cada bloque Bs de spara cada tupla tr en Brpara cada tupla ts en
Bssi (tr,ts) satisface la condición entonces añadir tr ts al resultado

Algoritmo 5–2 - Join en bucles anidados por bloques.

La diferencia principal en costos de este algoritmo con el anterior es que en el peor de los casos
cada bloque de la relación interna s se lee una vez por cada bloque de r y no por cada tupla de la
relación externa, de este modo el número de bloques a acceder es de donde además resulta más
conveniente utilizar la relación más pequeña como la relación externa.

Join en bucles anidados por índices.

Este algoritmo simplemente sustituye las búsquedas en tablas por búsquedas en índices, esto
puede ocurrir siempre y cuando exista un índice en el atributo de join de la relación interna. Este
método se utiliza cuando existen índices así como cuando se crean índices temporales con el
único propósito de evaluar la reunión.

El costo de este algoritmo se puede calcular como sigue: para cada tupla de la relación externa r
se realiza una búsqueda en el índice de s para recuperar las tuplas apropiadas, sea c = costo de la
búsqueda en el índice, el cual se puede calcular con cualquiera de los algoritmos A3, A4 o A5.
Entonces el costo del join es; si hay índices disponibles para el atributo de join en ambas
relaciones, es conveniente utilizar la relación con menos tuplas.

3.3 Optimización de Consultas.

Para poder optimizar una consulta necesitamos tener claras las propiedades del algebra relacional
para asegurar la reformulación de la consulta, al optimizar una consulta obtenemos los siguientes
beneficios:
 Minimizar costos.
  Reducir espacios de comunicaciones.
 Seguridad en envíos de información.

Tipo de optimización
El problema de optimización de consultas es altamente demandante en tiempo de ejecución y, en
el caso general, es un problema de la clase NP. Así existen dos estrategias para su solución:
búsqueda exhaustiva o el uso de heurísticas. Los algoritmos de búsqueda exhaustiva tienen una
complejidad combinatoria en el número de relaciones de la consulta. Obtienen la transformación
óptima, pero sólo se aplican a consultas simples dado su tiempo de ejecución.
Por otro lado, los algoritmos heurísticos obtienen solo aproximaciones a la transformación óptima,
pero lo hacen en un tiempo de ejecución razonable. Las heurísticas más directas a aplicar son el
agrupamiento de expresiones comunes para evitar el cálculo repetido de las mismas, aplicar
primero las operaciones de selección y proyección, reemplazar una junta por una serie de semi-
juntas y reordenar operaciones para reducir el tamaño de las relaciones intermedias.

Optimización global de consultas

Cuando hablamos de optimización de consultas nos referimos a mejorar los tiempos de respuesta
en un sistema de gestión de bases de datos relacional, pues la optimización es el proceso de
modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles. En
bases de datos relacionales el lenguaje de consultas SQL es el más utilizado por el común de los
programadores y desarrolladores para obtener información desde la base de datos. La complejidad
que pueden alcanzar algunas consultas puede ser tal, que el diseño de una consulta puede tomar
un tiempo considerable, obteniendo no siempre una respuesta óptima.

Optimización local de consultas

Para procesar una consulta local solo se hace referencia a tablas y bases de datos locales(no a
vistas ni a tablas remotas) , es decir que estén dentro de la misma instancia del manejador de
bases de datos, en una única máquina y que no se tenga que conectar al servidor a otras
máquinas para poder efectuar la consulta. Cada subconsulta que se ejecuta en un nodo, llamada
consulta local, es optimizada usando el esquema local del nodo. Hasta este momento, se pueden
eligen los algoritmos para realizar las operaciones relacionales. La optimización local utiliza los
algoritmos de sistemas centralizados

Granularidad de la optimización
Existen dos alternativas: considerar sólo una consulta a la vez o tratar de optimizar múltiples
consultas. La primera alternativa no considera el uso de resultados comunes intermedios. En el
segundo caso puede obtener transformaciones eficientes si las consultas son similares. Sin
embargo, el espacio de decisión es mucho más amplio lo que afecta grandemente el tiempo de
ejecución de la optimización.

Tiempo de optimización
Una consulta puede ser optimizada en tiempos diferentes con relación a tiempo de ejecución de la
consulta. La optimización se puede realizar de manera estática antes de ejecutar la consulta o de
forma dinámica durante la ejecución de la consulta. La optimización estática se hace en tiempo de
compilación de la consulta. Así, el costo de la optimización puede ser amortizada sobre múltiples
ejecuciones de la misma consulta. Durante la optimización de consultas dinámica la elección de la
mejor operación siguiente se puede hacer basada en el conocimiento exacto de los resultados de
las operaciones anteriores. Por tanto, se requiere tener estadísticas acerca del tamaño de los
resultados intermedios para aplicar esta estrategia.
Un tercer enfoque, conocido como híbrido, utiliza básicamente un enfoque estático, pero se puede
aplicar un enfoque dinámico cuando los tamaños de las relaciones estimados están alejados de los
tamaños actuales.
Estadísticas
La efectividad de una optimización recae en las estadísticas de la base de datos. La optimización
dinámica de consultas requiere de estadísticas para elegir las operaciones que deben realizarse
primero. La optimización estática es aún más demandante ya que el tamaño de las relaciones
intermedias también debe ser estimado basándose en estadísticas.
Nodos de Decisión
Cuando se utiliza la optimización estática, un solo nodo o varios de ellos pueden participar en la
selección de la estrategia a ser aplicada para ejecutar la consulta. La mayoría de los sistemas
utilizan un enfoque centralizado para la toma de decisiones en el cual un solo lugar decide la
estrategia a ejecutar. Sin embargo, el proceso de decisión puede ser distribuido entre varios nodos
los cuales participan en la elaboración de la mejor estrategia.
•Indicar cuales son los puntos para la optimización de consultas
distribuidas, y explicar la optimización global de consultas y la optimización
local de consultas.

El objetivo del procesamiento de consultas en un ambiente distribuido es transformar una consulta

sobre una base de datos distribuida en una especificación de alto nivel a una estrategia de
ejecución eficiente expresada en un lenguaje de bajo nivel sobre bases de datos locales.
Así, el problema de optimización de consultas es minimizar una función de costo tal que la función
del costo total = costo de I/O + costo de CPU + costo de comunicación.
Los diferentes factores pueden tener pesos diferentes dependiendo del ambiente distribuido en el
que se trabaje. Por ejemplo, en las redes de área amplia (WAN), normalmente el costo de
comunicación domina dado que hay una velocidad de comunicación relativamente baja, los
canales están saturados y el trabajo adicional requerido por los protocolos de comunicación es
considerable. Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los
costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan
dominante, así que se consideran los tres factores con pesos variables.
Optimización Global de Consultas
Dada una consulta algebraica sobre fragmentos, el objetivo de esta capa es hallar una estrategia
de ejecución para la consulta cercana a la óptima. La estrategia de ejecución para una consulta
distribuida puede ser descrita con los operadores del álgebra relacional y con primitivas de
comunicación para transferir datos entre nodos. Para encontrar una buena transformación se
consideran las características de los fragmentos, tales como, sus cardinalidades. Un aspecto
importante de la optimización de consultas es el ordenamiento de juntas, dado que algunas
permutaciones de juntas dentro de la consulta pueden conducir a un mejoramiento de varios
órdenes de magnitud. La salida de la capa de optimización global es una consulta algebraica
optimizada con operación de comunicación incluida sobre los fragmentos.

Optimización Local de Consultas

El trabajo de la última capa se efectúa en todos los nodos con fragmentos involucrados en la
consulta. Cada subconsulta que se ejecuta en un nodo, llamada consulta local, es optimizada
usando el esquema local del nodo. Hasta este momento, se pueden eligen los algoritmos para
realizar las operaciones relacionales.
Conclusión
 Referencias
Samperio Mauricio. (06 de diciembre de 2010). Blog Mauricio-ISO20000.
Recuperado el 25 de mayo de 2021, de
http://www.desarrolloweb.com/articulos/arquitectura-base-de-datos.html

3.2. Estrategias de procesamiento de consultas distribuidas. -

2015_08_BDD_Gonzalez_Damian. (s/f). Recuperado el 25 de mayo de
2021, de Google.com website:
https://sites.google.com/site/201508bddgonzalezdamian/3-procesamiento-
de-consultas-distribuidas/3-2-estrategias-de-procesamiento-de-consultas-
distribuidas

Mauricio, & Perfil, V. T. mi. (s/f). Bases de Datos Distribuidas. Recuperado el 25 de

mayo de 2021, de Blogspot.com website: http://mauricio-
iso20000.blogspot.com/p/unidad-3.html

(S/f). Recuperado el 25 de mayo de 2021, de Itpn.mx website:

http://itpn.mx/recursositics/5semestre/basededatosdistribuidas/Unidad
%20III.pdf