University of Konstanz
Database & Information Systems Group
Prof. Marc H. Scholl

support for non-standard datatypes in dbms

Schedule

Recurring Events

Talks

XPath Accelerator: Efficient Processing of Tree Structured Data

Although the tree is one of the most fundamental data structures in computer science, tree structured data is usually poorly supported by current database systems. Trees are inherently recursive, but recursive (SQL) queries are usually expensive on relational database systems. The XPath accelerator is a mapping scheme to store tree data in a relational database and replaces recursive queries by range conditions on integer values that can be efficiently handled by the B+- or R-Trees of current databases.

presented by Brendan Briody

Subtyping for Regular Tree Types

The data model behind XML documents is the tree. This naturally leads to tree-structured datatypes in XML. Subtyping is then defined with rather complex tree-inclusion properties. It turns out, however, that subtyping can still be decided efficiently with the help of an algorithm originally described by Antimirov. The master thesis of Stefan Hohenadel is an implementation of this algorithm and he will give us an overview in the course of this seminar.

presented by Stefan Hohenadel

R-Trees: A Dynamic Index Structure for Spatial Searching

Similar to grid files, R-Trees (and their variant the R+-Trees) support queries on multi-dimensional data. While grid files are primarily designed for point data, R-Trees support objects in multidimensional space natively. R-Trees are an extension of the one-dimensional B+-Trees and may be used for data of any dimension.

presented by Gabriele Wilke-Müller

(CANCELLED) The Relational Interval Tree: Efficient Support for Interval Data

Particularly in conjuction with time data, many applications demand for an efficient support for the management of interval data. Index structures like R-Trees have been designed for high dimensional data and interval queries but do not behave sufficiently well for one-dimensional intervals. The RI-Tree jumps into this gap and provides support for these intervals on top of an B+-Implementation in any RDBMS. (This talk has been cancelled.)

Efficient and Effective Querying by Image Content

With the increasing amount of multimedia data that is stored in databases (movies, images,...), new types of queries are desired. Instead of searching by file names or given keywords, the database should be searchable by giving a query image (or movie scene, etc.) and asking for multimedia objects similar to it. The database system needs to extract relevant features from the query object and compare it against the database objects. The two main approaches are color features and shape features, both of which are addressed in the given article.

presented by Jan Rittinger

The Grid File: An Adaptable, Symmetric Multikey File Structure

In contrast to traditional index structures like B+-Trees or Hash indices, grid files support multi-dimensional keys. All dimensions are treated symmetrically, allowing for range queries on any (combination of) key(s). Grid files can adapt to insertions and deletions.

presented by Markus Apell

Non First Normal Form Relations

Codd's relational data model requires all relations to be in “at least first normal form”: All attributes have to be atomic values, nested relations are not allowed. For some applications, however, it turned out to be convenient to also allow relations as attributes. Releasing Codd's restriction requires some extensions to the existing relational algebra. Two of these extensions are proposed and discussed in the given articles.

presented by Markus Lindenberg

The Decompositional Storage Model

The relational data model is usually described as relations with an arbitrary number of attributes (“columns”). In 1985 already, Copeland and Khoshafian described a model with binary (“two-column”) relations only. In the past few years this model has become very popular again. The model is not only highly suitable for data mining applications. It has also shown very good performance in latest database developments such as main-memory databases or MEMS based storage devices.

presented by Dominik Morent

Storage Techniques for Object Hierarchies

Object Oriented Databases reflect the object oriented structure of programming languages like C++ or Java. These databases natively support the hierarchical structure of the object oriented model. Some of the storage techniques that are able to support this model are presented in the given articles.

presented by Tobias Sorg

Efficient Join Processing in Streaming Data

Database technology is traditionally used process data that is stored on permanent storage devices like disks, etc. With the latest developments in microelectronics and sensoring, database technology becomes more and more interesting for processing streaming data. Sensors, cameras, etc. produce streams of data tuples at high rates. For efficient processing, these tuples have to be (pre-) processed in real-time. With variations of traditional join operators database technology is used for this task.

presented by Bettina Scherer

Seminar Description

In the early times, when databases were mainly used in financial or supply-chain management systems, “simple” datatypes like numbers or strings have been sufficient to support the application programmers needs.

As the number of database applications grew, and as databases became popular in application domains that had not typically used databases, customers demanded specific datatypes for their applications. Today's databases store images, geographical data, web pages, etc.

Supporting these datatypes, however, does not simly mean to store them in data structures like BLOBs (binary large objects) or large text fields. The database system has to provide specific access methods, like geographic region queries or similarity searches in images or large texts.

This seminar will discuss some storage structures and access methods to provide these features. Many of them already found their way into commercial database systems, while others might still require more detailed research.

Contacts