Temporal and Real-Time Databases: A Survey
---
paper_title: A consensus glossary of temporal database concepts

paper_content:

This document contains definitions of a wide range of concepts specific to and widely used within temporal databases. In addition to providing definitions, the document also includes separate explanations of many of the defined concepts. Two sets of criteria are included. First, all included concepts were required to satisfy four relevance criteria, and, second, the naming of the concepts was resolved using a set of evaluation criteria. The concepts are grouped into three categories: concepts of general database interest, of temporal database interest, and of specialized interest. This document is a digest of a full version of the glossary1. In addition to the material included here, the full version includes substantial discussions of the naming of the concepts.The consensus effort that lead to this glossary was initiated in Early 1992. Earlier status documents appeared in March 1993 and December 1992 and included terms proposed after an initial glossary appeared in SIGMOD Record in September 1992. The present glossary subsumes all the previous documents. It was most recently discussed at the "ARPA/NSF International Workshop on an Infrastructure for Temporal Databases," in Arlington, TX, June 1993, and is recommended by a significant part of the temporal database community. The glossary meets a need for creating a higher degree of consensus on the definition and naming of temporal database concepts.
---
paper_title: The role of time in information processing: a survey

paper_content:

Numerous researchers in a handful of disciplines have been concerned, in recent years, with the special role (or roles) that time seems to play in information processing. Designers of computerized information systems have had to deal with the fact that when an information item becomes outdated, it need not be forgotten. Researchers in artificial intelligence have pointed to the need for a realistic world model to include representations not only for snapshot descriptions of the real world, but also for histories, or the evolution of such descriptions over time. Many logicians have regarded classical logic as an awkward tool for capturing the relationships and the meaning of statements involving temporal reference, and have proposed special "temporal logics" for this purpose. Finally, the analysis of tensed statements in natural language is a principal concern of researchers in linguistics.
---
paper_title: The TSQL2 Data Model

paper_content:

