Técnicas de particionamiento multidimensional basadas en índices multiatributo en bases de datos paralelas

Barrena García, Manuel (1995). Técnicas de particionamiento multidimensional basadas en índices multiatributo en bases de datos paralelas. Tesis (Doctoral), Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Técnicas de particionamiento multidimensional basadas en índices multiatributo en bases de datos paralelas
Autor/es:
  • Barrena García, Manuel
Director/es:
  • Miguel Anasagasti, Pedro de
Tipo de Documento: Tesis (Doctoral)
Fecha: Noviembre 1995
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Arquitectura y Tecnología de Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (7MB) | Vista Previa

Resumen

Los requerimientos cada día más exigentes de modernas aplicaciones de bases de datos, tales como GIS, CAD, CASE y otras, imponen la necesidad de encontrar nuevas vías de solución al problema del tratamiento de grandes volúmenes de información. La potencia de procesamiento de computadores paralelos económicamente abordables, ha atraído la atención de una gran comunidad de investigadores y técnicos que encuentran en los sistemas paralelos de bases de datos la respuesta eficiente a las exigencias de nuevas aplicaciones. Específicamente, la tecnología del paralelismo resulta una atractiva vía de solución a la problemática tradicional del cuello de botella que representan las operaciones de entrada/salida. Con objeto de minimizar el tiempo de respuesta a una consulta, los sistemas de bases de datos paralelas particionan los datos entre un conjunto de dispositivos de almacenamiento, favoreciendo el acceso en paralelo a los mismos y permitiendo, en definitiva la participación concurrente de varios procesadores en la ejecución de una consulta. Habitualmente, el particionamiento de las relaciones se efectúa por un sólo atributo, enviando las tupias a distintos dispositivos dependiendo del valor de dicha tupia sobre el atributo de particionamiento. Esta forma de fragmentar los datos resulta adecuada cuando el predicado de la consulta incluye el atributo de particionamiento. Sin embargo, en aquellos casos en que esto no sea así, la consulta debe ser dirigida hacia todos los nodos de procesamiento encargados de gestionar algún fragmento de la relación o relaciones implicadas en la consulta. Este modo de proceder afecta negativamente no sólo al tiempo de ejecución de la consulta, sino también al throughput del sistema. En la tesis que se presenta, se proponen modelos de particionamiento multidimensional, basados en la consideración de múltiples atributos. Básicamente, la técnica propuesta consiste en realizar un particionamiento por múltiples dimensiones del espacio de tupias, enviando posteriormente los diferentes fragmentos en que queda dividido este espacio a un determinado número de discos del sistema. Por su parte, la fragmentación del espacio de tupias se realiza equilibradamente por medio de un nuevo mecanismo de indexación multiatributo, conocido bajo el nombre de árbol Q. En el desarrollo de esta memoria de tesis, se exponen las ideas que han conducido al establecimiento del árbol Q; se definen con detalle las estructuras y algoritmos de manipulación del árbol Q; se presentan diversas estrategias de particionamiento basadas en esta estructura y se exhiben los resultados de rendimiento de las diferentes propuestas, basados en los trabajos de implementación realizados durante la fase de ejecución de esta tesis. Abstract The demanding requirements of modern datábase applications, such as GIS, CAD, CASE and others, claim for new solutions to the problem of managing large quantity of information. The processing power of inexpensive parallel computers has focussed the attention of many searchers who find in such computer systems the answer to the demands of these new applications. Specifically, the parallelism technology seems an attractive via to solve the traditional bottlelneck found in input/output operations. With the goal of minimizing the response time of a query, the parallel datábase systems decluster data among a number of storage devices, by favouring the access in parallel to data and by permitting the contribution of several processors in the execution of a query. Frequently, the partitioning of relations is made by a single attribute, sending tupies to different disks by depending on the valué of the tupie on the partitioning attribute. This way to fragment data is useful when the partitioning attribute is involved in the predícate of the query. However, in those situations where it is not the case, the query must be directed to every processing node which is in charge of some fragment of the relation or relations involved in the query. This approach affects negatively to both, the response time of the query and the throughput of the system. In the thesis we present, a multidimensional partitioning model is proposed. In short, the proposed technique partitions, on the base of múltiple attributes, the tupie space by sending the different fragments of the space to a specific number of disks in the system. By its hand, the tupie space partitioning is made in a balanced way by means of a new multi-attribute indexing method, called the Q-tree. In this thesis dissertation, we present the ideas which have guided the stablishment of the Q-tree. In addition, we define the structures and algorithms for manipulating the Q-tree, we introduce several partitioning strategies based on this structure and, finally, we include the performance results of the different proposals, based on the implementation tasks carried out during the execution of this doctoral thesis.

Más información

ID de Registro: 4016
Identificador DC: http://oa.upm.es/4016/
Identificador OAI: oai:oa.upm.es:4016
Depositado por: Archivo Digital UPM
Depositado el: 27 Ago 2010 09:25
Ultima Modificación: 20 Abr 2016 13:23
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM