The query optimization phase within a database management system (DBMS) ostensibly finds the fastest query execution plan from a potentially large set of enumerated plans, all of which correctly compute the same result of the specified query. Sometimes the cost-based optimizer selects a slower plan, for a variety of reasons. Previous work has focused on increasing the performance of specific components, often a single operator, within an individual DBMS. However, that does not address the fundamental question: from where does this suboptimality arise, across DBMSes generally? In particular, the contribution of each of many possible factors to DBMS suboptimality is currently unknown. To identify the root causes of DBMS suboptimality, we first introduce the notion of empirical suboptimality of a query plan chosen by the DBMS, indicated by the existence of a query plan that performs more efficiently than the chosen plan, for the same query. A crucial aspect is that this can be measured externally to the DBMS, and thus does not require access to its source code. We then propose a novel predictive model to explain the relationship between various factors in query optimization and empirical suboptimality. Our model associates suboptimality with the factors of complexity of the schema, of the underlying data on which the query is evaluated, of the query itself, and of the DBMS optimizer. The model also characterizes concomitant interactions among these factors. This model induces a number of specific hypotheses that were tested on multiple DBMSes. We performed a series of experiments that examined the plans for thousands of queries run on four popular DBMSes. We tested the model on over a million of these query executions, using correlational analysis, regression analysis, and causal analysis, specifically Structural Equation Modeling (SEM). We observed that the dependent construct of empirical suboptimality prevalence correlates positively with nine specific constructs characterizing four identified factors that explain in concert much of the variance of suboptimality of two extensive benchmarks, across these disparate DBMSes. This predictive model shows that it is the common aspects of these DBMSes that predict suboptimality, not the particulars embedded in the inordinate complexity of each of these DBMSes. This paper thus provides a new methodology to study mature query optimizers, identifies underlying DBMS-independent causes for the observed suboptimality, and quantifies the relative contribution of each of these causes to the observed suboptimality. This work thus provides a roadmap for fundamental improvements of cost-based query optimizers.

Summary Measuring execution time is one of the most used performance evaluation techniques in computer science research. Inaccurate measurements cannot be used for a fair performance comparison between programs. Despite the prevalence of its use, the intrinsic variability in the time measurement makes it hard to obtain repeatable and accurate timing results of a program running on an operating system. We propose a novel execution time measurement protocol (termed EMP) for measuring the execution time of a compute‐bound program on Linux, while minimizing that measurement's variability. During the development of execution time measurement protocol, we identified several factors that disturb execution time measurement. We introduce successive refinements to the protocol by addressing each of these factors, in concert, reducing variability by more than an order of magnitude. We also introduce a new visualization technique, what we term ‘dual‐execution scatter plot’ that highlights infrequent, long‐running daemons, differentiating them from frequent and/or short‐running daemons. Our empirical results show that the proposed protocol successfully achieves three major aspects—precision, accuracy, and scalability—in execution time measurement that can work for open‐source and proprietary software. Copyright © 2017 John Wiley & Sons, Ltd.

It is surprisingly hard to obtain accurate and precise measurements of the time spent executing a query because there are many sources of variance. To understand these sources, we review relevant per-process and overall measures obtainable from the Linux kernel and introduce a structural causal model relating these measures. A thorough correlational analysis provides strong support for this model. We attempted to determine why a particular measurement wasn’t repeatable and then to devise ways to eliminate or reduce that variance. This enabled us to articulate a timing protocol that applies to proprietary DBMSes, that ensures the repeatability of a query, and that obtains a quite accurate query execution time while dropping very few outliers. This resulting query time measurement procedure, termed the Tucson Timing Protocol Version 2 (TTPv2), consists of the following steps: (i) perform sanity checks to ensure data validity; (ii) drop some query executions via clearly motivated predicates; (iii) drop some entire queries at a cardinality, again via clearly motivated predicates; (iv) for those that remain, compute a single measured time by a carefully justified formula over the underlying measures of the remaining query executions; and (v) perform post-analysis sanity checks. The result is a mature, general, robust, self-checking protocol that provides a more precise and more accurate timing of the query. The protocol is also applicable to other operating domains in which measurements of multiple processes each doing computation and I/O is needed.

Recruitment and retention of women has been a persistent problem in the field of computer science. With a growing number of jobs that require a computer science degree, this problem does not only affect computer science departments with low enrollment, but also impacts industry. There is still no universally accepted explanation for the underrepresentation of women in the computing field. Various solutions have been implemented in an attempt to resolve this problem and yet gender imbalance in fields related to computer science persists.

In the database field, while very strong mathematical and engineering work has been done, the scientific approach has been much less prominent. The deep understanding of query optimizers obtained through the scientific approach can lead to better engineered designs. Unlike other domains, there have been few DBMS-dedicated laboratories, focusing on such scientific investigation. In this demonstration, we present a novel DBMS-oriented research infrastructure, called Arizona Database Laboratory (AZDBLab), to assist database researchers in conducting a large-scale empirical study across multiple DBMSes. For them to test their hypotheses on the behavior of query optimizers, AZDBLab can run and monitor a large-scale experiment with thousands (or millions) of queries on different DBMSes. Furthermore, AZDBLab can help users automatically analyze these queries. In the demo, the audience will interact with AZDBLab through the stand-alone application and the mobile app to conduct such a large-scale experiment for a study. The audience will then run a Tucson Timing Protocol analysis on the finished experiment and then see the analysis (data sanity check and timing) results.

Software engineering frameworks tame the complexity of large collections of classes by identifying structural invariants, regularizing interfaces, and increasing sharing across the collection. We wish to appropriate these benefits for families of closely related benchmarks, say for evaluating query engine implementation strategies. We introduce the notion of a benchmark framework, an ecosystem of benchmarks that are related in semantically rich ways and enabled by organizing principles. A benchmark framework is realized by iteratively changing one individual benchmark into another, say by modifying the data format, adding schema constraints, or instantiating a different workload. Paramount to our notion of benchmark frameworks are the ease of describing the differences between individual benchmarks and the utility of methods to validate the correctness of each benchmark component by exploiting the overarching ecosystem. As a detailed case study, we introduce τBench, a benchmark framework consisting of ten individual benchmarks, spanning XML, XQuery, XML Schema, and PSM, along with temporal extensions to each. The second case study examines the Mining Unstructured Data benchmark framework, and the third examines the potential benefits of rendering the TPC family as a benchmark framework. Copyright © 2013 John Wiley & Sons, Ltd.

Time provides context for all our experiences, cognition, and coordinated collective action. Prior research in linguistics, artificial intelligence, and temporal databases suggests the need to differentiate between temporal facts with goal-related semantics (i.e., telic) from those are intrinsically devoid of culmination (i.e., atelic). To differentiate between telic and atelic data semantics in conceptual database design, we propose an annotation-based temporal conceptual model that generalizes the semantics of a conventional conceptual model. Our temporal conceptual design approach involves: 1) capturing "what" semantics using a conventional conceptual model; 2) employing annotations to differentiate between telic and atelic data semantics that help capture "when" semantics; 3) specifying temporal constraints, specifically nonsequenced semantics, in the temporal data dictionary as metadata. Our proposed approach provides a mechanism to represent telic/atelic temporal semantics using temporal annotations. We also show how these semantics can be formally defined using constructs of the conventional conceptual model and axioms in first-order logic. Via what we refer to as the "semantics of composition," i.e., semantics implied by the interaction of annotations, we illustrate the logical consequences of representing telic/atelic data semantics during temporal conceptual design.

It is surprisingly hard to obtain accurate and precise measurements of the time spent executing a query. We review relevant process and overall measures obtainable from the Linux kernel and introduce a structural causal model relating these measures. A thorough correlational analysis provides strong support for this model. Using this model, we developed a timing protocol, which (1) performs sanity checks to ensure validity of the data, (2) drops some query executions via clearly motivated predicates, (3) drops some entire queries at a cardinality, again via clearly motivated predicates, (4) for those that remain, for each computes a single measured time by a carefully justified formula over the underlying measures of the remaining query executions, and (5) performs post-analysis sanity checks. The resulting query time measurement procedure, termed the Tucson Protocol, applies to proprietary and open-source DBMSes.

Valid-time indeterminacy is "don't know when" indeterminacy, coping with cases in which one does not exactly know when a fact holds in the modeled reality. In this paper, we first propose a reference representation (data model and algebra) in which all possible temporal scenarios induced by valid-time indeterminacy can be extensionally modeled. We then specify a family of 16 more compact representational data models. We demonstrate their correctness with respect to the reference representation and analyze several properties, including their data expressiveness. Then, we compare these compact models along several relevant dimensions. Finally, we also extend the reference representation and a representative of compact representations to cope with probabilities.

In this article we present refinements on previously proposed approaches to forensic analysis of database tampering. We significantly generalize the basic structure of these algorithms to admit new characterizations of the “where” axis of the corruption diagram. Specifically, we introduce page-based partitioning as well as attribute-based partitioning along with their associated corruption diagrams. We compare the structure of all the forensic analysis algorithms and discuss the various design choices available with respect to forensic analysis. We characterize the forensic cost of the newly introduced algorithms, compare their forensic cost, and give our recommendations. We then introduce a comprehensive taxonomy of the types of possible corruption events, along with an associated forensic analysis protocol that consolidates all extant forensic algorithms and the corresponding type(s) of corruption events they detect. The result is a generalization of these algorithms and an overarching characterization of the process of database forensic analysis, thus providing a context within the overall operation of a DBMS for all existing forensic analysis algorithms.

Database management systems (DBMSes) form a cornerstone of modern IT infrastructure, and it is essential that they have excellent performance. Much of the work to date on optimizing DBMS performance has emphasized ensuring efficient data access from secondary storage. This paper shows that DBMSes can also benefit significantly from dynamic code specialization. Our approach focuses on the iterative query evaluation loops typically used by such systems. Query evaluation involves extensive references to the relational schema, predicate values, and join types, which are all invariant during query evaluation, and thus are subject to dynamic value-based code specialization.

