Algoritmo de reunión espacio-temporal usando estructura 3DR-tree podada

Abstract

La consulta de reunión (join) es una de las operaciones fundamentales en un Sistema de Administración de Bases de Datos (DBMS). Debido a que los (DBMS) modernos han incorporado nuevos tipos de bases de datos (temporal, espacial, entre otros), se ha hecho necesario contar con nuevos algoritmos para procesar consultas de reunión en esas áreas. Actualmente las bases de datos espacio-temporales han ido cobrando mayor importancia debido a la amplia variedad de aplicaciones que requieren procesar la historia espacial de los objetos. Los métodos de acceso espacio-temporales propuestos hasta ahora estan orientados a procesar principalmente consultas de tipo time-slice y de tipo interval y no abordan la consulta de reunión. En este trabajo presentamos y evaluamos un algoritmo de reunión espacio temporal basado en la estructuras 3DR-tree y que se beneficia por la técnica de podado aplicada. También se introduce un modelo analítico del algoritmo que estima el costo en términos de accesos a nodo o accesos a disco. Finalmente se evalua el comportamiento predictivo del modelo propuesto con el modelo original de costo del algoritmo de reunión espacio-temporal 3DR-tree mostrando la precisión del mismo.

The join query is one of the most important operation in the Database Management System (DBMS). Because of the modern (DBMS) have incorporated new types of data bases (temporal, spatial, among others), it has become necessary to possess new algorithms to process join queries in these areas. Nowadays the databases have been receiving major importance due to the wide variety of applications that they need to process the spatial history of the objects. The spatio-temporal access methods proposed till now are orientated to trying principally timeslice and interval query and they do not approach the join query. In this work we present and evaluate a join space-temporal algorithm based on it structures 3DRtree and that benefits by the applied pruned technique from. Also it is introduced an analytical model about the algorithm that estimate the cost in terms of node or disk accesses. Finally the predictive behavior of the proposed model will be compared with the 3DR-tree cost model showing the accuracy of this model.