Departamento de Computación

Una de las actividades más importantes del diseño de bases de datos distribuidas es la fragmentación, esta consiste en dividir una relación o tabla en un conjunto de relaciones (esquema de fragmentación), que contienen subconjuntos de tuplas (fragmentación horizontal), atributos (fragmentación vertical) o tuplas y atributos (fragmentación híbrida)para reducir el número de accesos a disco, así como el transporte de datos necesarios para realizar consultas y de esta forma reducir el tiempo de respuesta de dichas consultas. La fragmentación vertical es una técnica de diseño de bases de datos distribuidas ampliamente utilizada en las bases de datos tradicionales (relacionales y orientadas a objetos que sólo contienen atributos textuales y numéricos) para reducir el número de atributos irrelevantes accedidos por las consultas. Actualmente, debido a la popularidad de las aplicaciones multimedia en Internet, surge la necesidad de utilizar estrategias de fragmentación en las bases de datos multimedia para aprovechar sus ventajas potenciales con respecto a la optimización de consultas. En las bases de datos multimedia los atributos tienden a ser objetos multimedia muy grandes, y por lo tanto, la reducción del número de accesos a objetos no utilizados por las consultas (irrelevantes) implicaría un ahorro considerable en el costo de ejecución de las consultas. Sin embargo, la utilización de las técnicas de fragmentación vertical en bases de datos multimedia implica dos problemas: 1) los algoritmos de fragmentación vertical sólo toman en cuenta datos alfanuméricos y 2) el proceso de fragmentación se realiza de manera estática. Para resolver estos problemas proponemos un sistema basado en reglas activas (o sistema activo) llamado DYMOND (DYnamic Multimedia ON line Distribution) que realiza una fragmentación vertical dinámica en bases de datos multimedia. Nuestras contribuciones son las siguientes:       1. Creamos un método de fragmentación vertical para bases de datos relacionales, el cual se basa en soporte, una medida utilizada en minería de reglas de asociación. La principal ventaja de nuestro método es que obtiene automáticamente el valor del umbral de soporte mínimo y utilizando dicho umbral encuentra el esquema de fragmentación vertical óptimo, mientras que otros métodos relacionados prueban diferentes umbrales, con los que obtienen distintos esquemas de fragmentación vertical y después utilizan un modelo de costo para encontrar el óptimo. 2. Desarrollamos un algoritmo de fragmentación vertical para bases de datos multimedia, llamado MAVP (Multimedia Adaptable Vertical Partitioning). La principal ventaja de MAVP es que toma en cuenta el tamaño de los atributos para obtener fragmentos que minimizan la cantidad de datos irrelevantes accedidos y datos transportados por las consultas. 3. Presentamos un modelo de costo para evaluar esquemas de fragmentación vertical en bases de datos multimedia distribuidas. Algunos modelos de costo existentes sólo miden el costo de acceso a disco (E/S), pero no consideran el costo de transporte que es un factor que domina el costo de las consultas en bases de datos multimedia distribuidas. Los modelos que si miden el costo de transporte no toman en cuenta el tamaño de los atributos. Nuestro modelo de costo utiliza el tamaño de los atributos para obtener el costo de acceso a atributos irrelevantes, así como el costo de transporte de las consultas en una base de datos multimedia distribuida. 4. Proponemos un sistema activo de fragmentación vertical dinámica para bases de datos relacionales llamado DYVEP (DYnamic VErtical Partitioning). Usando reglas activas DYVEP puede monitorizar consultas ejecutadas en la base de datos con el fin de acumular la información necesaria para desarrollar la fragmentación vertical y disparar automáticamente el proceso de fragmentación si se determina que el esquema de fragmentación vertical se ha vuelto inadecuado debido a cambios en los patrones de acceso o en el esquema de la base de datos. 5. Extendemos DYVEP para utilizarlo en bases de datos multimedia (DYMOND). DYMOND tiene cuatro módulos basados en reglas activas: 1) un Recolector de Estadísticas que almacena, filtra y analiza información relacionada con las consultas que se realizan en la base de datos, como la frecuencia de acceso de las consultas y los objetos multimedia que estas acceden, 2) un Evaluador de Desempeño, que obtiene el costo del esquema de fragmentación actual basado en el modelo de costo propuesto y si el costo es mayor que un umbral, entonces dispara el algoritmo de fragmentación vertical, 3) MAVP que genera un esquema de fragmentación vertical que minimiza el costo de ejecución de las consultas, y 4) un Generador de Fragmentos, que materializa el esquema de fragmentación encontrado por MAVP.

