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. Thesis (Doctoral), Facultad de Informática (UPM).

Description

Title: Técnicas de particionamiento multidimensional basadas en índices multiatributo en bases de datos paralelas
Author/s:
  • Barrena García, Manuel
Contributor/s:
  • Miguel Anasagasti, Pedro de
Item Type: Thesis (Doctoral)
Date: November 1995
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Arquitectura y Tecnología de Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (7MB) | Preview

Abstract

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.

More information

Item ID: 4016
DC Identifier: http://oa.upm.es/4016/
OAI Identifier: oai:oa.upm.es:4016
Deposited by: Archivo Digital UPM
Deposited on: 27 Aug 2010 09:25
Last Modified: 20 Apr 2016 13:23
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM