Catálogo de publicaciones - libros

ODRA (Object Database for Rapid Application development) is an object-oriented application development environment currently being constructed at the Polish-Japanese Institute of Information Technology. The aim of the project is to design a next-generation development tool for future database application programmers. The tool is based on the query language SBQL (Stack-Based Query Language), a new, powerful and high level object-oriented programming language tightly coupled with query capabilities. The SBQL execution environment consists of a virtual machine, a main memory DBMS and an infrastructure supporting distributed computing. The paper presents design goals of ODRA, its fundamental mechanisms and some relationships with other solutions.

Nowadays, ontologies are used in a lot of diverse research fields. They provide with the capability to describe a huge set of information contents. Therefore, several approaches for storing ontologies and their instances in databases have been proposed. We call Ontology Based Database (OBDB) a database providing such a capability. Several OBDB have been developed using different ontology models and different representation schemas to store the data. This paper proposes a data model and an algebra of operators for OBDB which can be used whatever are the used ontology model and representation schema. By extending the work done for object oriented databases (OODB), we highlight the differences between OODB and OBDB both in terms of data model and query languages.

Advanced database systems offer similarity queries on complex data. Searching by similarity on complex data is accelerated through the use of metric access methods (MAM). These access methods organize data in order to reduce the number of comparison between elements when answering queries. MAM can be categorized in two types: disk-based and memory-based. The disk-based structures limit the partitioning of space forcing nodes to have multiple elements according to disk page sizes. However, memory-based trees allows more flexibility, producing trees faster to build and to perform queries. Although recent developments target disk-based methods on tree structures, several applications benefits from a faster way to build indexes on main memory. This paper presents a memory-based metric tree, the MM-tree, which successively partitions the space into non-overlapping regions. We present experiments comparing MM-tree with existing high performance MAM, including the disk-based Slim-tree. The experiments reveal that MM-tree requires up to one fifth of the number of distance calculations to be constructed when compared with Slim-tree, performs range queries requiring 64% less distance calculations and KNN queries requiring 74% less distance calculations.

The M-tree and its variants have been proved to provide an efficient similarity search in database environments. In order to further improve their performance, in this paper we propose an extension of the M-tree family, which makes use of nearest-neighbor (NN) graphs. Each tree node maintains its own NN-graph, a structure that stores for each node entry a reference (and distance) to its nearest neighbor, considering just entries of the node. The NN-graph can be used to improve filtering of non-relevant subtrees when searching (or inserting new data). The filtering is based on using ”sacrifices” – selected entries in the node serving as pivots to all entries being their reverse nearest neighbors (RNNs). We propose several heuristics for sacrifice selection; modified insertion; range and kNN query algorithms. The experiments have shown the M-tree (and variants) enhanced by NN-graphs can perform significantly faster, while keeping the construction cheap.

We present a set of time-efficient approaches to index objects moving on the plane to efficiently answer range queries about their future positions. Our algorithms are based on previously described solutions as well as on the employment of efficient data structures. Finally, an experimental evaluation is included that shows the performance, scalability and efficiency of our methods.

In this study, we propose a better relationship based clus tering framework for dealing with unbalanced clustering and outlier fil tering on high dimensional datasets. Original relationship based cluster ing framework is based on a weighted graph partitioning system named METIS. However, it has two major drawbacks: no outlier filtering and forcing clusters to be balanced. Our proposed framework uses Graclus, an unbalanced kernel k-means based partitioning system. We have two major improvements over the original framework: First, we introduce a new space. It consists of tiny unbalanced partitions created using Graclus, hence we call it micro-partition space. We use a filtering approach to drop out singletons or micro-partitions that have fewer members than a threshold value. Second, we agglomerate the filtered micro-partition space and apply Graclus again for clustering. The visualization of the results has been carried out by CLUSION. Our experiments have shown that our proposed framework produces promising results on high dimen sional datasets.

Existing work repeatedly addresses that the ubiquitous positioning devices will start to generate an unprecedented stream of time-stamped positions leading to storage and computation challenges. Hence the need for trajectory compression arises. The goal of this paper is to estimate the effect of compression in spatiotemporal querying; towards this goal, we present an analysis of this effect and provide a model to estimate it in terms of average false hits per query. Then, we propose a method to deal with the model’s calculation, by incorporating it in the execution of the compression algorithm. Our experimental study shows that this proposal introduces a small overhead in the execution of trajectory compression algorithms, and also verifies the results of the analysis, confirming that our model can be used to provide a good estimation of the effect of trajectory compression in spatiotemporal querying.

The paper presents the methods for prediction of bus arrival times and continuous query processing as foundations of traveler information services. The time series of data from automatic vehicle location (AVL) system, consisting of time, location and speed data, is used with historical statistics and bus schedule information to predict future arrivals and motion. Based on predicted and AVL data, continuous query processing technique is proposed to extend traveler information service with notification/alarm features. Extensive experiments have shown that the proposed algorithm for bus motion prediction is efficient enough to function in real conditions and that augmented with continuous query processing techniques can produce services that useful to the travelers.

Query mapping to aggregation lattices is used in order to exploit sub-cube dependencies in multidimensional databases. It is employed in mobile OLAP dissemination systems, in order to reduce the number of handled data items and thus optimize their scheduling and dissemination process. This paper analyzes the impact of choosing between mapping to the data cube lattice or alternatively to the respective hierarchical data cube lattice. We analyze the involved tradeoffs and identify the exploitation degree of sub-cube derivability as the deciding factor. We therefore introduce an analytical framework which computes derivability related probabilities and thus facilitates the quantification of this degree. The information provided by the framework is consistent with experimental results of state of the art mobile OLAP dissemination systems.

Query generators producing sequences of SQL statements are embedded in many applications. As the response time of such sequences is often far from optimal, their optimization is an important issue. CGO (Coarse-Grained Optimization) is an appropriate optimization approach that applies rewrite rules to statement sequences. In previous work on CGO, a heuristic, priority-based control strategy was utilized to choose and execute rewrite rules. In this paper, we present an approach to enable cost-based optimization of statement sequences. We show how to exploit histogram propagation and the costing component of the underlying database system for this purpose. Our work extends previous work on histogram propagation. We conclude with experiments demonstrating the effectiveness of our approach.