Regulations and societal expectations have recently emphasized the need to mediate access to valuable databases, even access by insiders. Fraud occurs when a person, often an insider, tries to hide illegal activity. Companies would like to be assured that such tampering has not occurred, or if it does, that it will be quickly discovered and used to identify the perpetrator. At one end of the compliance spectrum lies the approach of restricting access to information and on the other that of information accountability. We focus on effecting information accountability of data stored in high-performance databases. The demonstrated work ensures appropriate use and thus end-to-end accountability of database information via a continuous assurance technology based on cryptographic hashing techniques. A prototype tamper detection and forensic analysis system named DRAGOON was designed and implemented to determine when tampering(s) occurred and what data were tampered with. DRAGOON is scalable, customizable, and intuitive. This work will show that information accountability is a viable alternative to information restriction for ensuring the correct storage, use, and maintenance of databases on extant DBMSes.

We show how to extend temporal support of SQL to the Turing-complete portion of SQL, that of persistent stored modules (PSM). Our approach requires minor new syntax beyond that already in SQL/Temporal to define and to invoke PSM routines, thereby extending the current, sequenced, and non-sequenced semantics of queries to PSM routines. Temporal upward compatibility (existing applications work as before when one or more tables are rendered temporal) is ensured. We provide a transformation that converts Temporal SQL/PSM to conventional SQL/PSM. To support sequenced evaluation of PSM routines, we define two different slicing approaches, maximal slicing and per-statement slicing. We compare these approaches empirically using a comprehensive benchmark and provide a heuristic for choosing between them.

Relational database management systems are general in the sense that they can handle arbitrary schemas, queries, and modifications, this generality is implemented using runtime metadata lookups and tests that ensure that control is channelled to the appropriate code in all cases. Unfortunately, these lookups and tests are carried out even when information is available that renders some of these operations superfluous, leading to unnecessary runtime overheads. This paper introduces micro-specialization, an approach that uses relation- and query-specific information to specialize the DBMS code at runtime and thereby eliminate some of these overheads. We develop a taxonomy of approaches and specialization times and propose a general architecture that isolates most of the creation and execution of the specialized code sequences in a separate DBMS-independent module. Through three illustrative types of micro-specializations applied to PostgreSQL, we show that this approach requires minimal changes to a DBMS and can improve the performance simultaneously across a wide range of queries, modifications, and bulk-loading, in terms of storage, CPU usage, and I/O time of the TPC-H and TPC-C benchmarks.

Information restriction controls access and renders records immutable, information accountability requires data transparency to easily and efficiently determine when a particular use is appropriate. Information accountability in the context of relational databases is associated with time in a surprising number of ways, as is summarized in this paper. Notarization and validation of a database exploit the temporal semantics of a transaction-time database. A corruption can be associated with multiple times. Forensic analysis determines the when: bounds on the corruption time, and the where: also specified in terms of time. These bounds are depicted in a two-dimensional corruption diagram, with both axes denoting time. The various kinds of corruption events are defined in terms of time. A parameter termed the regret interval has significant security and performance implications. This paper emphasizes the deep connections between time and the definition, detection, forensic analysis, and characterized extent of a database corruption within the context of information accountability.

If past versions of XML documents are retained, what of the various integrity constraints defined in XML Schema on those documents? This paper describes how to interpret such constraints as sequenced constraints, applicable at each point in time. We also consider how to add new variants that apply across time, so-called nonsequenced constraints. Our approach supports temporal documents that vary over both valid and transaction time, whose schema can vary over transaction time. We do this by replacing the schema with a (possibly time-varying) temporal schema and replacing the document with a temporal document, both of which are upward compatible with conventional XML and with conventional tools like XMLLINT, which we have extended to support the temporal constraints introduced here.

Valid-time indeterminacy concerns not knowing exactly when a fact holds in the modeled reality. In this paper, we first propose a reference approach (data model and algebra) in which all possible temporal scenarios induced by valid-time indeterminacy can be extensionally modeled. We then specify a family of sixteen more compact representational data models. We demonstrate their correctness with respect to the reference approach and analyze several properties, including their data expressiveness and correctness with respect to the reference approach. Finally, we compare these compact models along several relevant dimensions.

Tampering of a database can be detected through the use of cryptographically strong hash functions. Subsequently, applied forensic analysis algorithms can help determine when, what, and perhaps ultimately who and why. This paper presents a novel forensic analysis algorithm, the tiled Bitmap algorithm, which is more efficient than prior forensic analysis algorithms. It introduces the notion of a candidate set (all possible locations of detected tampering(s)) and provides a complete characterization of the candidate set and its cardinality. An optimal algorithm for computing the candidate set is also presented. Finally, the implementation of the tiled Bitmap algorithm is discussed, along with a comparison to other forensic algorithms in terms of space/time complexity and cost. An example of candidate set generation and proofs of the theorems and lemmata and of algorithm correctness can be found in the appendix, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TKDE.2009.121.

Spurred by financial scandals and privacy concerns, governments worldwide have moved to ensure confidence in digital records by regulating their retention and deletion. These requirements have led to a huge market for compliance storage servers, which ensure that data are not shredded or altered before the end of their mandatory retention period. These servers preserve unstructured and semi-structured data at a file-level granularity: email, spreadsheets, reports, instant messages. In this paper, we extend this level of protection to structured data residing in relational databases. We propose a compliant DBMS architecture and two refinements that illustrate the additional security that one can gain with only a slight performance penalty, with almost no modifications to the DBMS kernel. We evaluate our proposed architecture through experiments with TPC-C on a high-performance DBMS, and show that the runtime overhead for transaction processing is approximately 10% in typical configurations.

