Abstract BBoxDB Streams is a distributed stream processing system, which allows the handling of multi-dimensional data. Multi-dimensional streams consist of n-dimensional elements, such as position data (e.g., two-dimensional positions of cars or three-dimensional positions of aircraft). The software is an enhancement of BBoxDB, a distributed key-bounding-box-value store that allows the handling of n-dimensional big data. BBoxDB Streams supports continuous range queries and continuous spatial joins; n-dimensional point and non-point data are supported. Operations in BBoxDB Streams are performed primarily on the bounding boxes of the data. With user-defined filters (UDFs), custom data formats can be decoded, and the bounding box-based operations are refined (e.g., a UDF decodes and performs intersection tests on the real geometries of WKT encoded stream elements). A unique feature of BBoxDB Streams is the ability to perform continuous spatial joins between stream elements and previously stored multi-dimensional big data. For example, the dynamic position of a car can be efficiently joined with the static spatial data of a street network.

Abstract We propose a simple model for distributed query processing based on the concept of a distributed array. Such an array has fields of some data type whose values can be stored on different machines. It offers operations to manipulate all fields in parallel within the distributed algebra. The arrays considered are one-dimensional and just serve to model a partitioned and distributed data set. Distributed arrays rest on a given set of data types and operations called the basic algebra implemented by some piece of software called the basic engine. It provides a complete environment for query processing on a single machine. We assume this environment is extensible by types and operations. Operations on distributed arrays are implemented by one basic engine called the master which controls a set of basic engines called the workers. It maps operations on distributed arrays to the respective operations on their fields executed by workers. The distributed algebra is completely generic: any type or operation added in the extensible basic engine will be immediately available for distributed query processing. To demonstrate the use of the distributed algebra as a language for distributed query processing, we describe a fairly complex algorithm for distributed density-based similarity clustering. The algorithm is a novel contribution by itself. Its complete implementation is shown in terms of the distributed algebra and the basic algebra. As a basic engine the Secondo system is used, a rich environment for extensible query processing, providing useful tools such as main memory M-trees, graphs, or a DBScan implementation.

Moving objects databases are specialized for processing objects that have attributes which change over time. A moving region is a powerful data type in this context, describing a region which changes shape and position over a specified time interval. This data type is, for example, a suitable model for natural phenomena like hurricanes, clouds or forest fires. Several operations exist to process and analyze moving regions in moving objects databases. One useful operation is to determine which areas are covered for which time span during the movement of moving regions to calculate, for example, which areas are affected by a hurricane for a certain period of time. This paper presents a set of operations that can be used to analyze the spatiotemporal coverage behavior of a moving region to determine which regions are covered for shorter or longer than a given time, or which parts are covered for a specified time interval. Furthermore, the coverage duration of a single point and the average coverage duration for a given region can be determined.

Moving objects databases store and process objects with a focus on their spatiotemporal behaviour. To achieve this, the model of the data must be suitable to efficiently store and process moving objects. Currently, a unit-based model is widely used, where each moving object is divided into one or more time intervals, during which the object behaves uniformly. This model is also used for a data type called moving regions, which resembles moving and shape changing regions as, for example, forest fires or cloud fields. However, this model struggles to support operations like union, difference or intersection of two moving regions; the resulting objects are unnecessarily bloated and uncomfortable to handle because the resulting number of units is generally very high. In this paper, an alternative model for moving regions is proposed, which is based on polyhedra. Furthermore, this work develops an isomorphism between moving regions and polyhedra including all relevant operations, which has the additional advantage that several implementations for those are already readily available; this is demonstrated by a reference implementation using the existing and well-tested Computational Geometry Algorithms Library (CGAL).

BBoxDB is a distributed key-bounding-box-value store which is capable of handling large scale n-dimensional data. Unlike existing key-value stores, each value is stored together with a bounding box which describes the location of the value in an n-dimensional space. BBoxDB splits large datasets automatically and spreads them across a cluster of nodes. The software works primarily on the bounding boxes of the stored data; operations like range queries or joins take only the bounding boxes of the data into consideration. In version 0.9.1, we implemented support for user defined filters (UDF) in BBoxDB; UDFs operate on the real values of the data. In this paper, we describe this novel feature for the first time. As an example, a UDF is developed in this paper which is capable of handling GeoJSON encoded data. The UDF consists only of a few lines of code and turns the generic distributed datastore BBoxDB into a specialized system that is capable of processing large scale GeoJSON encoded datasets. Operations like spatial joins or range queries on the real geometries of the data become possible. During our demonstration, we show the implementation of the UDF and perform range queries and spatial joins. The used dataset contains spatial data of the whole world and is obtained from the Open Street Map project. For visualization, the GUI of BBoxDB was extended in a way that spatial queries can easily be executed. Using the GUI, query results can be interactively explored; they are shown as an overlay on a map dynamically fetched from the Open Street Map project.