Adding time to the relational model has been a daunting task [Bolour et al. 1982, McKenzie 1986, Soo 1991, Stam & Snodgrass 1988]. More than two dozen time-extended relational data models have been proposed over the last fifteen years [Snodgrass 1992]. Most of these are valid-time models. Each fact in a valid-time relation has associated the time when it is true in the modeled reality. Other models support transaction-time relations where each fact has associated the time when it is current in the database. A few support both valid and transaction time [Ben-Zvi 1982, BhargavaG such models are termed bitemporal. As a whole, these data models are referred to as temporal data models [Jensen et al. 1994].
---
paper_title: Evaluation of relational algebras incorporating the time dimension in databases

paper_content:

The relational algebra is a procedural query language for relational databases. In this paper we survey extensions of the relational algebra that can query databases recording time-varying data. Such an algebra is a critical part of a temporal DBMS. We identify 26 criteria that provide an objective basis for evaluating temporal algebras, Seven of the criteria are shown to be mutually unsatisfiable, implying there can be no perfect temporal algebra, Choices made as to which of the incompatible criteria are satisfied characterize existing algebras Twelve time-oriented algebras are summarized and then evaluated against the criteria. We demonstrate that the design space has in some sense been explored in that all combinations of basic design decisions have at least one representative algebra. Coverage of the remaining criteria provides one measure of the quality of each algebra We argue that all of the criteria are independent and that the criteria identified as compatible are indeed so, Finally, we list plausible properties proposed by others that are either subsumed by other criteria, are not well defined, or have no objective basis for being evaluated. The algebras realize many different approaches to what appears initially to be a straightforward design task.
---
paper_title: On real-time databases: Concurrency control and scheduling

paper_content:

In addition to maintaining database consistency as in conventional databases, real-time database systems must also handle transactions with timing constraints. While transaction response time and throughput are usually used to measure a conventional database system, the percentage of transactions satisfying the deadlines or a time-critical value function is often used to evaluate a real-time database system. Scheduling real-time transactions is far more complex than traditional real-time scheduling in the sense that (1) worst case execution times are typically hard to estimate, since not only CPU but also I/O requirement is involved; and (2) certain aspects of concurrency control may not integrate well with real-time scheduling. In this paper, we first develop a taxonomy of the underlying design space of concurrency control including the various techniques for achieving serializability and improving performance. This taxonomy provides us with a foundation for addressing the real-time issues. We then consider the integration of concurrency control with real-time requirements. The implications of using run policies to better utilize real-time scheduling in a database environment are examined. Finally, as timing constraints may be more important than data consistency in certain hard realtime database applications, we also discuss several approaches that explore the nonserializable semantics of real-time transactions to meet the hard deadlines. >
---
paper_title: A temporal relational model and a query language

paper_content:

Abstract This paper proposes an extension of the relational data model for incorporating temporal semantics of the real world into a database. In this temporal relational model (TRM), the attributes are categorized as synchronous and asynchronous. This categorization leads to the notions of temporal dependency and time normal form. The imposition of time normal form avoids redundancy and retrieval and update anomalies. New relational algebra operations for this model are also discussed. A temporal query language called tsql , which is a superset of sql , has been proposed to retrieve information from time-varying relations. tsql has several new features, which provide extremely powerful query processing capabilities for time-varying relations. The model and the language have numerous applications, where data in their historical form are important.
---
paper_title: A consensus glossary of temporal database concepts

paper_content:

This document contains definitions of a wide range of concepts specific to and widely used within temporal databases. In addition to providing definitions, the document also includes separate explanations of many of the defined concepts. Two sets of criteria are included. First, all included concepts were required to satisfy four relevance criteria, and, second, the naming of the concepts was resolved using a set of evaluation criteria. The concepts are grouped into three categories: concepts of general database interest, of temporal database interest, and of specialized interest. This document is a digest of a full version of the glossary1. In addition to the material included here, the full version includes substantial discussions of the naming of the concepts.The consensus effort that lead to this glossary was initiated in Early 1992. Earlier status documents appeared in March 1993 and December 1992 and included terms proposed after an initial glossary appeared in SIGMOD Record in September 1992. The present glossary subsumes all the previous documents. It was most recently discussed at the "ARPA/NSF International Workshop on an Infrastructure for Temporal Databases," in Arlington, TX, June 1993, and is recommended by a significant part of the temporal database community. The glossary meets a need for creating a higher degree of consensus on the definition and naming of temporal database concepts.
---
paper_title: Relational specifications of infinite query answers

paper_content:

We investigate here functional deductive databases: an extension of DATALOG capable of representing infinite phenomena. Rules in functional deductive databases are Horn and predicates can have arbitrary unary and limited k -ary function symbols in one fixed position. This class is known to be decidable. However, least fixpoints of functional rules may be infinite. We present here a method to finitely represent infinite least fixpoints and infinite query answers as relational specifications . Relational specifications consist of a finite set of tuples and of a finitely specified congruence relation. Our method is applicable to every domain-independent set of functional rules.
---
paper_title: Schema evolution in database systems: an annotated bibliography

paper_content:

Schema Evolution is the ability of a database system to respond to changes in the real world by allowing the schema to evolve. In many systems this property also implies a retaining of past states of the schema. This latter property is necessary if data recorded during the lifetime of one version of the schema is not to be made obsolete as the schema changes. This annotated bibliography investigates current published research with respect to the handling of changing schemas in database systems.
---
paper_title: A consensus glossary of temporal database concepts

paper_content:

This document contains definitions of a wide range of concepts specific to and widely used within temporal databases. In addition to providing definitions, the document also includes separate explanations of many of the defined concepts. Two sets of criteria are included. First, all included concepts were required to satisfy four relevance criteria, and, second, the naming of the concepts was resolved using a set of evaluation criteria. The concepts are grouped into three categories: concepts of general database interest, of temporal database interest, and of specialized interest. This document is a digest of a full version of the glossary1. In addition to the material included here, the full version includes substantial discussions of the naming of the concepts.The consensus effort that lead to this glossary was initiated in Early 1992. Earlier status documents appeared in March 1993 and December 1992 and included terms proposed after an initial glossary appeared in SIGMOD Record in September 1992. The present glossary subsumes all the previous documents. It was most recently discussed at the "ARPA/NSF International Workshop on an Infrastructure for Temporal Databases," in Arlington, TX, June 1993, and is recommended by a significant part of the temporal database community. The glossary meets a need for creating a higher degree of consensus on the definition and naming of temporal database concepts.
---
paper_title: Incomplete Information in Relational Temporal Databases

paper_content:

For the conventional relational model there has been considerable research in the area of incomplete information. On the other hand, research in temporal databases has concentrated on models in which complete historical information is needed. However, the likelihood of missing information in temporal databases is greater because of the vast amount of information. Hence, a mechanism must be provided to store and query incomplete temporal information. In this paper we present a model for incomplete information in temporal databases. The model generalizes our previous model for complete temporal information. It is shown that our relational operators produce results that are reliable. We also show, with some excentions. that if the definitions of the onerators were strengthened to give more information, we’ may obtain results that are not reliable.
---
paper_title: Valid-time indeterminacy

paper_content:

In valid-time indeterminacy, it is known that an event stored in a temporal database did in fact occur, but it is not known exactly when the event occurred. An extension of the tuple-timestamped temporal data model, called the possible chronons data model, is presented to support valid-time indeterminacy. In the possible chronons data model, each event is represented with a set of possible chronons, delimiting when the event might have occurred and a probability distribution over the set. The TQuel query language is extended using constructs that specify the user's credibility in the underlying valid-time data and the user's plausibility in the relationships among that data. A formal tuple calculus semantics is outlined, and it is shown that this semantics reduces to the determinate semantics on determinate data. >
---
paper_title: Dealing with granularity of time in temporal databases

paper_content:

A question that always arises when dealing with temporal information is the granularity of the values in the domain type. Many different approaches have been proposed; however, the community has not yet come to a basic agreement. Most published temporal representations simplify the issue which leads to difficulties in practical applications. In this paper, we resolve the issue of temporal representation by requiring two domain types (event times and intervals), formalize useful temporal semantics, and extend the relational operations in such a way that temporal extensions fit into a relational representation. Under these considerations, a database system that deals with temporal data can not only present consistent temporal semantics to users but perform consistent computational sequences on temporal data from diverse sources.
---
paper_title: Approaches to design of real-time database systems

paper_content:

Real-time database systems support applications which have severe operational constraints such as transaction deadlines and continued operation in the face of failures. In designing real-time database systems, there can be two approaches to meet those constraints. First approach is to redesign conventional database systems architecture to replace the bottleneck components. Second approach is to trade desired features, such as serializability, or exploit semantic information of transactions and data for high performance and reliability. In this paper, we discuss issues involved in these approaches, and present algorithms to solve problems in real-time database systems. 18 refs.
---
paper_title: Issues in real-time data management

paper_content:

This report explores issues related to the use of database management technology in support of real-time system programming. It describes the potential benefits of database support for real-time systems, and it describes the state of the art in database technologies relevant to real-time. The report concludes that more research and development will be needed before the benefits of database management can be applied to real-time system development.
---
paper_title: Time-critical database scheduling: a framework for integrating real-time scheduling and concurrency control

paper_content:

A framework is presented for analysis of time-critical scheduling algorithms. The main assumptions are analyzed behind real-time scheduling and concurrency control algorithms, and a unified approach is proposed. Two main classes of schedulers are identified according to the availability of information about resource requirements and execution times: conflict-resolving schedulers resolve conflicts at run-time, and hence can only produce a sequence of operations satisfying task priorities and resource constraints; and conflict-avoiding schedulers determine resource requirements and expected execution times through offline transaction-class preanalysis and produce a complete time-critical schedule satisfying both timing and resource constraints. For the latter case, the resolution of overload is essential. Examples are given to illustrate the framework and the main classes of scheduling algorithms. >
---
paper_title: Database description with SDM: a semantic database model

paper_content:

SDM is a high-level semantics-based database description and structuring formalism (database model) for databases. This database model is designed to capture more of the meaning of an application environment than is possible with contemporary database models. An SDM specification describes a database in terms of the kinds of entities that exist in the application environment, the classifications and groupings of those entities, and the structural interconnections among them. SDM provides a collection of high-level modeling primitives to capture the semantics of an application environment. By accommodating derived information in a database structural specification, SDM allows the same information to be viewed in several ways; this makes it possible to directly accommodate the variety of needs and processing requirements typically present in database applications. The design of the present SDM is based on our experience in using a preliminary version of it. SDM is designed to enhance the effectiveness and usability of database systems. An SDM database description can serve as a formal specification and documentation tool for a database; it can provide a basis for supporting a variety of powerful user interface facilities, it can serve as a conceptual database model in the database design process; and, it can be used as the database model for a new kind of database management system.
---
paper_title: Handling Temporal Knowledge in a Deductive Database System

paper_content:

We describe the design and implementation of a temporal deductive database system which supports (1) the storage of facts annotated with a time interval to indicate their perceived time of validity in the real world and (2) deduction rules which express temporal dependencies between (stored or derived) facts. The system features a logic-based query language in which even complex temporal queries can be expressed fairly concisely. We show how formulas involving temporal conjunction, disjunction, and negation can be translated into temporal extensions of the operators of relational algebra and into the database language SQL. A vital step in this translation is an implicit temporal normalization of intermediate results to avoid a redundant representation of temporal information which can even lead to incorrect results in certain cases.
---
paper_title: An analysis of the structural, dynamic, and temporal aspects of semantic data models

paper_content:

Semantic data models have been influenced by abstraction techniques used in knowledge representation. Early semantic models concentrated on the structural aspects of an application. More recently, researchers in semantic modeling have realized the importance of capturing the dynamic and temporal aspects of an application as well. This paper presents a detailed and uniform analysis of the structural, dynamic, and temporal aspects of object-oriented semantic models that support classification, aggregation, generalization, and association abstractions.
---
paper_title: PROBE: a knowledge-oriented database management system

paper_content:

Existing database management systems will be inadequate for many of the information processing applications (e.g., business and industrial automation, CAD/CAM, and military command and control) of the future. Our objective is to develop an advanced DBMS called PROBE that will handle more of the information types and intensional knowledge relevant to the new application areas. Our approach is to enhance existing DBMSs with (a) Abstract object types as the basis for defining new objects and operations and for integrating specialized processors, (b) Dimensional (space and time) concepts, which are the common characteristic of many of the new information types, and (c) Recursive predicates and queries, which provide intensional knowledge processing (deductive question-answering) capabilities. In each case, it is necessary to augment both the logical (data model, query language) components and the physical (storage structures, access methods, query processor) components of the DBMS. We describe approaches to addressing all these issues. We demonstrate via examples the dramatic performance improvement that can result if the DBMS optimizer is made cognizant of the information types and knowledge used by the application programs
---
paper_title: A homogeneous relational model and query languages for temporal databases

paper_content:

In a temporal database, time values are associated with data item to indicate their periods of validity. We propose a model for temporal databases within the framework of the classical database theory. Our model is realized as a temporal parameterization of static relations. We do not impose any restrictions upon the schemes of temporal relations. The classical concepts of normal forms and dependencies are easily extended to our model, allowing a suitable design for a database scheme. We present a relational algebra and a tuple calculus for our model and prove their equivalence. Our data model is homogeneous in the sense that the periods of validity of all the attributes in a given tuple of a temporal relation are identical. We discuss how to relax the homogeneity requirement to extend the application domain of our approach.
---
paper_title: Object-based semantic real-time concurrency control

paper_content:

This paper presents a technique that is capable of supporting two major requirements for concurrency control in real-time databases; data temporal consistency, and data logical consistency, as well as tradeoffs between these requirements. Our technique is based upon a real-time object-oriented database model in which each object has its own unique compatibility function that expresses the conditional compatibility of any two potential concurrent operations on the object. The conditions use the semantics of the object, such as allowable imprecision, along with current system state, such as time and the active operations on the object. Our concurrency control technique enforces that allowable concurrency expressed by the compatibility function by using semantic locking controlled by each individual object. The real-time object-oriented database model and process of evaluating the compatibility function to grant semantic locks are described. >
---
paper_title: A logical framework for temporal deductive databases

paper_content:

Temporal deductive databases are deductive databases with an ability to represent both valid time and transaction time. The work is based on the Event Calculus of Kowalski & Sergot. Event Calculus is a treatment of time, based on the notion of events, in first-order classical logic augmented with negation as failure. It formalizes the semantics of valid time in deductive databases and offers capability for the semantic validation of updates and default reasoning. In this paper, the Event Calculus is extended to include the concept of transaction time. The resulting framework is capable of handling both proactive and retroactive updates symmetrically. Error correction is achieved without deletions by means of negation as failure. The semantics of transaction time is formalised and the axioms of the Event Calculus are modified to cater for temporal databases. Given a description of events, axioms are presented for deducing relationships and the time periods for which they hold with respect to any past/present state of the database .
---
paper_title: Knowledge acquisition for temporal-abstraction mechanisms

paper_content:

Abstract We describe three general temporal-abstraction mechanisms needed for managing time-stamped data: point temporal abstraction (a mechanism for abstracting several parameter values into one class); temporal inference (a mechanism for inferring sound logical conclusions over a single interval or two meeting intervals); and temporal interpolation (a mechanism for bridging non-meeting temporal intervals). Making explicit the knowledge required for temporal abstractions supports the acquisition of problem-solving knowledge needed for planning, plan execution, problem identification and plan revision. These mechanisms are implemented in the RESUME system, and will be used in the context of our ongoing PROTEGE-II project, whose goal is to generate knowledge-based systems automatically, as well as the appropriate knowledge-acquisition tools, custom-tailored to acquire the specific domain and task knowledge needed by the specific problem-solving method chosen for the task.
---
paper_title: The Implementation of Postgres

paper_content:

The design and implementation decisions made for the three-dimensional data manager POSTGRES are discussed. Attention is restricted to the DBMS backend functions. The POSTGRES data model and query language, the rules system, the storage system, the POSTGRES implementation and the current status and performance are discussed. >
---
paper_title: TOOA: A Temporal Object-Oriented Algebra

paper_content:

In this paper, we present a temporal, object-oriented algebra which serves as a formal basis for the query language of a temporal, object-oriented data model. Our algebra is a superset of the relational algebra in that it provides support for manipulating temporal objects, temporal types, type hierarchies and class lattices, multiple time-lines, and correction sequences in addition to supporting the five relational algebra operators. Graphs are used as the visual representations of both the schema and the object instances. The algebra provides constructs to modify and manipulate the schema graph and its extension, the object graph. The algebra operates on a collection or collections of objects and returns a collection of objects. This algebra is a first step in providing a formal foundation for query processing and optimizing in a temporal, object-oriented data model.
---
paper_title: TOODM - A Temporal Object-Oriented Data Model with Temporal Constraints

paper_content:

A static Entity-Relationship (ER) or static Extended ER (EER) data model is not sufficient for representing the underlying time component of the data, more complex data types as found in planning, design and office automation applications or the operation required for this complex data. The decreasing cost of mass storage devices accompanied by an increased need for real-time systems and easier access to historical and planning data has made the study of the temporal aspects of data models more interesting both theoretically and practically. Furthermore, the ER-based data models can capture relationships between classes but they do not understand the object-oriented paradigm since they treat application-specific relationships and paradigm-specific relationships such as inheritance in the same manner. This shortcoming accompanied by a lack of support for the time dimension results in the specification of temporal relationships and constraints at the application level and often leads to inconsistencies in the data. In this paper, we extend the object-based ER model into a temporal, object-oriented model, incorporate temporal structures and constraints in the data model and propose a temporal, object-oriented query language for the model.
---
paper_title: A data model and query language for EXODUS

paper_content:

In this paper, we present the design of the EXTRA data model and the EXCESS query language for the EXODUS extensible database system. The EXTRA data model includes support for complex objects with shared subobjects, a novel mix of object- and value-oriented semantics for data, support for persistent objects of any type in the EXTRA type lattice, and user-defined abstract data types (ADTs). The EXCESS query language provides facilities for querying and updating complex object structures, and it can be extended through the addition of ADT functions and operators, procedures and functions for manipulating EXTRA schema types, and generic set functions EXTRA and EXCESS are intended to serve as a test vehicle for tools developed under the EXODUS extensible database system project.
---
paper_title: Integrating Access-Oriented Programming into a Multiparadigm Environment

paper_content:

The Loops knowledge programming system integrates function-oriented, system object-oriented, rule-oriented, and—something notfound in most other systems—access-oriented programming.
---
paper_title: The Implementation of Postgres

paper_content:

The design and implementation decisions made for the three-dimensional data manager POSTGRES are discussed. Attention is restricted to the DBMS backend functions. The POSTGRES data model and query language, the rules system, the storage system, the POSTGRES implementation and the current status and performance are discussed. >
---
paper_title: The Iris Architecture and Implementation

paper_content:

The goals of the Iris database management system are to enhance database programmer productivity and to provide generalized database support for the integration of future applications. Iris is based on an object and function model. Iris objects are typed but unlike other object systems, they contain no state. Attribute values, relationships and behavior of objects are modeled by functions. The Iris architecture efficiently supports the evaluation of functional expressions. The goal of the architecture is to provide a database system that is powerful enough to support the definition of functions and procedures that implement the semantics of the data model. An overview of the data model is provided, the architecture is described in detail, and implementation experience and usage of the system are discussed. >
---
paper_title: The time relational model

paper_content:

Existing data base management systems (DBMSs) allow users to operate upon the latest (committed) data base state. However, many real world applications require storing and accessing historical information. Furthermore, there are no provisions in current DBMSs for the distinction between the physical time a given data item is entered, and the time period to which it pertains. Many data base updates in real applications are either "retroactive", i.e., their effectiveness takes place sometime in the past, or "proactive", i.e., their effectiveness will take place sometime in the future. ::: The Time-Relational Model is an architecture which integrates comprehensive time processing capabilities into the Relational Model of data bases for managing changes of data values, data manipulation rules, and data structure. However, those who are not concerned about Time in their particular applications may perceive this model as a regular relational model. ::: A fundamental concept is the time-view of data and transaction programs. Its major objective is to automatically and dynamically provide multiple and complete data base views reflecting different points in time, including all system components that may change over time. The time-view theorem provides necessary and sufficient conditions for achieving any desirable, dynamic time-view. The time-consistency theorem states the conditions for which a given computation can be reproduced again and again in the face of data base changes over time. The basic relational algebra operators are extended to include the time-view concept, resulting in the time relational algebra. An implementation architecture is developed which demonstrates the feasibility of such model. The central idea is to gain more functions and solutions based on the presence of time related information and, thus, spread the overall operational and implementation cost across multiple sources. Recovery Manager and Concurrency Control Procedures are developed. The recovery manager uses only the data itself for its own operation rather, than a logging facility; there is no need for a locking mechanism to provide each user with an appropriate isolation level from other concurrent users. ::: A real-life case study is described based on the Informatics Inc. Manufacturing Planning System - PRODUCTION-IV.
---
paper_title: Scheduling real-time transactions with disk resident data

paper_content:

Managing transactions with real-time requirements and disk resident data presents many new problems. In this paper we address several: How can we schedule transactions with deadlines? How do the real-time constraints affect concurrency control? How does the scheduling of IO requests affect the timeliness of transactions? How should exclusive and shared locking be handled? We describe a new group of algorithms for scheduling realtime transactions which produce serializable schedules. We present a model for scheduling transactions with deadlines on a single processor disk resident database system, and evaluate the scheduling algorithms through detailed simulation.
---
paper_title: An Approach Towards Predictable Real-Time Transaction Processing

paper_content:

A real-tame database system can be defined as a database system where transactions are associated with real-time constraints typically in the form of deadlines. The system must process transactions to both meet the deadlines and maintain data consistency. Current research effort in this field has been focused on schedaling transactions with soft or firm deadlines under the conventional transaction model and database system archatecture. They cannot support predictable realtime transaction processing. In this paper, we will provide a framework to realize predictable real-time transaction processing. First, we introduce a new model for real-time database systems which includes both hard and soft real-time transactions. Second, we develop an integrated real-time transaction processing scheme under deterministic subsystem support.
---
paper_title: Principles of transaction-oriented database recovery

paper_content:

In this paper, a terminological framework is provided for describing different transactionoriented recovery schemes for database systems in a conceptual rather than an implementation-dependent way. By introducing the terms materialized database, propagation strategy, and checkpoint, we obtain a means for classifying arbitrary implementations from a unified viewpoint. This is complemented by a classification scheme for logging techniques, which are precisely defined by using the other terms. It is shown that these criteria are related to all relevant questions such as speed and scope of recovery and amount of redundant information required. The primary purpose of this paper, however, is to establish an adequate and precise terminology for a topic in which the confusion of concepts and implementational aspects still imposes a lot of problems.
---
paper_title: Event specification in an active object-oriented database

paper_content:

The concept of a trigger is central to any active database. Upon the occurrence of a trigger event, the trigger is “fired”, i.e, the trigger action is executed. We describe a model and a language for specifying basic and composite trigger events in the context of an object-oriented database. The specified events can be detected efficiently using finite automata. We integrate our model with O++, the database programming language for the ode object database being developed at AT&T Bell Labs. We propose a new Event-Action model, which folds into the event specification the condition part of the well-known Event-Condition-Action model and avoids the multiple coupling modes between the event, condition, and action trigger components.
---
paper_title: Issues in real-time data management

paper_content:

This report explores issues related to the use of database management technology in support of real-time system programming. It describes the potential benefits of database support for real-time systems, and it describes the state of the art in database technologies relevant to real-time. The report concludes that more research and development will be needed before the benefits of database management can be applied to real-time system development.
---
paper_title: Algorithms for scheduling imprecise computations

paper_content:

The imprecise computation technique, which prevents timing faults and achieves graceful degradation by giving the user an approximate result of acceptable quality whenever the system cannot produce the exact result in time, is considered. Different approaches for scheduling imprecise computations in hard real-time environments are discussed. Workload models that quantify the tradeoff between result quality and computation time are reviewed. Scheduling algorithms that exploit this tradeoff are described. These include algorithms for scheduling to minimize total error, scheduling periodic jobs, and scheduling parallelizable tasks. A queuing-theoretical formulation of the imprecise scheduling problem is presented. >
---
paper_title: Object-based semantic real-time concurrency control

paper_content:

This paper presents a technique that is capable of supporting two major requirements for concurrency control in real-time databases; data temporal consistency, and data logical consistency, as well as tradeoffs between these requirements. Our technique is based upon a real-time object-oriented database model in which each object has its own unique compatibility function that expresses the conditional compatibility of any two potential concurrent operations on the object. The conditions use the semantics of the object, such as allowable imprecision, along with current system state, such as time and the active operations on the object. Our concurrency control technique enforces that allowable concurrency expressed by the compatibility function by using semantic locking controlled by each individual object. The real-time object-oriented database model and process of evaluating the compatibility function to grant semantic locks are described. >
---
paper_title: Temporal and Modal Logic

paper_content:

Publisher Summary This chapter discusses temporal and modal logic. The chapter describes a multiaxis classification of systems of temporal logic. The chapter describes the framework of linear temporal logic. In both its propositional and first-order forms, linear temporal logic has been widely employed in the specification and verification of programs. The chapter describes the competing framework of branching temporal logic, which has seen wide use. It also explains how temporal logic structures can be used to model concurrent programs using non-determinism and fairness. The chapter also discusses other modal and temporal logics in computer science. The chapter describes the formal syntax and semantics of Propositional Linear Temporal Logic (PLTL). The chapter also describes the formal syntax and semantics for two representative systems of propositional branching-time temporal logics.
---
paper_title: Partitioned storage for temporal databases

paper_content:

Abstract Efficiently maintaining history data on line together with current data is difficult. This paper discusses one promising approach, the temporally partitioned store. The current store contains current data and possibly some history data, whil the history store holds the rest of the data. The two stores can utilize different storage formats, and even different storage media, depending on the individual data characteristics. We discuss various issues on the temporally partitioned store, investigate several formats for the history store, and evaluate their performance on a set of sample queries.
---
paper_title: An object-oriented data model for a time series management system

paper_content:

The analysis of time series is a central issue in economic research and many other scientific applications. However, the data management functionality for this field is not provided by general-purpose DBMSs. Therefore, we propose a data model of a specialized time series management system (TSMS) which accounts for these needs. The model is centered around an object-oriented kernel that offers the classes and value types needed for the target applications. The model provides base classes for multivariate time series and for groups as a means to hierarchically partition the time series space. The system offers a computationally complete data manipulation language including capabilities to query time series and groups. An elaborate array model is supported to account for the functional needs of statistical computations. Furthermore, a customizable calendar system providing a variety of predefined calendars is included. >
---
paper_title: Logical modeling of temporal data

paper_content:

In this paper we examine the semantics and develop constructs for temporal data independent of any traditional data model, such as the relational or network data models. Unlike many other works which extend existing models to support temporal data, our purpose is to characterize the properties of temporal data and operators over them without being influenced by traditional models which were not specifically designed to model temporal data. We develop data constructs that represent sequences of temporal values, identify their semantic properties, and define operations over these structures.
---
paper_title: Design and implementation of a semantic query optimizer

paper_content:

The authors describe a scheme to utilize semantic knowledge in optimizing a user-specified query. The semantics is represented as function-free clauses in predicate logic. The scheme uses a graph-theoretic approach to identify redundant joins and restrictions present in a given query while adding additional profitable specifications to it. Dynamic and heuristic interaction of three entities-schema, semantics, and query-forms the basis of the algorithm. The implementation architecture of the algorithm and test results on a representative set of data are presented. Issues associated with updating of semantic constraints are addressed, and an algorithm for semantic maintenance is introduced. >
---
paper_title: Sequence Query Processing

paper_content:

Many applications require the ability to manipulate sequences of data. We motivate the importance of sequence query processing, and present a framework for the optimization of sequence queries based on several novel techniques. These include query transformations, optimizations that utilize meta-data, and caching of intermediate results. We present a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates. This work also identifies a number of directions in which future research can be directed.
---
paper_title: Global query optimization

paper_content:

In some recently proposed extensions to relational database systems as well as in deductive databases, a database system is presented with a collection of queries to process instead of just one. It is an interesting problem then, to come up with algorithms that process these queries together instead of one query at a time. We examine the problem of multiple (global) query optimization in this paper. A hierarchy of algorithms that can be used for global query optimization is exhibited and analyzed. These algorithms range from an arbitrary serial execution without any sharing of common results among the queries to an exhaustive search of all possible ways to process all queries.
---
paper_title: Partitioned storage for temporal databases

paper_content:

Abstract Efficiently maintaining history data on line together with current data is difficult. This paper discusses one promising approach, the temporally partitioned store. The current store contains current data and possibly some history data, whil the history store holds the rest of the data. The two stores can utilize different storage formats, and even different storage media, depending on the individual data characteristics. We discuss various issues on the temporally partitioned store, investigate several formats for the history store, and evaluate their performance on a set of sample queries.
---
paper_title: Using annotations to support multiple kinds of versioning in an object-oriented database system

paper_content:

The concept of annotation from object-oriented languages is adapted to object-oriented databases. It is shown how annotations can be used to model activities such as constraint checking, default values, and triggers. Annotations also are an appropriate way to model different versioning concepts. This paper discusses three kinds of versioning—histories, revisions, and alternatives—and demonstrates how each one can be modeled effectively using annotations. The use of annotations also allows other kinds of versioning to be defined extensibly, and arbitrary combinations of versions can be handled easily.
---
paper_title: Selectivity estimation of temporal data manipulations

paper_content:

Abstract Temporal relations possess several characteristics that distinguish them from conventional snapshot relations. First, for each instance of the surrogate (entity) there is a set of time-ordered tuples. Second, surrogate instances may arrive and depart in some time-dependent manner. Third, the surrogate instance may arrive and depart more than once, thus creating gaps (null values) within its history. Lastly, the value of the temporal attribute may also be time-dependent. Conventional methods of estimation are incapable of providing good approximations of the cost of various temporal operations, even for those involving selections on a single relation. The problem is more acute in the case of join operations, because selectivities on time interval intersections have to be estimated. We propose a practical, yet theoretically sound model to characterize the changes of temporal relations. From this model, estimates of the cardinalities of various unary and binary operations are derived. Simulation results show that the proposed estimates are both robust and superior to conventional estimates.
---
paper_title: Incremental implementation model for relational databases with transaction time

paper_content:

An implementation model for the standard relational data model extended with transaction time is presented. The implementation model integrates techniques of view materialization, differential computation, and deferred update into a coherent whole. It is capable of storing any view (reflecting past or present states) and subsequently using stored views as outsets for incremental and decremental computations of requested views, making it more flexible than previously proposed partitioned storage models. The working and the expressiveness of the model are demonstrated by sample queries that show how historical data are retrieved. >
---
paper_title: A framework for query optimization in temporal databases

paper_content:

We investigate issues pertaining to query processing of temporal databases in a relational environment. Tuple-versioning of relations is the adopted method of temporal data representation. New operators are necessary in order to exploit the richer semantics of temporal queries. We define four types of temporal joins— theta-join, time intersection, time union and the event-join. Factors that affect processing strategies are discussed, especially the problem of estimating data selectivity for various temporal operations. Strategies for implementing the temporal equijoin operator is evaluated.
---
paper_title: The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans

paper_content:

Critical to the design of an historical database model is the representation of the “existence” of objects across the temporal dimension — for example, the “birth,” “death,” or “rebirth” of an individual, or the establishment or dis-establishment of a relationship. The notion of the “lifespan” of a database object is proposed as a simple framework for expressing these concepts. An object's lifespan is simply those periods of time during which the database models the properties of that object. In this paper we propose the historical relational data model (HRDM) and algebra that is based upon lifespans and that views the values of all attributes as functions from time points to simple domains. The model that we obtain is a consistent extension of the relational data model, and provides a simple mechanism for providing both time-varying data and time-varying schemes.
---
paper_title: The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans

paper_content:

Critical to the design of an historical database model is the representation of the “existence” of objects across the temporal dimension — for example, the “birth,” “death,” or “rebirth” of an individual, or the establishment or dis-establishment of a relationship. The notion of the “lifespan” of a database object is proposed as a simple framework for expressing these concepts. An object's lifespan is simply those periods of time during which the database models the properties of that object. In this paper we propose the historical relational data model (HRDM) and algebra that is based upon lifespans and that views the values of all attributes as functions from time points to simple domains. The model that we obtain is a consistent extension of the relational data model, and provides a simple mechanism for providing both time-varying data and time-varying schemes.
---
paper_title: Value-based scheduling in real-time database systems

paper_content:

In a real-time database system, an application may assign a value to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a "bucket" priority mechanism that allows the relative importance of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.
---
paper_title: Integration of Time Versions into a Relational Database System

paper_content:

New application areas for database systems, such as office automation and CAD/CAM will require to support not only access to the current data, as is done in current database systems, but also to previous instances of the data (versions). This means that time version support is needed. This paper presents the design considerations for a database system currently under implementation, that integrates time version support as a normal database function. It is shown that many subtle issues, such as choice of a suitable timestamp, how to store history data in a compact form, how to integrate version management into update processing, recovery, concurrency control, etc., have to be considered together to obtain an optimal design.
---
paper_title: Approximate analysis of real-time database systems

paper_content:

During the past few years, several studies have been made on the performance of real-time database systems with respect to the number of transactions that miss their deadlines. These studies have used either simulation models or database testbeds as their performance evaluation tools. We present a preliminary analytical performance study of real-time transaction processing. Using a series of approximations, we derive simple closed-form solutions to reduced real-time database models. Although quantitatively approximate, the solutions accurately capture system sensitivity to workload parameters and indicate conditions under which performance bounds are achieved. >
---
paper_title: The Design Of The Postgres Storage System

paper_content:

Abstract : This paper presents the design of the storage system for the POSTGRES data base system under construction at Berkeley. It is novel in several ways. First, the storage manager supports transaction management but does so without using a conventional write ahead log (WAL). In fact, there is no code to run at recovery time, and consequently recovery from crashes is essentially instantaneous. Second, the storage manager allows a user to optionally keep the entire past history of data base objects by closely integrating an archival storage system to which historical records are spooled. Lastly, the storage manager is consciously constructed as a collection of asynchronous processes. Hence, a large monolithic body of code is avoided and opportunities for parallelism can be exploited. The paper concludes with a analysis of the storage system which suggests that it is performance competitive with WAL systems in many situations.
---
paper_title: Value-based scheduling in real-time database systems

paper_content:

In a real-time database system, an application may assign a value to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a "bucket" priority mechanism that allows the relative importance of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.
---
paper_title: On Using Priority Inheritance In Real-Time Databases

paper_content:

The authors investigate solutions to the priority inversion problem in a real-time database where two-phase locking is employed for concurrency control. They examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. The authors also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantage of each of the two basic schemes. The performance studies, conducted on a real-time database testbed, indicated that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. The authors also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads. >
---
paper_title: Real-time transaction scheduling: a cost conscious approach

paper_content:

Real-time databases are an important component of embedded real-time systems. In a real-time database context, transactions must not only maintain the consistency constraints of the database but must also satisfy the timing constraints specified for each transaction. Although several approaches have been proposed to integrate real-time scheduling and database concurrency control methods, none of them take into account the dynamic cost of scheduling a transaction. In this paper, we propose a new cost conscious real-time transaction scheduling algorithm which considers dynamic costs associated with a transaction. Our dynamic priority assignment algorithm adapts to changes in the system load without causing excessive numbers of transaction restarts. Our simulations show its superiority over EDF-HP algorithm.
---
paper_title: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

paper_content:

The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed.
---
paper_title: Experimental evaluation of real-time transaction processing

paper_content:

Results are presented of empirical evaluations carried out on the RT-CARAT testbed. This testbed was used evaluating a set of integrated protocols that support real-time transactions. A basic locking scheme for concurrency control was used to develop and evaluate several algorithms for handling CPU scheduling, data-conflict resolution, deadlock resolution, transaction wakeup, and transaction restart. The performance data indicate that the CPU scheduling algorithm is the most significant of all the algorithms in improving the performance of real-time transactions, conflict-resolution protocols which directly address deadlines and criticality can have a substantial impact on performance compared to protocols that ignore such information, both criticality and deadline distributions strongly affect transaction performance, and overheads such as locking and message communication are nonnegligible and cannot be ignored in real-time transaction analysis. It is believed that these empirical results represent the first experimental results for real-time transactions on a testbed system. >
---
paper_title: Priority Inheritance Protocols: An Approach to Real-Time Synchronization

paper_content:

An investigation is conducted of two protocols belonging to the priority inheritance protocols class; the two are called the basic priority inheritance protocol and the priority ceiling protocol. Both protocols solve the uncontrolled priority inversion problem. The priority ceiling protocol solves this uncontrolled priority inversion problem particularly well; it reduces the worst-case task-blocking time to at most the duration of execution of a single critical section of a lower-priority task. This protocol also prevents the formation of deadlocks. Sufficient conditions under which a set of periodic tasks using this protocol may be scheduled is derived. >
---
paper_title: Earliest deadline scheduling for real-time database systems

paper_content:

A new priority assignment algorithm called adaptive earliest deadline (AED) is given that stabilizes the overload performance of the earliest deadline policy in a real-time database system (RTDBS) environment. The AED algorithm uses a feedback control mechanism to achieve this objective and does not require knowledge of transaction characteristics. Using a detailed simulation model, the authors compare the performance of AED with respect to earliest deadline and other fixed priority schemes. They also present and evaluate an extension of the AED algorithm called hierarchical earliest deadline (HED), which is designed to handle applications that assign different values to transactions and where the goal is to maximize the total value of the in-time transactions. >
---
paper_title: Dynamic real-time optimistic concurrency control

paper_content:

The authors (1990) have shown that in real-time database systems that discard late transactions, optimistic concurrency control outperforms locking. Although the optimistic algorithm used in that study, OPT-BC, did not factor in transaction deadlines in making data conflict resolution decisions, it still outperformed a deadline-cognizant locking algorithm. A discussion is presented of why adding deadline information to optimistic algorithms is a nontrivial problem, and some alternative methods of doing so are described. A new real-time optimistic concurrency control algorithm, WAIT-50, is presented that monitors transaction conflict states and gives precedence to urgent transactions in a controlled manner. WAIT-50 is shown to provide significant performance gains over OPT-BC under a variety of operating conditions and workloads. >
---
paper_title: On Using Priority Inheritance In Real-Time Databases

paper_content:

The authors investigate solutions to the priority inversion problem in a real-time database where two-phase locking is employed for concurrency control. They examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. The authors also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantage of each of the two basic schemes. The performance studies, conducted on a real-time database testbed, indicated that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. The authors also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads. >
---
paper_title: Approaches to design of real-time database systems

paper_content:

Real-time database systems support applications which have severe operational constraints such as transaction deadlines and continued operation in the face of failures. In designing real-time database systems, there can be two approaches to meet those constraints. First approach is to redesign conventional database systems architecture to replace the bottleneck components. Second approach is to trade desired features, such as serializability, or exploit semantic information of transactions and data for high performance and reliability. In this paper, we discuss issues involved in these approaches, and present algorithms to solve problems in real-time database systems. 18 refs.
---
paper_title: Enhancing real-time DBMS performance with multiversion data and priority based disk scheduling

paper_content:

Real-time multiversion concurrency control algorithms are proposed, to: increase concurrency, adjust the serialization order dynamically and work without an estimate of a transaction's runtime. The authors also propose disk scheduling algorithms which consider not only the transactions which request input/output (I/O) but also those affected by I/O. They consider transactions which are directly affected when priorities of I/O requests are assigned, in addition to transactions which generates these requests. The real-time disk resident database system model and the multiversion concurrency control algorithms are described. The real-time disk scheduling algorithms and their properties are also described. Real-time multiversion concurrency control and disk scheduling algorithms are shown to decrease miss ratio significantly. >
---
paper_title: Dynamic real-time optimistic concurrency control

paper_content:

The authors (1990) have shown that in real-time database systems that discard late transactions, optimistic concurrency control outperforms locking. Although the optimistic algorithm used in that study, OPT-BC, did not factor in transaction deadlines in making data conflict resolution decisions, it still outperformed a deadline-cognizant locking algorithm. A discussion is presented of why adding deadline information to optimistic algorithms is a nontrivial problem, and some alternative methods of doing so are described. A new real-time optimistic concurrency control algorithm, WAIT-50, is presented that monitors transaction conflict states and gives precedence to urgent transactions in a controlled manner. WAIT-50 is shown to provide significant performance gains over OPT-BC under a variety of operating conditions and workloads. >
---
paper_title: Replication control for distributed real-time database systems

paper_content:

An algorithm that integrates real-time scheduling with replication control is presented. The algorithm adopts a token-based scheme for replication control and attempts to balance the urgency of real-time transactions with the conflict resolution policies. In addition, the algorithm employs epsilon-serializability (ESR), a correctness criterion that is less stringent than conventional one-copy serializability. The algorithm is flexible and very practical, since no prior knowledge of data requirements or execution time of each transaction is required. >
---
paper_title: Divergence control for epsilon-serializability

paper_content:

The authors present divergence control methods for epsilon-serializability (ESR) in centralized databases. ESR alleviates the strictness of serializability (SR) in transaction processing by allowing for limited inconsistency. The bounded inconsistency is automatically maintained by divergence control (DC) methods in a way similar to the manner in which SR is maintained by concurrency control mechanisms, but DC for ESR allows more concurrency. Concrete representative instances of divergence-control methods are described based on two-phase locking, timestamp ordering, and optimistic approaches. The applicability of ESR is demonstrated by presenting the designs of DC methods using other most known inconsistency specifications, such as absolute value, age, and total number of nonserializably read data items. >
---
paper_title: Performance characteristics of epsilon serializability with hierarchical inconsistency bounds

paper_content:

The notion of hierarchical inconsistency bounds that allows inconsistency to be specified at different granularities-with transactions being at the top of the hierarchy, objects at the bottom, and groups in between-is introduced. The mechanisms needed to control the inconsistency so that it lies within the specified bounds are described. The performance improvement due to epsilon serializability (ESR) is evaluated. Two important observations are made. First, the thrashing point shifts to a higher multiprogramming level when transaction inconsistency bounds are increased. Second, for a particular multiprogramming level and a particular transaction inconsistency bound, the throughput does not increase with increasing object inconsistency bounds but peaks at some intermediate value. >
---
paper_title: The time relational model

paper_content:

Existing data base management systems (DBMSs) allow users to operate upon the latest (committed) data base state. However, many real world applications require storing and accessing historical information. Furthermore, there are no provisions in current DBMSs for the distinction between the physical time a given data item is entered, and the time period to which it pertains. Many data base updates in real applications are either "retroactive", i.e., their effectiveness takes place sometime in the past, or "proactive", i.e., their effectiveness will take place sometime in the future. ::: The Time-Relational Model is an architecture which integrates comprehensive time processing capabilities into the Relational Model of data bases for managing changes of data values, data manipulation rules, and data structure. However, those who are not concerned about Time in their particular applications may perceive this model as a regular relational model. ::: A fundamental concept is the time-view of data and transaction programs. Its major objective is to automatically and dynamically provide multiple and complete data base views reflecting different points in time, including all system components that may change over time. The time-view theorem provides necessary and sufficient conditions for achieving any desirable, dynamic time-view. The time-consistency theorem states the conditions for which a given computation can be reproduced again and again in the face of data base changes over time. The basic relational algebra operators are extended to include the time-view concept, resulting in the time relational algebra. An implementation architecture is developed which demonstrates the feasibility of such model. The central idea is to gain more functions and solutions based on the presence of time related information and, thus, spread the overall operational and implementation cost across multiple sources. Recovery Manager and Concurrency Control Procedures are developed. The recovery manager uses only the data itself for its own operation rather, than a logging facility; there is no need for a locking mechanism to provide each user with an appropriate isolation level from other concurrent users. ::: A real-life case study is described based on the Informatics Inc. Manufacturing Planning System - PRODUCTION-IV.
---
paper_title: Partitioned storage for temporal databases

paper_content:

Abstract Efficiently maintaining history data on line together with current data is difficult. This paper discusses one promising approach, the temporally partitioned store. The current store contains current data and possibly some history data, whil the history store holds the rest of the data. The two stores can utilize different storage formats, and even different storage media, depending on the individual data characteristics. We discuss various issues on the temporally partitioned store, investigate several formats for the history store, and evaluate their performance on a set of sample queries.
---
paper_title: Integration of Time Versions into a Relational Database System

paper_content:

New application areas for database systems, such as office automation and CAD/CAM will require to support not only access to the current data, as is done in current database systems, but also to previous instances of the data (versions). This means that time version support is needed. This paper presents the design considerations for a database system currently under implementation, that integrates time version support as a normal database function. It is shown that many subtle issues, such as choice of a suitable timestamp, how to store history data in a compact form, how to integrate version management into update processing, recovery, concurrency control, etc., have to be considered together to obtain an optimal design.
---
paper_title: Enhancing real-time DBMS performance with multiversion data and priority based disk scheduling

paper_content:

Real-time multiversion concurrency control algorithms are proposed, to: increase concurrency, adjust the serialization order dynamically and work without an estimate of a transaction's runtime. The authors also propose disk scheduling algorithms which consider not only the transactions which request input/output (I/O) but also those affected by I/O. They consider transactions which are directly affected when priorities of I/O requests are assigned, in addition to transactions which generates these requests. The real-time disk resident database system model and the multiversion concurrency control algorithms are described. The real-time disk scheduling algorithms and their properties are also described. Real-time multiversion concurrency control and disk scheduling algorithms are shown to decrease miss ratio significantly. >
---
paper_title: PriorityHints: An Algorithm for Priority-Based Buffer Management

paper_content:

In this paper, we address the problem of buffer management in a DBMS when the workload consists of transactions of different priority levels. We present Priority-Hints. a new buffer management algorithm that uses hints provided by the DBMS access methods. The performance of Priority-Hints is compared to that of priority buffer management schemes introduced earlier for a variety of workloads. Our simulation results indicate that Priority-Hints performs consistently better than simple LRU-based algorithms. Furthermore, our algorithm approaches (and in some cases surpasses) the performance of highly sophisticated algorithms that require much more information to be provided to the buffer manager.
---
paper_title: Performance evaluation of two new disk scheduling algorithms for real-time systems

paper_content:

In this paper, we present two new disk scheduling algorithms for real-time systems. The two algorithms, called SSEDO (for Shortest Seek and Earliest Deadline by Ordering) and SSEDV (for Shortest Seek and Earliest Deadline by Value), combine deadline information and disk service time information in different ways. The basic idea behind these new algorithms is to give the disk I/O request with the earliest deadline a high priority, but if a request with a larger deadline is "very" close to the current disk arm position, then it may be assigned the highest priority. The performance of SSEDO and SSEDV algorithms is compared with three other proposed real-time disk scheduling algorithms ED, P-SCAN, and FD-SCAN, as well as four conventional algorithms SSTF, SCAN, C-SCAN, and FCFS. An important aspect of the performance study is that the evaluation is not done in isolation with respect to the disk, but as part of an integrated collection of protocols necessary to support a real-time transaction system. The transaction system model is validated on an actual real-time transaction system testbed, called RT-CARAT. The performance results show that SSEDV outperforms SSEDO; that both of these new algorithms can improve performance of up to 38% over previously-known real-time disk scheduling algorithms; and that all of these real-time scheduling algorithms are significantly better than non-real-time algorithms in the sense of minimizing the transaction loss ratio.
---

Title: Temporal and Real-Time Databases: A Survey

Section 1: INTRODUCTION
Description 1: This section introduces the key concepts of temporal and real-time databases, highlighting their importance in different applications.

Section 2: THE TIME DOMAIN
Description 2: This section focuses on the nature of time itself, covering its structure, dimensionality, indeterminacy, and the types of time associated with real-time data.

Section 3: Temporal Data Models
Description 3: This section examines various temporal data models proposed in the literature, focusing primarily on relational and object-oriented models.

Section 4: Real-time Data Models
Description 4: This section explores real-time data models and their initial research, considering both relational and object-oriented models.

Section 5: TEMPORAL QUERY LANGUAGES
Description 5: This section discusses temporal query languages, their operations, and the different proposals to date for handling temporal data in queries.

Section 6: REAL-TIME DATA AND TRANSACTION PROPERTIES
Description 6: This section explains the properties and requirements of real-time data and transactions, including constraints and consistency requirements.

Section 7: Real-Time Query Languages
Description 7: This section discusses the state of research on real-time query and transaction specification languages for real-time databases.

Section 8: ARCHITECTURAL ISSUES
Description 8: This section delves into the implementation aspects of temporal and real-time databases, focusing on query processing and transaction management.

Section 9: CONCLUSIONS AND FUTURE WORK
Description 9: This section summarizes the major accomplishments in the research, highlights ongoing challenges, and suggests future research directions.