Regulations and societal expectations have recently expressed the need to mediate access to valuable databases, even by insiders. One approach is tamper detection via cryptographic hashing. This article shows how to determine when the tampering occurred, what data was tampered with, and perhaps, ultimately, who did the tampering, via forensic analysis. We present four successively more sophisticated forensic analysis algorithms: the Monochromatic, RGBY, Tiled Bitmap, and a3D algorithms, and characterize their “forensic cost” under worst-case, best-case, and average-case assumptions on the distribution of corruption sites. A lower bound on forensic cost is derived, with RGBY and a3D being shown optimal for a large number of corruptions. We also provide validated cost formulæ for these algorithms and recommendations for the circumstances in which each algorithm is indicated.

Computer science has long been considered to emphasize three distinct perspectives: mathematics, science, and engineering. While the database field has some very strong mathematical and engineering work, the scientific perspective has been much less prominent. This keynote elaborate the scientific perspective, apply it to research questions in temporal databases, and emphasize that this new way of thinking can yield new insights and deeper understanding.

Abstract Programmers are increasingly interested in developing applications that can be used internationally. Part of the internationalization effort is the ability to engineer applications to use dates and times that conform to local calendars yet can inter‐operate with dates and times in other calendars, for instance between the Gregorian and Islamic calendars. $\tau$ ZAMAN is a system that provides a natural language‐ and calendar‐independent framework for integrating multiple calendars. $\tau$ ZAMAN performs ‘runtime‐binding’ of calendars and language support. A running $\tau$ ZAMAN system dynamically loads calendars and language support tables from XML‐formatted files. Loading a calendar integrates it with other, already loaded calendars, enabling users of $\tau$ ZAMAN to add, compare, and convert times between multiple calendars. $\tau$ ZAMAN also provides a flexible, calendar‐independent framework for parsing temporal literals. Literals can be input and output in XML or plain text, using user‐defined formats, and in different languages and character sets. Finally, $\tau$ ZAMAN is a client/server system, enabling shared access to calendar servers spread throughout the Web. This paper describes the architecture of $\tau$ ZAMAN and experimentally quantifies the cost of using a calendar server to translate and manipulate dates. Copyright © 2006 John Wiley & Sons, Ltd.

This editorial analyzes from a variety of perspectives the controversial issue of single-blind versus double-blind reviewing. In single-blind reviewing, the reviewer is unknown to the author, but the identity of the author is known to the reviewer. Double-blind reviewing is more symmetric: The identity of the author and the reviewer are not revealed to each other. We first examine the significant scholarly literature regarding blind reviewing. We then list six benefits claimed for double-blind reviewing and 21 possible costs. To compare these benefits and costs, we propose a double-blind policy for TODS that attempts to minimize the costs while retaining the core benefit of fairness that double-blind reviewing provides, and evaluate that policy against each of the listed benefits and costs. Following that is a general discussion considering several questions: What does this have to do with TODS , does bias exist in computer science, and what is the appropriate decision procedure? We explore the “knobs” a policy design can manipulate to fine-tune a double-blind review policy. This editorial ends with a specific decision.

Mechanisms now exist that detect tampering of a database, through the use of cryptographically-strong hash functions. This paper addresses the next problem, that of determining who, when, and what, by providing a systematic means of performing forensic analysis after such tampering has been uncovered. We introduce a schematic representation termed a "corruption diagram" that aids in intrusion investigation. We use these diagrams to fully analyze the original proposal, that of a linked sequence of hash values. We examine the various kinds of intrusions that are possible, including retroactive, introactive, backdating, and postdating intrusions. We then introduce successively more sophisticated forensic analysis algorithms: the monochromatic, RGB, and polychromatic algorithms, and characterize the "forensic strength" of these algorithms. We show how forensic analysis can efficiently extract a good deal of information concerning a corruption event.

Our goal is to support transaction-time functionality that enables the coexistence of ordinary, non-temporal tables with transaction-time tables. In such a system, each transaction updating a transaction-time or snapshot table must include a timestamp for its updated data that correctly reflects the serialization order of the transactions, including transactions on ordinary tables. A serious issue is coping with SQL CURRENT/spl I.bar/TIME functions, which should return a time consistent with a transaction's timestamp and serialization order. Prior timestamping techniques cannot support such junctions with this desired semantics. We show how to compatibly extend conventional database functionality for transaction-time support by exploiting the database system lock manager and by utilizing a spectrum of optimizations.

Spatiotemporal databases are becoming increasingly more common. Typically, applications modeling spatiotemporal objects need to process vast amounts of data. In such cases, generating aggregate information from the data set is more useful than individually analyzing every entry. In this paper, we study the most relevant techniques for the evaluation of aggregate queries on spatial, temporal, and spatiotemporal data. We also present a model that reduces the evaluation of aggregate queries to the problem of selecting qualifying tuples and the grouping of these tuples into collections on which an aggregate function is to be applied. This model gives us a framework that allows us to analyze and compare the different existing techniques for the evaluation of aggregate queries. At the same time, it allows us to identify opportunities for research on types of aggregate queries that have not been studied.