The research field of moving objects has been quite active in the past 20 years. The recording of position data becomes easy and huge amounts of mobile data are collected. Moving objects databases represent time-dependent objects and support queries with spatial and temporal constraints. In this paper we provide the vision of a multi-model and intelligent moving objects database. The goal is to enhance the data management of moving objects by providing extensive data models for different applications and fusing artificial intelligence techniques. Toward this goal, we propose how to develop corresponding modules and integrate them into the system to achieve the next-generation moving objects database.

BBoxDB is a distributed and highly available key-bounding-box-value store which enhances the classical key-value data model with an axis-parallel bounding box. The bounding box describes the location of the values in an n-dimensional space, and enables BBoxDB to efficiently distribute multi-dimensional data across a cluster of nodes. Well-known geometric algorithms (such as the K-D Tree) are used to create distribution regions (multi-dimensional shards). Distribution regions are created dynamically, based on the stored data. BBoxDB stores data of multiple tables co-partitioned, which enables efficient distributed spatial joins. Spatial joins on co-partitioned tables can be executed without data shuffling between nodes. A two-level index structure is employed to retrieve stored data quickly. We demonstrate the interaction with the system, the dynamic creation of distribution regions and the data redistribution feature of BBoxDB.

Moving object databases are designed to store and process spatial and temporal object data. An especially useful moving object type is a moving region, which consists of one or more moving polygons suitable for modeling the spread of forest fires, the movement of clouds, spread of diseases and many other real-world phenomena. Previous implementations usually allow a changing shape of the region during the movement; however, the necessary restrictions on this model result in an inaccurate interpolation of rotating objects. In this paper, we present an alternative approach for moving and rotating regions of fixed shape, called Fixed Moving Regions, which provide a significantly better model for a wide range of applications like modeling the movement of oil tankers, icebergs and other rigid structures. Furthermore, we describe and implement several useful operations on this new object type to enable a database system to solve many real-world problems, as for example collision tests, projections and intersections, much more accurate than with other models. Based on this research, we also implemented a library for easy integration into moving objects database systems, as for example the DBMS Secondo (1) (2) developed at the FernUniversität in Hagen.

Motivated by the trend of providing comprehensive knowledge about trajectory data, we study multi-attribute trajectories each of which contains a sequence of time-stamped locations and a set of characteristic attributes. This enriches the data representation by providing a comprehensive description of moving objects and thus enables new types of queries on moving object trajectories. In this paper, we consider answering range queries that return trajectories (i) containing particular attribute values and (ii) passing a certain area during the query time. We integrate standard trajectories and attributes into one unified framework and propose an index structure as well as the query algorithm. The structure is general and flexible in terms of handling both multi-attribute trajectories and standard trajectories, answering a range of queries and supporting update-intensive applications. The evaluation is conducted in a prototype database system and experimental results demonstrate that our method outperforms alternative methods by a factor of 3-10 on a data set of one million real trajectories and synthetic attribute values.

The widespread use of GPS-enabled devices has led to huge amounts of trajectory data. In addition to location and time, trajectories are associated with descriptive attributes representing different aspects of real entities, called multi-attribute trajectories. This comes from the combination of several data sources and enables a range of new applications in which users can find interesting trajectories and discover potential relationships that cannot be determined solely based on GPS data. In this demo, we provide the motivation scenario and introduce a system that is developed to integrate standard trajectories (a sequence of timestamped locations) and attributes into one unified framework. The system is able to answer a range of interesting queries on multi-attribute trajectories that are not handled by standard trajectories. The system supports both standard trajectories and multi-attribute trajectories. We demonstrate how to form queries and animate multi-attribute trajectories in the system. To our knowledge, existing moving objects prototype systems do not support multi-attribute trajectories.

The recent proliferation of positioning devices has boosted the requirement for efficient methods of processing and analyzing large amounts of recorded movement data. Besides the geographic position, for many application domains there is more relevant time-dependent information such as speed, elevation, street names, or transportation modes, depending on the kind of moving object and on the evaluation purpose. In this paper, we present an application of a new framework that efficiently analyzes datasets with several time-dependent attributes of different types, using a highly flexible and expressive pattern language. In contrast to previous variants, the semantics of the language has been changed to make it more expressive and flexible, and the efficiency has been improved.

