Aplicación de técnicas de optimización para la generación de planes de ejecución de consultas hacia bases de datos remotas

¿Cómo se generan los planes de ejecución de consultas hacia bases de datos remotas, donde la consulta es única y el plan la descompone en preguntas parciales hacia las bases de datos relevantes (el software debe escoger primero cuáles bases serán las relevantes, las usadas)? ¿En qué orden deben ejecutarse estas consultas parciales, o pueden ser simultáneas? En su tesis de maestría en el CIC-IPN, dirigido por el M. en C. Alejandro Botello, Rodolfo Navarro Zayas aborda y resuelve este problema. Pulse aquí para obtener la tesis de Rodolfo (texto completo). 

Resumen.
Un sistema mediador es aquel que permite llevar a cabo la integración de datos que residen en fuentes de información generalmente heterogéneas – que no son del mismo sistema y/o modelo de datos - y remotas, y para ello utiliza una representación unificada de los datos (denominada esquema mediado). Este esquema es utilizado por el usuario para formular consultas particulares al sistema mediador, sin que el usuario conozca la ubicación física de los datos, ni los esquemas de las fuentes en las que estos se encuentran alojados. Estos aspectos deben ser resueltos por el sistema mediador al tiempo de ejecutar la consulta.
En este trabajo se presenta una propuesta de solución para la generación de planes de ejecución de consultas hacia bases de datos remotas, que podrá ser incorporada por el módulo optimizador de un sistema mediador, y en donde el enfoque propuesto inicia recibiendo la consulta del usuario (que inicialmente se encuentra en términos del esquema mediado) y procede a: a) hacer la selección de fuentes relevantes (aquellas que cooperan con respuestas trascendentes), b) la descomposición de la consulta en expresiones que están en términos de los esquemas locales (denominadas consultas objetivo), así como, c) generar la definición del orden de las operaciones de reunión, buscando que este orden proporcione agilidad al procesamiento de la consulta en la integración.
Para determinar el orden de ejecución, se aplican algunas fórmulas de optimización para estimar el número de registros resultantes de las reuniones implicadas en la consulta, tomando en cuenta los valores de selectividad (número de tuplas que cumplen un predicado sobre el total de tuplas), la cardinalidad (los valores que aparecen en un atributo) y los tamaños de las tablas (número total de tuplas) involucradas; posteriormente se utilizan estos datos en un algoritmo Greedy cuya función de progreso consiste en dar una mayor prioridad a la ejecución temprana de las operaciones que generan una cantidad menor de tuplas, con el fin de evitar o postergar tanto como sea posible las operaciones que generan más tuplas y por consiguiente reducir el tiempo de respuesta del sistema para resolver la consulta del usuario.

Abstract.
A mediator system performs the integration of data which is located in remote sources, these sources usually are heterogeneous (it means that sources do not belong to the same system or that the sources use different data models to store the information). In order to handle these differences the mediator uses a unified data representation (called mediated schema), this representation is used by the user to express their queries to the system, therefore the user does not need to know the location of the data or the schemas of the sources where the data is stored, These aspects are handled by the mediator system at query execution time.
In this text is presented an approach to generate optimal query execution plans through the access to remote databases, this approach must be able to be incorporated in a query optimizer module of a mediator system. This module receives the user query (which initially is expressed in terms of the mediated schema) and then: a) perform the selection of the relevant sources (those which provide meaningful results), b) do the query decomposition of expressions in terms of local schemas (called target queries) and c) determine the execution order of joins operations, aiming to provide agility to query execution process.
To determine the execution order, some optimization formulas are performed for estimating the number of records resulting from the join operations involved in the query, considering the selectivity values (number of tuples that satisfy a condition) cardinality (the values that appear in an attribute) and the sizes of the tables (total number of tuples) involved; then these data is used for a Greedy algorithm whose progress evaluation function gives greater priority to the early execution of operations that generate fewer tuples, in order to avoid or delay as much as possible the operations that generate more tuples and thus reduce the response time of the system to resolve the user query.
Click here to obtain Rodolfo's thesis.