While many real-world applications need to organize data based on space (e.g., geology, geomarketing, environmental modeling) and/or time (e.g., accounting, inventory management, personnel management), existing conventional conceptual models do not provide a straightforward mechanism to explicitly capture the associated spatial and temporal semantics. As a result, it is left to database designers to discover, design, and implement - on an ad hoc basis - the temporal and spatial concepts that they need. We propose an annotation-based approach that allows a database designer to focus first on nontemporal and nongeospatial aspects (i.e., "what") of the application and, subsequently, augment the conceptual schema with geospatiotemporal annotations (i.e., "when" and "where"). Via annotations, we enable a supplementary level of abstraction that succinctly encapsulates the geospatiotemporal data semantics and naturally extends the semantics of a conventional conceptual model. An overarching assumption in conceptual modeling has always been that expressiveness and formality need to be balanced with simplicity. We posit that our formally defined annotation-based approach is net only expressive, but also straightforward to understand and implement.

The analysis of the semantics of temporal data and queries plays a central role in the area of temporal databases. Although many different algebrae and models have been proposed, almost all of them are based on a point-based (snapshot) semantics for data. On the other hand, in the areas of linguistics, philosophy, and recently, artificial intelligence, an oft-debated issue concerns the use of an interval-based versus a point-based semantics. In this paper, we first show some problems inherent in the adoption of a point-based semantics for data, then argue that these problems arise because there is no distinction drawn in the data between telic and atelic facts. We then introduce a three-sorted temporal model and algebra including coercion functions for transforming relations of one sort into relations of the other at query time which properly copes with these issues.

Difference, intersection, semi join and anti-semi-join may be considered binary subset operators, in that they all return a subset of their left-hand argument. These operators are useful for implementing SQL's EXCEPT, INTERSECT, NOT IN and NOT EXISTS, distributed queries and referential integrity. Difference-all and intersection-all operate on multi-sets and track the number of duplicates in both argument relations; they are used to implement SQL's EXCEPT ALL and INTERSECT ALL. Their temporally sequenced analogues, which effectively apply the subset operator at each point in time, are needed for implementing these constructs in temporal databases. These SQL expressions are complex; most necessitate at least a three-way join, with nested NOT EXISTS clauses. We consider how to implement these operators directly in a DBMS. These operators are interesting in that they can fragment the left-hand validity periods (sequenced difference-all also fragments the right-hand periods) and thus introduce memory complications found neither in their non-temporal counterparts nor in temporal joins and semijoins. We introduce novel algorithms for implementing these operators by ordering the computation so that fragments need not be retained in main memory. We evaluate these algorithms and demonstrate that they are no more expensive than a single conventional join.

Joins are among the most frequently executed operations. Several fast join algorithms have been developed and extensively studied; these can be categorized as sort-merge, hash-based, and index-based algorithms. While all three types of algorithms exhibit excellent performance over most data, ameliorating the performance degradation in the presence of skew has been investigated only for hash-based algorithms. However, for sort-merge join, even a small amount of skew present in realistic data can result in a significant performance hit on a commercial DBMS. This paper examines the negative ramifications of skew in sort-merge join and proposes several refinements that deal effectively with data skew. Experiments show that some of these algorithms also impose virtually no penalty in the absence of data skew and are thus suitable for replacing existing sort-merge implementations. We also show how sort-merge band join performance is significantly enhanced with these refinements.

Primary key and referential integrity are the most widely used integrity constraints in relational databases. Each has a sequenced analogue in temporal databases, in which the constraint must apply independently at every point in time. In this paper, we assume a stratum approach, which expresses the checking in conventional SQL, as triggers on period-stamped relations. We evaluate several novel approaches that exploit B/sup +/-tree indexes to enable efficient checking of sequenced primary key (SPK) and sequenced referential integrity (SRI) constraints. We start out with a brute-force SPK algorithm, then adapt the relational interval-tree overlap algorithm. After that, we propose a new method, the straight traversal algorithm, which utilizes the B/sup +/-tree more directly in order to identify when multiple key values are present. Our evaluation, on two platforms, shows that the straight traversal algorithm approaches the performance of built-in nontemporal primary key and referential integrity checking, with a constant time per tuple.

Time-referenced data are pervasive in most real-world databases. Recent advances in temporal query languages show that such database applications may benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query optimization and evaluation mechanisms must be provided, either within the DBMS proper or as a source level translation from temporal queries to conventional SQL. This paper proposes a new approach: using a middleware component on top of a conventional DBMS. This component accepts temporal SQL statements and produces a corresponding query plan consisting of algebraic as well as regular SQL parts. The algebraic parts are processed by the middleware, while the SQL parts are processed by the DBMS. The middleware uses performance feedback from the DBMS to adapt its partitioning of subsequent queries into middleware and DBMS parts. The paper describes the architecture and implementation of the temporal middleware component, termed TANGO, which is based on the Volcano extensible query optimizer and the XXL query processing library. Experiments with the system demonstrate the utility of the middleware's internal processing capability and its cost-based mechanism for apportioning the processing between the middleware and the underlying DBMS.