Lately, the amount of mobility data recorded by GPS-enabled (and other) devices has increased drastically, entailing the necessity of efficient processing and analysis methods. In many cases, not only the geographic position, but also additional information according to the purpose of the evaluation are traced and/or generated. In this paper, we present an application of a framework for analyzing datasets with several time-dependent attributes. This can be considered as a major extension of our previous work, a comprehensive framework for pattern matching on symbolic trajectories. For an efficient processing of different data types, a variable number of corresponding index types are applied. We demonstrate the expressiveness and efficiency with the help of a sophisticated pattern and a dataset consisting of GPS-recorded animal data and additional geological and meteorological information.

Recording mobility data with GPS-enabled devices, e.g., smart phones or vehicles, has become a common issue for private persons, companies, and institutions. Consequently, the requirements for managing these enormous datasets have increased drastically, so trajectory management has become an active research field. In order to avoid querying raw trajectories, which is neither convenient nor efficient, a symbolic representation of the geometric data has been introduced.

Parallel Secondo scales up the capability of processing extensible data models in Secondo. It combines Hadoop with a set of Secondo databases, providing almost all existing SECONDO data types and operators. Therefore it is possible for the user to convert large-scale sequential queries to parallel queries without learning the Map/Reduce programming details. This paper demonstrates such a procedure. It imports the data from the project OpenStreetMap into Secondo databases to build up the urban traffic network and then processes network-based queries like map-matching and symbolic trajectory pattern matching. All involved queries were stated as sequential expressions and time-consuming in single-computer Secondo. However, they can achieve an impressive performance in Parallel Secondo after being converted to the corresponding parallel queries, even on a small cluster consisting of six low-end computers.

This seminar overviews recent research on novel data models for the advanced representation of mobility data encompassing semantic and contextual information.

Symbolic trajectories is a novel data model recently proposed for the modeling and querying of temporally annotated sequences of symbolic descriptions, representing e.g. transportation means, places of interest, and so forth. Unlike geometric trajectories, symbolic trajectories capture the thematic dimension of movement. In this demonstration, we illustrate a practical approach to the querying of hybrid trajectories, combining the symbolic and geometric dimension in a multidimensional trajectory. The system runs on the Secondo moving object database. The multi-dimensional trajectories are obtained from the GeoLife dataset.

This paper presents a hybrid parallel processing system, named Parallel Secondo. It combines the Hadoop framework and a set of single-computer Secondo databases, in order to introduce the mobility data procedures into the parallel processing community, and vice versa. The system keeps the front-end and the executable language of Secondo to allow the users to state their parallel queries like common sequential queries. Besides, a set of auxiliary scripts is provided so as to make it easier to manage the system no matter how large the underlying cluster is, and keep the Hadoop platform as a transparent level of the system. Further, a parallel data model is also proposed in this paper to encapsulate all available Secondo data types and operators. Thereby, it is able to transform any Secondo sequential query to its corresponding parallel expression. For instance, all example queries in the moving objects database benchmark BerlinMOD are transformed, and two of them are demonstrated in this paper. In the last evaluations, this paper illustrates that Parallel Secondo is not only a practical but also an efficient system. For queries involving large amounts of data, it performs both linear speed-up and scale-up.

In this paper, we introduce a benchmark called GMOBench that aims to evaluate the performance of a database system managing moving objects in different environments. In real life, people's movement can cover several environments rather than one, for example, Indoor → Walk → Bus. Consequently, the complete trip needs to be managed by a database system in order to support novel queries. Since existing methods are limited to one environment, new technologies are developed in a database system that is able to manage generic moving objects. A meaningful analysis and evaluation of such a system necessitates a comprehensive benchmark. GMOBench is settled in a realistic scenario which comprises (1) a data generator with the capability of creating a scalable set of trips representing the complete movement of humans (both indoor and outdoor); (2) a set of carefully designed and benchmark queries. We create the benchmark data in such a way that the dataset can mirror important characteristics and real world distributions of human mobility. We perform an extensive experimental study on comprehensive datasets to evaluate the performance of the system. The results demonstrate the effectiveness and efficiency of our approaches.

