Search

Technical report TR98-01. In this paper we present a type system that combines inclusion and parametric polymorphism with behaviors (multi-methods) and precise function typing. Type declarations allow user-definable variance specification of type parameters and user-definable subtyping between types of different kind. Our approach involves use of type specification logic which translates type specifications into types. Types are computable values. Type computation of types generated by the logic results in precise function and behavior typing. As a proof of concept, a toy language with its syntax, semantics, and subject reduction theorem is presented. | TRID-ID TR98-01

Technical report TR97-01. Declarative query languages are an important feature of database management systems and have played an important role in their success. As database management technology enters the multimedia information system domain, the availability of query languages for multimedia applications will be equally important. However, one common problem with currently existing multimedia query languages is their lack of generality. They are designed either for a certain medium (e.g. images) or special applications (e.g. medical, geographical information systems). We describe general multimedia queries based on the ODMG's Object Query Language (OQL) and TIGUKAT Query Language (TQL). In order to capture the temporal and spatial relationships in multimedia data, both OQL and TQL are extended by a set of multimedia primitives. These extended OQL and TQL also include functions for query presentation. We illustrate the extended language features by query examples. | TRID-ID TR97-01

Technical report TR96-05. In this paper we consider various spatial relationships that are of general interest for retrieving data from multimedia databases. We present a unified representation of spatial objects for both topological and directional relations. Such a representation is based on Allen's temporal interval algebra. We also present a set of spatial inference rules, which allow us to make heterogeneous spatial relation deductions from existing directional and topological relations. For example, if we know A north of B, B overlap with C, and C north of D, then we derive A above D. Since all the rules are propositional Horn clauses, they can be easily integrated into any multimedia database by using either a simple inference engine or a lookup table. | TRID-ID TR96-05

Technical report TR96-12. Modeling moving objects has become a topic of increasing interest in the area of video databases. Two key aspects of such modeling are object spatial and temporal relationships. In this paper we introduce an innovative way to represent the trajectory of a single moving object and the relative spatio-temporal relations between multiple moving objects. The representation supports a rich set of spatial topological and directional relations. It also supports both quantitative and qualitative user queries about moving objects. Algorithms for matching trajectories and spatio-temporal relations of moving objects are designed to facilitate query processing. These algorithms can handle both exact and similarity matches. We also discuss the integration of our moving object model, based on a video model, in an object-oriented system. Some query examples are provided to further validate the expressiveness of our model. | TRID-ID TR96-12

Technical report TR96-03. Most of the work in modeling time in information systems has concentrated on issues such as support for historical information and providing query facilities to manipulate such information. In doing so, some simplistic view of the underling nature of time has been assumed. However, the domain of time is far from being simplistic. In this paper, we outline the various issues which arise in modeling basic temporal entities and propose solutions to these issues. More specifically, we note that the nature of temporal information can either be anchored (e.g., October 25, 1995) or unanchored (e.g., week), and is usually available in multiple granularities (e.g., the airline flight departure and arrival times are usually given in minutes, while the history of the salary of an employee is usually recorded in days). Physical temporal information also needs to be represented in a manner so as to be human readable. This is achieved using calenders. In this work, we show how both anchored and unanchored temporal entities are represented within the context of calenders. We discuss how calenders provide relationships between multiple granularities and facilitate the conversion of anchored and unanchored times from one granularity to another. We also give the semantics of various operations on anchored and unanchored times. | TRID-ID TR96-03

Technical report TR96-06. Video modeling has become a topic of increasing interest in the area of multimedia research. One of the key aspects in the video medium is spatial relationships. In this paper we propose a spatial representation, based on the temporal interval algebra, for specifying the spatial semantics of video data. Based on such a representation, a set of comprehensive spatial relationships for salient objects are defined in supporting qualitative and quantitative spatial properties. Further, both topological and directional spatial relationships are captured within the proposed model. We present a novel way of incorporating the spatial model into a video model, called a common video object tree, and integrating the abstract video model into an objectbase management system which has rich multimedia temporal operations. The integrated video objectbase management system supports a broad range of spatial queries and is extensible, thus allowing the easy incorporation of new features into the system. Our focus here is in supporting different types of spatial queries including direct spatial queries, hybrid spatial queries, complex spatial queries, computational spatial queries, and temporal spatial queries. The integrated model is further enhanced by a spatial inference engine. The powerful expressiveness of our video model are validated by many concrete query examples. | TRID-ID TR96-06