Most real-world databases contain substantial amounts of time-referenced, or temporal, data. Recent advances in temporal query languages show that such database applications may benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query representation, optimization, and processing mechanisms must be provided. This paper presents a foundation for query optimization that integrates conventional and temporal query optimization and is suitable for both conventional DBMS architectures and ones where the temporal support is obtained via a layer on top of a conventional DBMS. This foundation captures duplicates and ordering for all queries, as well as coalescing for temporal queries, thus generalizing all existing approaches known to the authors. It includes a temporally extended relational algebra to which SQL and temporal SQL queries may be mapped, six types of algebraic equivalences, concrete query transformation rules that obey different equivalences, a procedure for determining which types of transformation rules are applicable for optimizing a query, and a query plan enumeration algorithm.

editorial Free Access Share on Editorial Author: Richard Snodgrass Department of Computer Science, University of Arizona. Department of Computer Science, University of Arizona.View Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 26Issue 4pp 385–387https://doi.org/10.1145/503099.505055Published:01 December 2001Publication History 0citation476DownloadsMetricsTotal Citations0Total Downloads476Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Most real-world database applications contain a substantial portion of time references, or temporal data. Recent advances in temporal query languages show that such database applications could benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query representation, optimization and processing mechanisms must be provided. This paper presents a general algebraic foundation for query optimization that integrates conventional and temporal query optimization and is suitable for providing temporal support both via a stand-alone temporal DBMS and via a layer on top of a conventional DBMS. By capturing duplicate removal and retention and order preservation for all queries, as well as coalescence for temporal queries, this foundation formalizes and generalizes existing approaches.

Granularity is an integral feature of temporal data. For instance, a person's age is commonly given to the granularity of years and the time of their next airline flight to the granularity of minutes. A granularity creates a discrete image, in terms of granules, of a (possibly continuous) time-line. We present a formal model for granularity in temporal operations that is integrated with temporal indeterminacy, or "don't know when" information. We also minimally extend the syntax and semantics of SQL-92 to support mixed granularities. This support rests on two operations, scale and cast, that move times between granularities, e.g., from days to months. We demonstrate that our solution is practical by showing how granularities can be specified in a modular fashion, and by outlining a time- and space-efficient implementation. The implementation uses several optimization strategies to mitigate the expense of accommodating multiple granularities.

The ability to model the temporal dimension is essential to many applications. Furthermore, the rate of increase in database size and response time requirements has out-paced advancements in processor and mass storage technology, leading to the need for parallel temporal database management systems. In this paper, we introduce a variety of parallel temporal aggregation algorithms for a shared-nothing architecture based on the sequential "aggregation tree algorithm". Via an empirical study, we found that the number of processing nodes, the partitioning of the data, the placement of results and the degree of data reduction effected by the aggregation impacted on the performance of the algorithms. For distributed results placement, we discovered that time-division merging was the obvious choice. For centralized results and high data reduction, pairwise merging was preferred, regardless of the number of processing nodes, but for low data reduction, it only performed well up to 32 nodes. This led us to a centralized variant of time-division merging which was best for larger configurations having low data reduction.

A wide range of database applications manage time-varying information. Existing database technology currently provides little support for managing such data. The research area of temporal databases has made important contributions in characterizing the semantics of such information and in providing expressive and efficient means to model, store, and query temporal data. This paper introduces the reader to temporal data management, surveys stale-of-the-art solutions to challenging aspects of temporal data management, and points to research directions.

Previous approaches to implementing temporal DBMSs have assumed that a temporal DBMS must be built from scratch, employing an integrated architecture and using new temporal implementation techniques such as temporal indexes and join algorithms. However, this is a very large and time-consuming task. The paper explores approaches to implementing a temporal DBMS as a stratum on top of an existing non-temporal DBMS, rendering implementation more feasible by reusing much of the functionality of the underlying conventional DBMS. More specifically, the paper introduces three stratum meta-architectures, each with several specific architectures. Based on a new set of evaluation criteria, advantages and disadvantages of the specific architectures are identified. The paper also classifies all existing temporal DBMS implementations according to the specific architectures they, employ. It is concluded that a stratum architecture is the best short, medium, and perhaps even long-term, approach to implementing a temporal DBMS.

In valid-time indeterminacy it is known that an event stored in a database did in fact occur, but it is not known exactly when . In this paper we extend the SQL data model and query language to support valid-time indeterminacy. We represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. We also describe query language constructs to retrieve information in the presence of indeterminacy. These constructs enable users to specify their credibility in the underlying data and their plausibility in the relationships among that data. A denotational semantics for SQL's select statement with optional credibility and plausibility constructs is given. We show that this semantics is reliable, in that it never produces incorrect information, is maximal, in that if it were extended to be more informative, the results may not be reliable, and reduces to the previous semantics when there is no indeterminacy. Although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. A contribution of this paper is to demonstrate that our approach is useful and practical. An efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. The cost of support for indeterminacy is empirically measured, and is shown to be modest. Finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for SQL3.

Although “ now ” is expressed in SQL and CURRENT_TIMESTAMP within queries, this value cannot be stored in the database. How ever, this notion of an ever-increasing current-time value has been reflected in some temporal data models by inclusion of database-resident variables, such as “ now ” “ until-changed, ” “**,” “@,” and “-”. Time variables are very desirable, but their used also leads to a new type of database, consisting of tuples with variables, termed a variable database.