Moving objects representing movement in all real world environments (e.g., road network, bus network, indoor) should be managed in a database system, for the reason that a person's trip can cover several environments rather than one. GMOD (Generic Moving Objects Database) is a database system to manage moving objects that (1) travel through different environments; (2) contain multiple transportation modes such as Car → Walk → Indoor. To evaluate the performance of GMOD, one needs a comprehensive and scalable dataset consisting of all available environments and moving objects. Due to the difficulty of gaining real datasets, in this paper we present a tool called MWGen that creates the overall space for moving objects, composed of the following environments: road network, bus network, metro network, pavement areas and indoor. Based on roads, all outdoor environments are created. The indoor environment consisting of a set of buildings is established from public floor plans. Moving objects are generated based on trip planning where a navigation algorithm through different environments is developed. We are able to produce moving objects integrated with multiple transportation modes. In addition, trip planning in a single environment is also available, e.g., shortest path for pedestrians, indoor navigation. The generated data, including all infrastructures and moving objects, are managed by GMOD. We conduct an extensive performance study to evaluate MWGen on two real road datasets and a set of public floor plans.

In this demonstration, we introduce a system that is able to manage moving objects in all real world environments, e.g., road network, bus network and indoor. The complete trip of a person is managed by the system such as Walk, Car, Walk , and Indoor , where the precise locations of both outdoor and indoor movements are represented. Trajectories located in several environments are integrated into the same framework. The system supports the shortest path searching for start and end locations being in different environments, for example, from a room to a bus stop. A comprehensive and scalable set of moving objects is generated to simulate human movement in practice. Optimization methods are developed to efficiently answer novel queries regarding transportation modes and mobile environments. Most of these queries are not supported by existing methods because of the limitation of data representation.

In previous work, we have proposed a tool for Spatiotemporal Pattern Query. It matches individual moving object trajectories against a given movement pattern. For example, it can be used to find the situations of Missed Approach in ATC data (Air Traffic Control systems, used for tracking the movement of aircrafts), where the landing of the aircraft was interrupted for some reason. This tool expresses the pattern as a set of predicates that must be fulfilled in a certain temporal order. It is implemented as a Plugin to the Secondo DBMS system. Although the tool is generic and flexible, domain expertise is required to formulate and tune queries. The user has to decide the set of predicates, their arguments, and the temporal constraints that best describe the pattern. This paper demonstrates a novel solution where a Visual Analytics system, V-Analytics, is used in integration with this query tool to help a human analyst explore such patterns. The demonstration is based on a real ATC data set.

Moving objects with multiple transportation modes (e.g., Car, Bus, Walk) can be represented by the reference method where the location is mapped to infrastructure objects, e.g., roads, buses, pavements. A scalable dataset is required to evaluate the performance of a database system managing these moving objects. To produce multimodal moving objects, infrastructure objects are essentially needed. Due to the major challenge of gaining real datasets, in this demonstration we propose a method create these infrastructure objects for different environments including pavement areas, bus network and indoor just from a given road network and some floor plans. An indoor viewer is also implemented in a database system for visualizing 3D indoor moving objects and trajectories. The work is to be used for evaluating the performance of a database system managing generic moving objects.

In this paper, we demonstrate our results of designing and implementing spatiotemporal pattern queries. That is, one can specify temporal order constraints on the fulfillment of predicates on moving objects. Compared with other approaches, our approach is not restricted in terms of the types of moving object or the sets of predicates. Our work covers the language integration in SQL, the evaluation of the queries, and the integration with the query optimizer. We provide a complete implementation in C++ and Prolog in the context of the SECONDO platform. The implementation is made publicly available online as a SECONDO Plug in We have also made available automatic scripts for executing the examples in this demonstration.

Traditional indexing techniques are not well suited for complex data types such as spatial, spatio-temporal, and multimedia data types, where an instance is a composite of multiple components. In this paper we propose two indexing techniques that allow the parts of a composite object to be indexed separately, called multiple entry indexing and double indexing. We present the implementation of these approaches in the SECONDO extensible database system. The improvements in terms of performance of both approaches presented in this paper are shown in an experimental evaluation.

Representing descriptions of movements in databases and querying them is a basic capability required in mobile data management. In this article we present a prototype of a moving objects database system and an environment for building such prototypes called Secondo. The Secondo environment is freely available on the Web. The prototype of a moving objects DBMS is based on the concept of spatio-temporal data types, providing abstractions such as moving point and moving region. These can represent time dependent positions or objects with extent, respectively, such as vehicles or forest fires. Moving point and moving region are offered as data types with suitable operations. We explain the basic idea, the distinction between abstract and discrete model, and the design principles for an abstract model with carefully designed types and operations. The discrete model defines finite representations for all data types and can serve as a blueprint for implementation.