Abstract

One of the most important activities of distributed database design is partitioning, this consists of dividing a relation or table into two or more relations (partitioning scheme) which contain subsets of either tuples (horizontal partitioning), attributes (vertical partitioning), or tuples and attributes (hybrid fragmentation) to reduce both the number of disk accesses and the remote data transported needed to answer a query, and in this way, reducing the response time of such queries. Vertical partitioning is a distributed database design technique widely employed in traditional databases (relational and object-oriented databases that only manage numeric and textual attributes) to reduce the number of irrelevant attributes accessed by the queries. Currently, due to the popularity of multimedia applications on the Internet, the need of using partitioning strategies in multimedia databases has arisen in order to use their potential advantages with regard to query optimization. In multimedia databases, the attributes tend to be of very large multimedia objects. Therefore, the reduction in the number of accesses to objects which are not used by the queries (irrelevant) would imply a considerable cost saving in the query execution. Nevertheless, the use of vertical partitioning techniques in multimedia databases implies two problems: 1) current vertical partitioning algorithms only take into account alphanumeric data, and 2) the partitioning process is carried out in a static way. In order to solve these problems, we propose an active rule-based system (or active system) called DYMOND (DYnamic Multimedia ON line Distribution) which performs a dynamic vertical partitioning in multimedia databases. Our contributions are the following: 1. We create a vertical partitioning method for relational databases, which is based on support, a measure used in association rule mining. The main advantage of our method is that it automatically obtains the value of the threshold of minimum support, and according to this threshold, it finds the optimal vertical partitioning scheme, while other related methods probe different thresholds to get different vertical partitioning schemes, and then they use a cost model to find the optimal. 2. We develop a vertical partitioning algorithm for multimedia databases, called MAVP (Multimedia Adaptable Vertical Partitioning), The main advantage of MAVP is that it takes into account the size of the attributes to obtain fragments that minimizes the amount of both irrelevant data accessed and data transported by the queries. 3. We present a cost model to evaluate vertical partitioning schemes in distributed multimedia databases. Some existing cost models only measure the number of disk accesses (I/O) to query processing, but they do not consider the transportation cost, which dominates query costs in distributed multimedia databases. The models which measure the transportation cost do not take into account the size of the attributes. Our cost model uses the size of the attributes to obtain both the cost of accessing irrelevant attributes and the transportation cost of the queries in a distributed multimedia database. 4. We propose an active system for dynamic vertical partitioning of relational databases, called DYVEP (DYnamic VErtical Partitioning). Using active rules, DYVEP can monitor queries run against the database in order to accumulate the necessary information to develop the vertical partitioning, and automatically trigger the partitioning process if it is determined that the vertical partitioning scheme has become inadequate due to changes in access patterns or in the database scheme. 5. We extend DYVEP to use it in multimedia databases (DYMOND). DYMOND has four active rule-based modules: 1) The Statistics Collector stores, filters and analyzes information related to the database queries, like the access frequency of such queries and the multimedia objects accessed by them, 2) The Performance Evaluator calculates the cost of the current vertical partitioning scheme using the proposed cost model, and if the cost is greater than a threshold, then it triggers the vertical partitioning algorithm, 3) MAVP generates a vertical partitioning scheme, which minimizes the execution cost of the queries, and 4) the Partitioning Generator materializes the partitioning scheme found by MAVP.