Normal forms play a central role in the design of relational databases. Several normal forms for temporal relational databases have been proposed. These definitions are particular to specific temporal data models, which are numerous and incompatible. The paper attempts to rectify this situation. We define a consistent framework of temporal equivalents of the important conventional database design concepts: functional dependencies, primary keys, and third and Boyce-Codd normal forms. This framework is enabled by making a clear distinction between the logical concept of a temporal relation and its physical representation. As a result, the role played by temporal normal forms during temporal database design closely parallels that of normal forms during conventional database design. These new normal forms apply equally well to all temporal data models that have timeslice operators, including those employing tuple timestamping, backlogs, and attribute value timestamping. As a basis for our research, we conduct a thorough examination of existing proposals for temporal dependencies, keys, and normal forms. To demonstrate the generality of our approach, we outline how normal forms and dependency theory can also be applied to spatial and spatiotemporal databases.

Aggregate computation, such as selecting the minimum attribute value of a relation, is expensive, especially in a temporal database. We describe the basic techniques behind computing aggregates in conventional databases and show that these techniques are not efficient when applied to temporal databases. We examine the problem of computing constant intervals (intervals of time for which the aggregate value is constant) used for temporal grouping. We introduce two new algorithms for computing temporal aggregates: the aggregation tree and the k-ordered aggregation tree. An empirical comparison demonstrates that the choice of algorithm depends in part on the amount of memory available, the number of tuples in the underlying relation, and the degree to which the tuples are ordered. This study shows that the simplest strategy is to first sort the underlying relation, then apply the k-ordered aggregation tree algorithm with k=1.>

A temporal database contains time-varying data. In a real-time database transactions have deadlines or timing constraints. In this paper we review the substantial research in these two previously separate areas. First we characterize the time domain; then we investigate temporal and real-time data models. We evaluate temporal and real-time query languages along several dimensions. We examine temporal and real-time DBMS implementation. Finally, we summarize major research accomplishments to date and list several unanswered research questions.>

Joins are arguably the most important relational operators. Poor implementations are tantamount to computing the Cartesian product of the input relations. In a temporal database, the problem is more acute for two reasons. First, conventional techniques are designed for the optimization of joins with equality predicates, rather than the inequality predicates prevalent in valid-time queries. Second, the presence of temporally-varying data dramatically increases the size of the database. These factors require new techniques to efficiently evaluate valid-time joins. The authors address this need for efficient join evaluation in databases supporting valid-time. A new temporal-join algorithm based on tuple partitioning is introduced. This algorithm avoids the quadratic cost of nested-loop evaluation methods; it also avoids sorting. Performance comparisons between the partition-based algorithm and other evaluation methods are provided. While the paper focuses on the important valid-time natural join, the techniques presented are also applicable to other valid-time joins.>

Spatial and temporal databases are important and well-established sub-disciplines of database research. Some 350 papers in temporal databases have appeared, authored by almost 300 researchers. The literature on spatial databases is also substantial; the bibliography of Samet's landmark book on spatial data structures lists 823 references.

Abstract In this paper we provide efficient algorithms for converting between timestamp values that signify some number of seconds from an arbitrary origin, and character strings specifying Gregorian dates, such as ‘January 1, 1993’. We give several algorithms that explore a range of time and space trade‐offs. Unlike previous algorithms, those discussed here have a constant time cost over a greatly extended range of timestamp values. These algorithms are especially useful in operating systems and in database management systems.

A standard relation has two dimensions: attributes and tuples. A temporal relation contains two additional orthogonal time dimensions: valid time records when facts are true in the modeled reality, and transaction time records when facts are stored in the temporal relation. Although there are no restrictions between the valid time and transaction time associated with each fact, in many practical applications the valid and transaction times exhibit restricted interrelationships that define several types of specialized temporal relations. This paper examines areas where different specialized temporal relations are present. In application systems with multiple, interconnected temporal relations, multiple time dimensions may be associated with facts as they flow from one temporal relation to another. The paper investigates several aspects of the resulting generalized temporal relations, including the ability to query a predecessor relation from a successor relation. The presented framework for generalization and specialization allows one to precisely characterize and compare temporal relations and the application systems in which they are embedded. The framework's comprehensiveness and its use in understanding temporal relations are demonstrated by placing previously proposed temporal data models within the framework. The practical relevance of the defined specializations and generalizations is illustrated by sample realistic applications in which they occur. The additional semantics of specialized relations are especially useful for improving the performance of query processing.>

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.>

A conceptual temporal data model that captures the time-dependent semantics of data while permitting multiple data models at the representation level is described. A conceptual notion of a bitemporal relation in which tuples are stamped with sets of two-dimensional chronons in transaction-time/valid-time space is defined. A tuple-timestamped first normal form representation is introduced to show how the conceptual bitemporal data model is related, by means of snapshot equivalence, with representational models. Querying within the two-level framework is discussed. An algebra is defined at the conceptual level and mapped to the sample representational model in such a way that new operators compute equivalent results for different representations of the same conceptual bitemporal relation.>

This paper defines new constructs to support aggregation in the temporal query language TQuel and presents their formal semantics in the tuple relational calculus. A formal semantics for Quel aggregates is defined in the process. Multiple aggregates; aggregates appearing in the where, when, and valid clauses; nested aggregation; and instantaneous, cumulative, moving window, and unique variants are supported. These aggregates provide a rich set of statistical functions that range over time, while requiring minimal additions to TQuel and its semantics. We show how the aggregates may be supported in an historical algebra, both in a batch and in an incremental fashion, demonstrating that implementation is straightforward and efficient.>

