Página principal

Optimización de consultas y cuantificadores difusos


Descargar 119.57 Kb.
Página1/8
Fecha de conversión23.09.2016
Tamaño119.57 Kb.
  1   2   3   4   5   6   7   8
OPTIMIZACIÓN DE CONSULTAS Y CUANTIFICADORES DIFUSOS

Leonid TINEO

leonid@usb.ve

Doctorado en Computación

Universidad Simón Bolívar

Resumen


Los Manejadores de Bases de Datos tienen una gran utilidad en el almacenamiento confiable de gran volumen de data. Sin embargo no es sólo esta cualidad la que los hace tan exitosos y útiles, sino también la capacidad de dar acceso eficiente a tal volumen de datos. Para esto se han concebido los mecanismos de optimización de consulta. Un reto que se le plantea a estos sistemas es la posibilidad de permitir la expresión de requerimientos de usuarios con lenguajes cada vez más cercanos a su forma de pensar y a sus preferencias. En este sentido, algunas extensiones basadas en Lógica Difusa han sido propuestas para mejorar la expresividad de los lenguajes de consultas. Uno de los conceptos de esta teoría que podría ser de gran utilidad en la expresión de requerimientos de usuarios es el de Cuantificadores Difusos. Este artículo presenta brevemente el tema de Optimización de Consultas y el tema de Cuantificación Difusa, como marco conceptual básico para una investigación desarrollada sobre los Mecanismos de Evaluación de Consultas Difusas Cuantificadas.

Palabras Claves: Bases de Datos Relacionales, Optimización de Consultas, Cuantificadores Difusos, Consultas Difusas

INTRODUCCIÓN


Actualmente, se llevan a cabo grandes esfuerzos para “humanizar” el acceso a la información. En tal sentido, se busca crear mecanismos de especificación de consultas que se asemejen cada vez más a la expresión del lenguaje natural y al pensamiento humano. Se desea, por tanto, proveer capacidades de Consultas Flexibles que les permitan a los usuarios expresar requerimientos que involucren preferencias[12][13][30][42]. Estas capacidades de consulta necesitan de la expresión y manipulación de términos y sentencias lingüísticos en condiciones de consulta [7][25][39][41].

Un requerimiento de usuario que podría ser formulado y evaluado con estas nuevas capacidades sería, por ejemplo: “Un investigador va a una conferencia en otra ciudad y desea, para alojarse, encontrar un hotel que satisfaga la mayoría de los siguientes criterios: no muy caro, cerca del centro de convención, cerca de alguna estación del metro, con buenas áreas deportivas, cerca de un centro comercial”. Otro posible requerimiento, de este estilo es el siguiente: “Una joven quiere aplicar a un trabajo como investigador novel en un centro de investigación donde hayan al menos cinco investigadores de reconocido prestigio en algún área que sea de su interés”.

En los dos ejemplos anteriores hay algunos términos lingüísticos que representan preferencias de usuarios. Entre estos términos se quiere prestar atención particularmente a las frases “la mayoría” y “al menos cinco”. Estos términos son ejemplos de los llamados Cuantificadores Difusos, una extensión de los cuantificadores lógicos que permiten describir gradualmente cantidades mediante el uso de conjuntos difusos. La investigación realizada trata justamente sobre la evaluación de consultas que involucran cuantificadores difusos.

A pesar del poder expresivo de la Lógica Difusa, en la comunidad de Bases de Datos, existe cierta resistencia para su uso en consultas [25]. Una razón para tal resistencia radica en el costo que genera la evaluación de la consulta: el costo de procesamiento para las consultas difusas parece ser mucho mayor que para las consultas clásicas[10].

Se han hecho muchos esfuerzos para disminuir los costos de la evaluación de consultas en el contexto de Manejadores de Bases de Datos Relacionales[26]Error: Reference source not found[34][40]. Estructuras poderosas para almacenamiento y recuperación de datos han constituido la clave para mejorar el desempeño de las consultas. Asimismo, se han creado optimizadores de consultas, aprovechando estas estructuras, así como las condiciones de consulta. A pesar del uso de esta tecnología, el problema de la evaluación de consultas clásicas se mantiene, de alguna forma, abierto; dada una consulta, en general, puede que la forma de evaluación óptima no se logre[10]. Sin embargo, en este caso, generalmente, es posible encontrar un método de procesamiento de consultas con costo razonable. Ésta es la función de los optimizadores de consultas.