Technical report TR95-25. Declarative query languages are an important feature of database management systems and have played an important role in their success. As database management technology enters the multimedia information system area, the availability of special-purpose query languages for multimedia applications will be equally important. In this report, we survey multimedia query languages and query models. Particularly, we look at those systems from the point of view of well-defined queries, fuzzy queries, visual queries, and query presentations. Several research issues, such as generic multimedia query languages, incremental queries, fuzzy queries, spatio-temporal queries, feature storage and organization, are also identified. In our opinion these are vital issues for the success and development of a multimedia query language. | TRID-ID TR95-25

Technical report TR95-13. In this work, we present a uniform behavioral temporal object model which includes a rich and extensible set of types and behaviors to support various notions of time. Our temporal model supports the continuous and discrete domains of time. It also supports various specifications of time, namely, time instants, time intervals and time spans. Two issues that frequently arise in real-world applications which deal with temporal information are the need to consistently store and operate on temporal information that is comprised of different granularities, and the ability to represent indeterminate temporal information. Temporal indeterminacy arises when we know for certain that an event did occur, but exactly when it occured is unknown. Our model provides a uniform framework that supports different granularities of time and temporal indeterminacy. We show how different granularities can be converted to each other, and how this leads to temporal indeterminacy. We further show how continuous and discrete indeterminate time intervals, spans and instants are consistently modeled in our framework. | TRID-ID TR95-13

Technical report TR95-19. The role of indexing in query optimization is well-understood in the database community. Indexes enable efficient access to a subset of a database. There have been many studies on indexing within the context of relational database management systems (RDBMS). The most popular indexing techniques are based on B-trees. However, these index structures do not apply for images in Multimedia Database Systems (MMDBS). Some novel index structures to retrieve images have been proposed. In this report, we discuss some issues concerning these advanced indexing techniques, and report the results. | TRID-ID TR95-19

Technical report TR94-16. We describe the design of a multimedia database for a distributed news-on-demand multimedia information system. News-on-demand is an application that utilizes broadband network services to deliver news articles to subscribers in the form of multimedia documents. Different news providers insert articles into the database, which is then accessed by remote users over a broadband network. Multimedia documents are composite objects where the component objects have spatial and temporal relationships which need to be captured in the database. Modeling of multimedia documents involves three issues: (1) modeling of individual document components (i.e., monomedia objects such as text, images, etc), (2) modeling of the document structure, and (3) modeling of the presentation structure. We take an object- oriented approach to dealing with these issues. Within (1), our research has so far concentrated on text. We use an annotation based scheme where entire text is stored as a single document and the formatting mark-ups are represented as annotations on the text. To model the structure of multimedia news documents, we follow the SGML/HyTime international standard by designing a document type declaration (DTD) for multimedia news articles. We build an object oriented model of multimedia news documents based on this DTD. Finally, we model the presentational aspects (e.g., fonts, number of columns, playing of audio and video) as objects and store them in the database. | TRID-ID TR94-16

Technical report TR94-15. In this paper we describe an implementation of a temporal relational database management system based on attribute timestamping. For this purpose we modify an existing software which supports set-valued attributes. The algebraic language of the system includes relational algebra operators, restructuring operators and temporal operators. We use this system to carry out a performance evaluation of different types of temporal databases: databases using attribute timestamping, databases using tuple timestamping where relations are in temporal normal form and databases using tuple timestamping where a single relation is used. We run sample queries against these types of temporal databases and measure processing time of these queries. This study verifies that the major performance trade off is between the restructuring (unpack) operation needed in databases using attribute timestamping and the join operation needed in databases using tuple timestamping. Furthermore, keeping all temporal tuples in one single relation does not prove to be an effective alternative. | TRID-ID TR94-15