Achieving high performance for parallel or distributed programs often requires substantial amounts of information about the programs themselves, about the systems on which they are executing, and about specific program runs. The monitoring system that collects, analyzes, and makes application-dependent monitoring information available to the programmer and to the executing program is presented. The system may be used for off-line program analysis, for on-line debugging, and for making on-line, dynamic changes to parallel or distributed programs to enhance their performance. The authors use a high-level, uniform data model for the representation of program information and monitoring data. They show how this model may be used for the specification of program views and attributes for monitoring, and demonstrate how such specifications can be translated into efficient, program-specific monitoring code that uses alternative mechanisms for the distributed analysis and collection to be performed for the specified views. The model's utility has been demonstrated on a wide variety of parallel machines.>

The authors explore a variety of temporal relations with specialized relationships between transaction and valid time. An example is a retroactive temporal event relation, where the event must have occurred before it was stored, i.e., the valid time-stamp is restricted to be less than the transaction time-stamp. The authors discuss many useful restrictions, defining a large number of specialized types of temporal relations, and indicate some of their applications. A detailed taxonomy of specialized temporal relations is presented. This taxonomy may be used during database design to specify the particular time semantics of temporal relations.>

The Interface Description Language (IDL) is a notation for describing the characteristics of data structures passed among collections of cooperating processes in a programming environment. The authors discuss a mapping from IDL to C data structures and macro definitions that supports the full language and is type safe and run-time efficient, but is not particularly compile-time efficient nor easy to use. They then propose that the mapping be performed in a preprocessor, thereby achieving efficiency and ease of use as well.>

Monitoring is an essential part of many program development tools, and plays a central role in debugging, optimization, status reporting, and reconfiguration. Traditional monitoring techniques are inadequate when monitoring complex systems such as multiprocessors or distributed systems. A new approach is described in which a historical database forms the conceptual basis for the information processed by the monitor. This approach permits advances in specifying the low-level data collection, specifying the analysis of the collected data, performing the analysis, and displaying the results. Two prototype implementations demonstrate the feasibility of the approach.

The authors summarize the trace specification language and present the trace specification methodology: a set of heuristics designed to make the reading and writing of complex specifications manageable. Also described is a technique for constructing formal, executable models from specifications written using the methodology. These models are useful as proof of specification consistency and as executable prototypes. Fully worked examples of the methodology and the model building techniques are included.>

In this paper we discuss extensions to the conventional relational algebra to support transaction time. We show that these extensions are applicable to historical algebras that support valid time, yielding a temporal algebraic language. Since transaction time concerns the storage of information in the database, the notion of state is central. The extensions are formalized using denotational semantics. The additions preserve the useful properties of the conventional relational algebra.

Recently, attention has been focused on temporal databases , representing an enterprise over time. We have developed a new language, Tquel , to query a temporal database. TQuel was designed to be a minimal extension, both syntactically and semantically, of Quel, the query language in the Ingres relational database management system. This paper discusses the language informally, then provides a tuple relational calculus semantics for the TQuel statements that differ from their Quel counterparts, including the modification statements. The three additional temporal constructs defined in Tquel are shown to be direct semantic analogues of Quel's where clause and target list. We also discuss reducibility of the semantics to Quel's semantics when applied to a static database. TQuel is compared with ten other query languages supporting time.

A prototype of a temporal database management system was built by extending Ingres. It supports the temporal query language TQuel, a superset of Quel, handling four types of database static, rollback, historical and temporal. A benchmark set of queries was run to study the performance of the prototype on the four types of databases. We analyze the results of the benchmark, and identify major factors that have the greatest impact on the performance of the system. We also discuss several mechanisms to address the performance bottlenecks we encountered.

Recently, attention has been focussed on historical databases (HDBs), representing an enterprise over time. We have developed a new language, TQuel, to query an HDB. TQuel is a superset of Quel, the query language in the Ingres relational database management system. This paper provides an overview of the language, motivating the various design decisions with the objective that it be a minimal extension, both syntactically and semantically, of Quel.

This paper introduces the concept of an integrated instrumentation environment (IIE) for multiprocessors. The primary objective of such an environment is to assist the user in the process of experimentation. The emphasis in an IIE is on experiment management (including stimulus generation, monitoring, data collection and analysis), rather than on techniques for program development as in conventional programming environments. We believe the functionality of the two environments should eventually be provided in one comprehensive environment.

This paper describes Cola, an object-oriented command language for Hydra; Hydra is a capability-based operating system that runs on C.mmp, a tightly coupled multiprocessor. The two primary aspects of Cola, that it is a command language for Hydra, and that it is based on the object paradigm, are examined. Cola was designed to effect a correspondence between capabilities in Hydra and objects that are supported by the language. Cola is based on Smalltalk in that it uses message-passing as a control structure to allow syntactic freedom in the expression of commands to the system. Cola objects are arranged in a hierarchy, and the message-passing mechanism was designed to exploit this structure by automatically forwarding an unanswered message up the hierarchy. Two ramifications of this mechanism, automatic inheritance and shadowing, are discussed. An evaluation of the design decisions is also given.