Efficient evaluation of spatial queries is an important issue in spatial database. Among spatial operations, spatial join is very useful, intersection being the most common predicate. However, the exact intersection test of two spatial objects is the most time-consuming and I/O-consuming step in processing spatial joins. On the other hand, the use of approximations can reduce the need for examining the exact geometry of spatial objects in order to find the intersecting ones. This work proposes a new raster approximation (Three-Color Raster Signature - 3CRS) for representing different data types (polygons, polylines and points), and to be used as filter in the second step of the Multi-Step Query Processor. We have also executed experimental tests over real datasets, the results having demonstrated the effectiveness of our approach.

In the real world, lots of objects with changing position can be found. Some of them repeat the same movement several times, called periodic movements. Examples include airplanes, trains, planets, and marine turtles. This paper describes a model for representing the periodic movements to be stored in a database system, exploiting the information about the repetitions. The model is generic enough to represent any kind of movement, not being restricted to objects with repetitions in their movement. We present algorithms to detect the repetitions and to convert to the periodic representation as well as the implementation of some operations on such representation. We show, in an experimental evaluation against the so-called flat representation, that the approach presented in this paper significantly improves the performance of query processing in a database system when dealing with objects with some periodic movement. We also show that, for the worst case where the objects do not follow any periodic movement at all, our approach still performs acceptably.

Representing descriptions of movements in databases and querying them is a basic capability required in mobile data management. In this demonstration, we show for the first time a prototype implementing a data model and query language for moving objects (trajectories) completely integrated into a DBMS environment, including query optimization and user interface issues such as animation.

This paper describes a data model for fuzzy spatial objects implemented as an algebra module in SECONDO. Furthermore, the graphical representation of such objects is discussed.

The goal of SECONDO is to provide a "generic" database system frame that can be filled with implementations of various DBMS data models. SECONDO was intended originally as a platform for implementing and experimenting with new kinds of data models, especially to support spatial, spatio-temporal, and graph database models. We now feel, SECONDO has a clean architecture, and it strike a reasonable balance between simplicity and sophistication. Since all the source code is accessible and to a large extent comprehensible for students, we believe it is also an excellent tool for teaching database architecture and implementation concepts. SECONDO runs on Windows, Linux, and Solaris platforms, and consists of three major components SECONDO kernel, optimizer, and graphical user interface.

Presents SECONDO, a new generic environment supporting the implementation of database systems for a wide range of data models and query languages. On the one hand, this framework is more flexible than common extensible and object-relational systems, offering the full extensibility of second-order signatures, which is the formal basis for data and query language definitions in SECONDO. On the other hand, it is much more complete and structured than database system toolkits. Extensibility is provided by the concept of algebra modules defining and implementing new types (type constructors, in fact) and operators. Support functions are used to register them with the system frame. After a review of second-order signatures' essentials, this paper presents the system functionality, given by a uniform set of user commands that are valid for all data models, and the extensible system architecture. All common DBMS features are implemented in the system frame; only purely data model-dependent functionality is coded in the algebra modules, supported by a variety of tools. Furthermore, we describe the key strategies for extensible query processing in the SECONDO environment and explain the structure of the algebra modules.

In implementations of non-standard database systems, large objects are often embedded within an aggregate of different types, i.e. a tuple. For a given size and access probability of a large object, query performance depends on its representation: either inlined within the aggregate or swapped out to a separate object. Furthermore, the implementation of complex data models often requires nested large objects, and access performance is highly influenced by the clustering strategy followed to store the resulting tree of large objects. In this paper we describe a large object extension which automatically clusters nested large objects. A rank function is developed which indicates the suitability of a large object being inserted into a given cluster. We present two clustering algorithms of different run-time complexity, both using the rank function, and a series of simulations is performed to compare them to each other as well as to two trivial ones. One of the algorithms proves to compute the most efficient clustering in all tests.