Technical report TR93-01. The establishment of a formal object model provides a theoretical foundation to investigate other objectbase features such as query processing. In this report, we present an extensible uniform behavioral object query model for the TIGUKAT(*) object management system. The TIGUKAT object model (see TR92-14) is purely behavioral in nature, supports full encapsulation of objects, defines a clear separation between primitive components such as types, classes, collections, behaviors and functions, and incorporates a uniform semantics over objects which makes it a favorable basis for an extensible query model. Every concept that can be modeled in TIGUKAT has the uniform semantics of a first class object with well-defined behavior. Following this semantics, queries are modeled as type and behavioral extensions to the base object model, thus incorporating queries as an extensible part of the model itself. The complete query model definition presented in this report includes: the type and behavior extensions to the base model; a formal object calculus with a logical foundation that introduces a function symbol to incorporate the behavioral paradigm of the object model into the calculus; a behavioral/functional object algebra with a comprehensive set of object-preserving and object-creating operators; an SQL-like ad hoc query language (TQL) for user-level retrieval of objects; user-level definition and control languages (TDL and TCL) for defining new types, classes, behaviors, functions, etc., and for controlling an interactive session with the query processor; a rigorous definition of safety based on the evaluable class of queries which is arguably the largest decidable subclass of the domain independent class; a notion of completeness that includes reductions between the algebra and calculus that prove their equivalence and a reduction from the user-level language to the calculus; and in addition to the formal aspects, we give a complete algorithmic translation from the calculus into the object algebra. At this point, the algebraic expressions can be optimized and an execution plan can be generated and passed to the storage manager for processing. A prototype implementation of the object model on top of the EXODUS storage manager is ongoing. We are implementing a compiler for the user language and an extensible query optimizer for the algebra. Furthermore, we are developing a view manager, with update semantics, for the model. *TIGUKAT (tee-goo-kat) is a term in the language of the Canadian Inuit people meaning \"objects.\" The Canadian Inuits, commonly known as Eskimos, are native to Canada with an ancestry originating in the Arctic regions of the country. | TRID-ID TR93-01

Technical report TR92-14. Object-oriented computing is influencing many areas of computer science including software engineering, user interfaces, operating systems, programming languages and database systems. The appeal of object-orientation is attributed to its higher levels of abstraction for modeling real world concepts, its support for incremental development and its potential for interoperability. Despite many advances, object-oriented computing is still in its infancy and a universally acceptable definition of an object-oriented data model is virtually nonexistent, although some standardization efforts are underway. This report presents the TIGUKAT(*) object model definition that is the result of an investigation of object-oriented modeling features which are common among earlier proposals, along with some distinctive qualities that extend the power and expressibility of this model beyond others. The literature recognizes two perspectives of an object model: the structural view and the behavioral view. Most object-oriented formalisms have concentrated on one or the other of these two perceptions. The TIGUKAT object model (i) favors formal specifications for both the behavioral and structural components, and (ii) shows an integration of the two components into a complete model definition. Furthermore, the model emphasizes (iii) a clean separation and precise definition of object modeling features which are usually bundled and only intuitively defined in other models, and (iv) a uniform approach to object modeling which encompasses all information, including meta-data, as objects within the primitive definitions. The establishment of a formal object model provides a theoretical foundation from which investigations of other object database features will be pursued. The first of these involves the definition of an object query model with complete calculus and algebra specifications, including an equivalence transformation proof between the two. Based on the query model, object views and view management with update semantics will be examined. The intention is to incorporate very powerful and dynamic object definition and manipulation language features into the model. In parallel with this, a dynamic schema evolution policy will be developed for integrating new types into the model. We are currently in the process of implementing the model presented in this report to establish a workable software base with the long range goal of developing a full-featured object database management system. *TIGUKAT (tee-goo-kat) is a term in the language of the Canadian Inuit people meaning \"objects.\" The Canadian Inuits, commonly known as Eskimos, are native to Canada with an ancestry originating in the Arctic regions of the country. | TRID-ID TR92-14

Stream Reasoning refers to inference approaches and deduction mechanisms which are concerned with providing continuous inference capabilities over dynamic data. The paradigm shift from current batch-like approaches towards timely and scalable stream reasoning leverages the natural temporal order in data streams and applies windows-based processing to complex deduction tasks that go beyond continuous query processing such as those involving preferential reasoning, constraint ptimization, planning, uncertainty, non-monotonicity, non-determinism, and solution enumeration.