En el proceso de evaluación de consultas difusas, las estructuras de acceso disponibles no pueden usarse directamente, ya que los criterios de selección se basan en el grado de satisfacción de las condiciones difusas cuya semántica dependiente del usuario. En general, es imposible crear estructuras de acceso especializadas[3].

A continuación se presentan las nociones fundamentales de optimización de consultas clásicas, así como las nociones sobre cuantificación difusa, con miras a sustentar una investigación sobre los mecanismo de evaluación de consultas difusas cuantificadas.

OPTIMIZACIÓN DE CONSULTAS


Las bases de datos son ampliamente usadas en sistemas de información tanto públicos como privados para una gran gama de campos de aplicación. Para la manipulación correcta y segura de bases de datos se han creado herramientas de software llamadas Sistemas Manejadores de Bases de Datos (DBMS, por sus siglas en inglés: Database Management Systems). Tales sistemas hacen la conexión entre la representación de los datos al nivel del usuario o programador y el nivel físico de almacenamiento de datos. Los modelos de datos tienen como finalidad la representación de la información de una situación del mundo real. En consecuencia, se usan en los DBMS para representar los datos.

En los inicios de la tecnología de bases de datos, los modelos de datos poseían un nivel de abstracción muy bajo, representando los datos con estructuras muy cercanas al nivel de almacenamiento físico. Codd [23], en 1970, propuso el Modelo Relacional con la idea de concebir una representación completamente independiente de las estructuras físicas. Este modelo de datos se basa en el concepto matemático de relación. Actualmente, la mayoría de los DBMS se basan en el Modelo Relacional.

Una de las funciones principales de los DBMS es proveer acceso eficiente a grandes volúmenes de datos [28][49]. Este acceso se hace mediante consultas que representan requerimientos de usuarios, las cuales son expresadas mediante lenguajes de manipulación de bases de datos, usualmente conocidos como lenguajes de consulta. Los enfoques más generales y formales son el Álgebra Relacional[23] y el Cálculo Relacional[37]. Basándose en estos lenguajes de consulta teóricos, se ha concebido un lenguaje práctico, SQL [35]. Este lenguaje se ha convertido en el estándar para las consultas sobre bases de datos relacionales.

La eficiencia en la recuperación de información en los DBMS es alcanzada mediante el uso adecuado de estructuras físicas concebidas para acelerar el acceso a los datos. Estas estructuras son conocidas bajo la denominación común de “caminos de acceso” (en inglés “access paths”) [45]. Entre tales estructuras destacan los árboles de búsqueda en memoria secundaria, como lo son los árboles B+ [24] y las tablas de acceso directo (conocidas como “Hash”, por su nombre en inglés).

Pese a la existencia de tales estructuras, dada una consulta en SQL, en general, no se puede garantizar cuál es la mejor manera de resolverla, de forma de obtener el menor costo. Una pieza de software dentro de los DBMS se encarga optimizar la consulta, esta pieza es el optimizador. En este contexto, se entiende por “optimizar” decidir la forma de procesar una consulta de manera que su costo de evaluación sea razonable[45]. Para realizar su trabajo, el optimizador se apoya en un componente del DBMS que almacena la información sobre las estructuras lógicas y físicas de los datos: el Catálogo del Sistema. Para su uso en la optimización, el catálogo, almacena ciertos datos estadísticos como el tamaño de las tablas, tiempo de acceso promedio, entre otros.

El problema de encontrar la mejor forma de procesar una consulta es NP completo, debido a la combinatoria de posibles ordenes de evaluación de los operadores involucrados en la consulta y las posibles manera de resolver cada uno de estos operadores. Si se quisiera obtener el menor costo, tendría que estimarse el costo de cada una de estas combinaciones y hallar el mínimo entre ellos. Lo que hacen los optimizadores es trabajar con un conjunto reducido de alternativas de procesamiento, para lo cual se aplican algunas heurísticas.

La mayoría de los optimizadores de consultas se basan en el Sistema R que es un optimizador de consulta de IBM[46]. El enfoque de este sistema se conoce como “Optimización Basada en Costos”. Las siguientes secciones se centran es este tipo de optimización. Hay otros enfoques los cuales no se consideran en este trabajo. Entre estos se encuentra la “Optimización Basada en Reglas” [29] en la que el programador puede especificar reglas que guíen al optimizador en su trabajo. Otro enfoque es el de “Generación Aleatoria de Planes”, éste usa algoritmos probabilísticos [22] para explorar el espacio de planes de ejecución de una manera rápida, obteniendo planes relativamente buenos.

  1   2   3   4   5   6   7   8


La base de datos está protegida por derechos de autor ©espanito.com 2016
enviar mensaje