Spatio-temporal databases deal with geometries changing over time. The goal of our work is to provide a DBMS data model and query language capable of handling such time-dependent geometries, including those changing continuously that describe moving objects . Two fundamental abstractions are moving point and moving region , describing objects for which only the time-dependent position, or position and extent, respectively, are of interest. We propose to present such time-dependent geometries as attribute data types with suitable operations, that is, to provide an abstract data type extension to a DBMS data model and query language. This paper presents a design of such a system of abstract data types. It turns out that besides the main types of interest, moving point and moving region, a relatively large number of auxiliary data types are needed. For example, one needs a line type to represent the projection of a moving point into the plane, or a “moving real” to represent the time-dependent distance of two points. It then becomes crucial to achieve (i) orthogonality in the design of the system, i.e., type constructors can be applied unifomly; (ii) genericity and consistency of operations, i.e., operations range over as many types as possible and behave consistently; and (iii) closure and consistency between structure and operations of nontemporal and related temporal types. Satisfying these goal leads to a simple and expressive system of abstract data types that may be integrated into a query language to yield a powerful language for querying spatio-temporal data, including moving objects. The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL. The paper offers a precise and conceptually clean foundation for implementing a spatio-temporal DBMS extension.

Observing that networks are ubiquitous in applications for spatial databases, we define a new data model and query language that especially supports graph structures. This model integrates concepts of functional data modeling with order-sorted algebra. Besides object and data type hierarchies, graphs are available as an explicit modeling tool, and graph operations are part of the query language. Graphs have three classes of components, namely, nodes, edges, and explicit paths. These are at the same time object types within the object type hierarchy and can be used like any other type. Explicit paths are useful because real-world objects often correspond to paths in a network. Furthermore, a dynamic generalization concept is introduced to handle heterogeneous collections of objects in a query. In connection with spatial data types, this leads to powerful modeling and querying capabilities for spatial databases, in particular for spatially embedded networks such as highways, rivers, public transport, and so forth. We use multilevel order-sorted algebra as a formal framework for the specification of our model. Roughly spoken, the first-level algebra defines types and operations of the query language, whereas the second-level algebra defines kinds (collections of types) and type constructors as functions between kinds, and so provides the types that can be used at the first level.>

We propose a framework for the specification of extensible database systems.A particular goal is to implement a software component for parsing and rule-based optimization that can be used with widely varying data models and query languages as well as representation and query processing systems.The key idea is to use second-order signature (and algebra), a system of two coupled many-sorted signatures, where the top-level signature offers kinds and type constructors and the bottom-level signature provides polymorphic operations over the types defiied as terms of the top level.Hence the top level can be used to define a data or representation model and the bottom level to describe a query algebra or a query processing algebra.We show the applicability of this framework by examples drawn from relational modeling and query processing.

Gral is an extensible database system, based on the formal concept of a many-sorted relational algebra. Many-sorted algebra is used to define any application's query language, its query execution language, and its optimiztion rules. In this paper we describe Gral's optimization component. It provides (1) a sophisticated rule language—rules are transformations of abstract algebra expressions, (2) a general optimization framework under which more specific optimization algorithms can be implemented, and (3) several control mechanisms for the application of rules. An optimization algorithm can be specified as a series of steps. Each step is defined by its own collection of rules together with a selected control strategy. The general facilities are illustrated by the complete design of an example optimizer—in the form of a rule file—for a small nonstandard query language and an associated execution language. The query language includes selection, join, ordering, embedding derived values, aggregate functions, and several geometric operations. The example shows in particular how the special processing techniques of a geometric database systems, such as spatial join methods and geometric index structures, can be integrated into query processing and optimization of a relational database system. A similar, though larger, optimizer is fully functional within the geometric database system implemented as a Gral prototype.

We describe a data model for structured office information objects, which we generically call “documents,” and a practically useful algebraic language for the retrieval and manipulation of such objects. Documents are viewed as hierarchical structures; their layout (presentation) aspect is to be treated separately. The syntax and semantics of the language are defined precisely in terms of the formal model, an extended relational algebra. The proposed approach has several new features, some of which are particularly useful for the management of office information. The data model is based on nested sequences of tuples rather than nested relations. Therefore, sorting and sequence operations and the explicit handling of duplicates can be described by the model. Furthermore, this is the first model based on a many-sorted instead of a one-sorted algebra, which means that atomic data values as well as nested structures are objects of the algebra. As a consequence, arithmetic operations, aggregate functions, and so forth can be treated inside the model and need not be introduced as query language extensions to the model. Many-sorted algebra also allows arbitrary algebra expressions (with Boolean result) to be admitted as selection or join conditions and the results of arbitrary expressions to be embedded into tuples. In contrast to other formal models, this algebra can be used directly as a rich query language for office documents with precisely defined semantics.