Vector search plays a crucial role in many real-world applications. In addition to single-vector search, multi-vector search becomes important for multi-modal and multi-feature scenarios today. In a multi-vector database, each row is an item, each column represents a feature of items, and each cell is a high-dimensional vector. In multi-vector databases, the choice of indexes can have a significant impact on performance. Although index tuning for relational databases has been extensively studied, index tuning for multi-vector search remains unclear and challenging. In this paper, we define multi-vector search index tuning and propose a framework to solve it. Specifically, given a multi-vector search workload, we develop algorithms to find indexes that minimize latency and meet storage and recall constraints. Compared to the baseline, our latency achieves 2.1X to 8.3X speedup.

Microsoft Orleans is a popular open source distributed programming framework and platform which invented the virtual actor model, and has since evolved into an actor-oriented database system with the addition of database abstractions such as ACID transactions. Properties of Orleans' virtual actor model imply that any ACID transaction mechanism for operations spanning multiple actors must support distributed transactions on top of pluggable cloud storage drivers. Unfortunately, distributed transactions usually perform poorly in this environment, partly because of the high performance and contention overhead of performing two-phase commit (2PC) on slow cloud storage systems. In this paper we describe the design and implementation of ACID transactions in Orleans. The system uses two primary techniques to mask the high latency of cloud storage and enable high transaction throughput. First, Orleans pioneered the use of a distributed form of early lock release by releasing all of a transaction's locks during phase one of 2PC, and by tracking commit dependencies to implement cascading abort. This avoids blocking transactions while running 2PC and enables a distributed form of group commit. Second, Orleans leverages reconnaissance queries to prefetch the state of all actors involved in a transaction from cloud storage prior to running the transaction and acquiring any locks, thus ensuring no locks are held while blocking on high latency cloud storage in most cases.

This paper presents DDS, a novel disaggregated storage architecture enabled by emerging networking hardware, namely DPUs (Data Processing Units). DPUs can optimize the latency and CPU consumption of disaggregated storage servers. However, utilizing DPUs for DBMSs requires careful design of the network and storage paths and the interface exposed to the DBMS. To fully benefit from DPUs, DDS heavily uses DMA, zero-copy, and userspace I/O to minimize overhead when improving throughput. It also introduces an offload engine that eliminates host CPUs by executing client requests directly on the DPU. Adopting DDS' API requires minimal DBMS modification. Our experimental study and production system integration show promising results---DDS achieves higher disaggregated storage throughput with an order of magnitude lower latency, and saves up to tens of CPU cores per storage server.

Window aggregates are ubiquitous in stream processing. In Azure Stream Analytics (ASA), a stream processing service hosted by Microsoft's Azure cloud, we see many customer queries that contain aggregate functions (such as MIN and MAX) over multiple correlated windows (e.g., tumbling windows of length five minutes and ten minutes) defined on the same event stream. In this paper, we present a cost-based optimization framework for optimizing such queries by sharing computation among multiple windows. In particular, we introduce the notion of factor windows, which are auxiliary windows that are not in the input query but may nevertheless help reduce the overall computation cost, and our cost-based optimizer can produce rewritten query plans that have lower costs than the original query plan by utilizing factor windows. Since our optimization techniques are at the level of query (plan) rewriting, they can be implemented on any stream processing system that supports a declarative, SQL-like query language without changing the underlying query execution engine. We formalize the shared computation problem, present the optimization techniques in detail, and report evaluation results over both synthetic and real datasets. Our results show that, compared to the original query plans, the rewritten plans output by our cost-based optimizer can yield significantly higher (up to 16.8×) throughput.

Index tuning aims to find the optimal index configuration for an input workload. It is a resource-intensive task since it requires making multiple expensive "what-if" calls to the query optimizer to estimate the cost of a query given an index configuration without actually building the indexes. In this paper, we study the problem of budget-aware index tuning where the number of what-if calls allowed when searching for the optimal configuration during tuning is constrained. This problem is challenging as it requires addressing the trade-off between investing what-if calls on exploring new configurations versus exploiting a known promising configuration. We formulate budget-aware index tuning as a Markov decision process, and propose a solution based on Monte Carlo tree search, a classic reinforcement learning technology. Experimental evaluation on both standard industry benchmarks and real workloads shows that our solution can significantly outperform alternative budget-aware solutions in terms of the quality of the index configuration.

Two-phase commit (2PC) is widely used in distributed databases to ensure atomicity of distributed transactions. Conventional 2PC was originally designed for the shared-nothing architecture and has two limitations: long latency due to two eager log writes on the critical path, and blocking of progress when a coordinator fails. Modern cloud-native databases are moving to a storage disaggregation architecture where storage is a shared highly-available service. Our key observation is that disaggregated storage enables protocol innovations that can address both the long-latency and blocking problems. We develop Cornus, an optimized 2PC protocol to achieve this goal. The only extra functionality Cornus requires is an atomic compare-and-swap capability in the storage layer, which many existing storage services already support. We present Cornus in detail and show how it addresses the two limitations. We also deploy it on real storage services including Azure Blob Storage and Redis. Empirical evaluations show that Cornus can achieve up to 1.9X latency reduction over conventional 2PC.

A common stream processing application is alerting, where the data stream management system (DSMS) continuously evaluates a threshold function over incoming streams. If the threshold is crossed, the DSMS raises an alarm. The threshold function is often calculated over two or more streams, such as combining temperature and humidity readings to determine if moisture will form on a machine and therefore cause it to malfunction. This requires taking a temporal join across the input streams. We show that for the broad class of functions called quasiconvex functions, the DSMS needs to retain very few tuples per-data-stream for any given time interval and still never miss an alarm. This surprising result yields a large memory savings during normal operation. That savings is also important if one stream fails, since the DSMS would otherwise have to cache all tuples in other streams until the failed stream recovers. We prove our algorithm is optimal and provide experimental evidence that validates its substantial memory savings.

Redy is a cloud service that provides high performance caches using RDMA-accessible remote memory. An application can customize the performance of each cache with a service level objective (SLO) for latency and throughput. By using remote memory, it can leverage stranded memory and spot VM instances to reduce the cost of its caches and improve data center resource utilization. Redy automatically customizes the resource configuration for the given SLO, handles the dynamics of remote memory regions, and recovers from failures. The experimental evaluation shows that Redy can deliver its promised performance and robustness under remote memory dynamics in the cloud. We augment a production key-value store, FASTER, with a Redy cache. When the working set exceeds local memory, using Redy is significantly faster than spilling to SSDs.

We present the vision of an actor-oriented database. Its goal is to integrate database abstractions into an actor-oriented programming language for interactive, stateful, scalable, distributed applications that use cloud storage.

Many service applications use actors as a programming model for the middle tier, to simplify synchronization, fault-tolerance, and scalability. However, efficient operation of such actors in multiple, geographically distant datacenters is challenging, due to the very high communication latency. Caching and replication are essential to hide latency and exploit locality; but it is not a priori clear how to combine these techniques with the actor programming model. We present Geo, an open-source geo-distributed actor system that improves performance by caching actor states in one or more datacenters, yet guarantees the existence of a single latest version by virtue of a distributed cache coherence protocol. Geo's programming model supports both volatile and persistent actors, and supports updates with a choice of linearizable and eventual consistency. Our evaluation on several workloads shows substantial performance benefits, and confirms the advantage of supporting both replicated and single-instance coherence protocols as configuration choices. For example, replication can provide fast, always-available reads and updates globally, while batching of linearizable storage accesses at a single location can boost the throughput of an order processing workload by 7x.

Scaling-out a database system typically requires partitioning the database across multiple servers. If applications do not partition perfectly, then transactions accessing multiple partitions end up being distributed, which has well-known scalability challenges. To address them, we describe a high-performance transaction mechanism that uses optimistic concurrency control on a multi-versioned tree-structured database stored in a shared log. The system scales out by adding servers, without partitioning the database.

We study the following problem: given the name of an ad-hoc concept as well as a few seed entities belonging to the concept, output all entities belonging to it. Since producing the exact set of entities is hard, we focus on returning a ranked list of entities. Previous approaches either use seed entities as the only input, or inherently require negative examples. They suffer from input ambiguity and semantic drift, or are not viable options for ad-hoc tail concepts. In this paper, we propose to leverage the millions of tables on the web for this problem. The core technical challenge is to identify the ``exclusive'' tables for a concept to prevent semantic drift; existing holistic ranking techniques like personalized PageRank are inadequate for this purpose. We develop novel probabilistic ranking methods that can model a new type of table-entity relationship. Experiments with real-life concepts show that our proposed solution is significantly more effective than applying state-of-the-art set expansion or holistic ranking techniques.

In large enterprises, data discovery is a common problem faced by users who need to find relevant information in relational databases. In this scenario, schema annotation is a useful tool to enrich a database schema with descriptive keywords. In this paper, we demonstrate Barcelos, a system that automatically annotates corporate databases. Unlike existing annotation approaches that use Web oriented knowledge bases, Barcelos mines enterprise spreadsheets to find candidate annotations. Our experimental evaluation shows that Barcelos produces high quality annotations; the top-5 have an average precision of 87%.

XML is commonly supported by SQL database systems. However, existing mappings of XML to tables can only deliver satisfactory query performance for limited use cases. In this paper, we propose a novel mapping of XML data into one wide table whose columns are sparsely populated. This mapping provides good performance for document types and queries that are observed in enterprise applications but are not supported efficiently by existing work. XML queries are evaluated by translating them into SQL queries over the wide sparsely-populated table. We show how to translate full XPath 1.0 into SQL. Based on the characteristics of the new mapping, we present rewriting optimizations that dramatically reduce the number of joins. Experiments demonstrate that query evaluation over the new mapping delivers considerable improvements over existing techniques for the target use cases.

There has been a resurgence of work on replicated, distributed database systems to meet the demands of intermittently-connected clients and of disaster-tolerant databases that span data centers. Many systems weaken the criteria for replica-consistency or isolation, and in some cases add new mechanisms, to improve partition-tolerance, availability, and performance. We present a framework for comparing these criteria and mechanisms, to help architects navigate through this complex design space.

In an object-to-relational mapping system (ORM), mapping expressions explain how to expose relational data as objects and how to store objects in tables. If mappings are sufficiently expressive, then it is possible to define lossy mappings. If a user updates an object, stores it in the database based on a lossy mapping, and then retrieves the object from the database, the user might get a different result than the updated state of the object; that is, the mapping might not "roundtrip." To avoid this, the ORM should validate that user-defined mappings roundtrip the data. However, this problem is NP-hard, so mapping validation can be very slow for large or complex mappings.

We describe a software architecture we have developed for a constructive containment checker of Entity SQL queries defined over extended ER schemas expressed in Microsoft's Entity Data Model. Our application of interest is compilation of object-to-relational mappings for Microsoft's ADO.NET Entity Framework, which has been shipping since 2007. The supported language includes several features which have been individually addressed in the past but, to the best of our knowledge, they have not been addressed all at once before. Moreover, when embarking on an implementation, we found no guidance in the literature on how to modularize the software or apply published algorithms to a commercially-supported language. This paper reports on our experience in addressing these real-world challenges.

XML is commonly supported by SQL database systems. However, existing mappings of XML to tables can only deliver satisfactory query performance for limited use cases. In this paper, we propose a novel mapping of XML data into one wide table whose columns are sparsely populated. This mapping provides good performance for document types and queries that are observed in enterprise applications but are not supported efficiently by existing work. XML queries are evaluated by translating them into SQL queries over the wide sparsely-populated table. We show how to translate full XPath 1.0 into SQL. Based on the characteristics of the new mapping, we present rewriting optimizations that minimize the number of joins. Experiments demonstrate that query evaluation over the new mapping delivers considerable improvements over existing techniques for the target use cases.

Cloud SQL Server is a relational database system designed to scale-out to cloud computing workloads. It uses Microsoft SQL Server as its core. To scale out, it uses a partitioned database on a shared-nothing system architecture. Transactions are constrained to execute on one partition, to avoid the need for two-phase commit. The database is replicated for high availability using a custom primary-copy replication scheme. It currently serves as the storage engine for Microsoft's Exchange Hosted Archive and SQL Azure.

Object-relational mapping systems have become often-used tools to provide application access to relational databases. In a database-first development scenario, the onus is on the developer to construct a meaningful object layer for the application because shipping tools, as ORM tools only ship database reverse-engineering tools that generate objects with a trivial one-to-one mapping. We built a tool, EdmGen++, that combines pattern-finding rules from conceptual modelling literature with configurable conditions that increase the likelihood that found patterns are semantically relevant. EdmGen++ produces a conceptual model with inheritance in Microsoft's Entity Data Model, which Microsoft's Entity Framework uses to support an executable object-to-relational mapping. The execution time of EdmGen++ on customer databases is reasonable for design-time.

Schema evolution is an unavoidable consequence of the application development lifecycle. The two primary schemas in an application, the client conceptual object model and the persistent database model, must co-evolve or risk quality, stability, and maintainability issues. We present MoDEF, an extension to Visual Studio that supports automatic evolution of object-relational mapping artifacts in the Microsoft Entity Framework. When starting with a valid mapping between client and store, MoDEF translates changes made to a client model into incremental changes to the store as an upgrade script, along with a new valid mapping to the new store. MoDEF mines the existing mapping for mapping patterns which MoDEF reuses for new client artifacts.

Many of the largest database-driven web sites use custom web-scale data managers (WDMs). On the surface, these WDMs are being applied to problems that are well-suited for relational database systems. Some examples are the following: • Map-Reduce [5], Hadoop [7], and Dryad [9] are used to process queries on large data sets using sequential scan and aggregation. Hive [8] is a data warehouse built on Hadoop. • Google's Bigtable [3] is used to store a replicated table of rows of semi-structured data. • Amazon's Dynamo [6] is used to store partitioned, replicated databases of key-value pairs. Cassandra [2] is similar. • Object caching systems are used instead of a persistent store, such as memcached [10], Oracle's Coherence, and Microsoft's Velocity project.

We address the problem of unsupervised matching of schema information from a large number of data sources into the schema of a data warehouse. The matching process is the first step of a framework to integrate data feeds from third-party data providers into a structured-search engine's data warehouse. Our experiments show that traditional schema-based and instance-based schema matching methods fall short. We propose a new technique based on the search engine's clicklogs. Two schema elements are matched if the distribution of keyword queries that cause click-throughs on their instances are similar. We present experiments on large commercial datasets that show the new technique has much better accuracy than traditional techniques.

Developers need to programmatically access persistent XML data. Object-oriented access is often the preferred method. Translating XML data into objects or vice-versa is a hard problem due to the data model mismatch and the difficulty of query translation. We propose a framework that addresses this problem by transforming object-based queries and updates into queries and updates on XML using flexible, declarative mappings between classes and XML schema types. The same mappings are used to shred XML fragments from query results into client-side objects. Information in the XML store that is not mapped using the mapping language, such as comments and processing instructions, are also made available in the object representation.

We address the problem of generating a mediated schema from a set of relational data source schemas and conjunctive queries that specify where those schemas overlap. Unlike past approaches that generate only the mediated schema, our algorithm also generates view definitions, i.e., source-to-mediated schema mappings.

Model management is a high-level programming language designed to efficiently manipulate schemas and mappings. It is comprised of robust operators that combined in short programs can solve complex metadata-oriented problems in a compact way. For instance, countless enterprise data integration scenarios can be easily expressed in this high-level language thus saving hundreds of development man-hours. Here we present the first model management engine that has reverse-engineering support for data integration, which is one of the most pressing metadata-oriented problems. It merges two schemas based on the mappings between them and allows user to correct the result keeping all the mappings in sync automatically. For user it is much more convenient than determining which mappings to correct in order to get desired result. In addition, the engine supports restructuring merging which is important when the sources are structured differently and cannot be mapped directly. While making schema merging fully automatic is not yet possible, our work simplifies and automates this process to make it practical in complex data integration scenarios.

Developers need to access persistent XML data programmatically. Object-oriented access is often the preferred method. Translating XML data into objects or vice-versa is a hard problem due to the data model mismatch and the difficulty of query translation. Our prototype addresses this problem by transforming object-based queries and updates into queries and updates on XML using declarative mappings between classes and XML schema types. Our prototype extends the ADO.NET Entity Framework and leverages its object-relational mapping capabilities. We demonstrate how a developer can interact with stored relational and XML data using the Language Integrated Query (LINQ) feature of .NET. We show how LINQ queries are translated into a combination of SQL and XQuery. Finally, we illustrate how explicit mappings facilitate data independence upon database refactoring.

Translating data and data access operations between applications and databases is a longstanding data management problem. We present a novel approach to this problem, in which the relationship between the application data and the persistent storage is specified using a declarative mapping, which is compiled into bidirectional views that drive the data transformation engine. Expressing the application model as a view on the database is used to answer queries, while expressing the database schema as a view on the application model allows us to leverage view maintenance algorithms for update translation. This approach has been implemented in a commercial product. It enables developers to interact with a relational database via a conceptual schema and an object-oriented programming surface. We outline the implemented system and focus on the challenges of mapping compilation, which include rewriting queries under constraints and supporting nonrelational constructs.

Model management is a generic approach to solving problems of data programmability where precisely engineered mappings are required. Applications include data warehousing, e-commerce, object-to-relational wrappers, enterprise information integration, database portals, and report generators. The goal is to develop a model management engine that can support tools for all of these applications. The engine supports operations to match schemas, compose mappings, diff schemas, merge schemas, translate schemas into different data models, and generate data transformations from mappings.

Translating data and data access operations between applications and databases is a longstanding data management problem. We present a novel approach to this problem, in which the relationship between the application data and the persistent storage is specified using a declarative mapping, which is compiled into bidirectional views that drive the data transformation engine. Expressing the application model as a view on the database is used to answer queries, while viewing the database in terms of the application model allows us to leverage view maintenance algorithms for update translation. This approach has been implemented in a commercial product. It enables developers to interact with a relational database via a conceptual schema and an object oriented programming surface. We outline the implemented system and focus on the challenges of mapping compilation, which include rewriting queries under constraints and supporting non-relational constructs.

Composition of mappings between schemas is essential to support schema evolution, data exchange, data integration, and other data management tasks. In many applications, mappings are given by embedded dependencies. In this article, we study the issues involved in composing such mappings. Our algorithms and results extend those of Fagin et al. [2004], who studied the composition of mappings given by several kinds of constraints. In particular, they proved that full source-to-target tuple-generating dependencies (tgds) are closed under composition, but embedded source-to-target tgds are not. They introduced a class of second-order constraints, SO tgds , that is closed under composition and has desirable properties for data exchange. We study constraints that need not be source-to-target and we concentrate on obtaining (first-order) embedded dependencies. As part of this study, we also consider full dependencies and second-order constraints that arise from Skolemizing embedded dependencies. For each of the three classes of mappings that we study, we provide: (a) an algorithm that attempts to compute the composition; and (b) sufficient conditions on the input mappings which guarantee that the algorithm will succeed. In addition, we give several negative results. In particular, we show that full and second-order dependencies that are not limited to be source-to-target are not closed under composition (for the latter, under the additional restriction that no new function symbols are introduced). Furthermore, we show that determining whether the composition can be given by these kinds of dependencies is undecidable.

Many applications, such as e-commerce, routinely use copies of data that are not in sync with the database due to heuristic caching strategies used to enhance performance. We study concurrency control for a transactional model that allows update transactions to read out-of-date copies. Each read operation carries a "freshness constraint" that specifies how fresh a copy must be in order to be read. We offer a definition of correctness for this model and present algorithms to ensure several of the most interesting freshness constraints. We outline a serializability-theoretic correctness proof and present the results of a detailed performance study.

A customizable and extensible tool is proposed to implement ModelGen, the model management operator that translates a schema from one model to another. A wide family of models is handled, by using a metamodel in which models can be succinctly and precisely described. The approach is novel because the tool exposes the dictionary that stores models, schemas, and the rules used to implement translations. In this way, the transformations can be customized and the tool can be easily extended.

Schema matching is the problem of identifying corresponding elements in different schemas. Discovering these correspondences or matches is inherently difficult to automate. Past solutions have proposed a principled combination of multiple algorithms. However, these solutions sometimes perform rather poorly due to the lack of sufficient evidence in the schemas being matched. In this paper we show how a corpus of schemas and mappings can be used to augment the evidence about the schemas being matched, so they can be matched better. Such a corpus typically contains multiple schemas that model similar concepts and hence enables us to learn variations in the elements and their properties. We exploit such a corpus in two ways. First, we increase the evidence about each element being matched by including evidence from similar elements in the corpus. Second, we learn statistics about elements and their relationships and use them to infer constraints that we use to prune candidate mappings. We also describe how to use known mappings to learn the importance of domain and generic constraints. We present experimental results that demonstrate corpus-based matching outperforms direct matching (without the benefit of a corpus) in multiple domains.

Composition of mappings between schemas is essential to support schema evolution, data exchange, data integration, and other data management tasks. In many applications, mappings are given by embedded dependencies. In this paper, we study the issues involved in composing such mappings.

This paper is a short introduction to an industrial session on the use of meta data to address data integration problems in large enterprises. The main topics are data discovery, version and configuration management, and mapping development.

Model management is an approach to simplify the programming of metadata-intensive applications. It offers developers powerful operators, such as Compose, Diff, and Merge, that are applied to models, such as database schemas or interface specifications, and to mappings between models. Prior model management solutions focused on a simple class of mappings that do not have executable semantics. Yet many metadata applications require that mappings be executable, expressed in SQL, XSLT, or other data transformation languages.In this paper, we develop a semantics for model-management operators that allows applying the operators to executable mappings. Our semantics captures previously-proposed desiderata and is language-independent: the effect of the operators is expressed in terms of what they do to the instances of models and mappings. We describe an implemented prototype in which mappings are represented as dependencies between relational schemas, and discuss algebraic optimization of model-management scripts.

By meta data management, we mean techniques for manipulating schemas and schema-like objects (such as interface definitions and web site maps) and mappings between them. Work on meta data problems goes back to at least the early 1970s, when data translation was the hot database research topic, even before relational databases caught on. Many popular research problems in the past five years are primarily meta data problems, such as data warehouse tools (e.g., ETL – to extract, transform and load), data integration, the semantic web, generation of XML or object-oriented wrappers for SQL databases, and generation of wrappers for web sites. Other classical meta data problems are information resource management, design tool support and integration, and schema evolution and data migration. Despite its longevity and continued importance, there is no widely-accepted conceptual framework for the meta data field, as there is for many other database topics, such as access methods, query processing, and transaction management. In this seminar, we propose such a conceptual framework. It consists of three layers: applications, design patterns, and basic operators. Applications are the end-user problems to be solved, like those listed in the previous paragraph. Design patterns are generic problems that need to be solved in support of many different applications, such as meta modeling (for all meta data problems), answering queries using views (for data integration and the semantic web), and change propagation (for data translation, schema evolution, and round-trip engineering). Basic operators are procedures that are needed to support multiple design patterns and applications, such as matching schemas to produce a mapping, merging schemas based on a mapping, and composing mappings. We will describe several meta data management problems, and for each, we will explain the design patterns and operators that are needed to solve it. We will summarize the main approaches to each design pattern and operator – the main choices of language, data structures, and algorithms – and will highlight the relevant papers that address it. This seminar is targeted at both practicing engineers and researchers. The former will learn about the latest solutions to important meta data problems and the many difficult unsolved problems that are best to avoid. Database researchers, especially professors, will benefit from considering the conceptual framework that we propose, since no database textbooks treat meta data management as a separate topic as far as we know.

The difficulty inherent in schema matching has led to the development of several generic match algorithms. We describe how we adapted general approaches to the specific task of aligning two ontologies of human anatomy, the Foundational Model of Anatomy and the GALEN Common Reference Model. Our approach consists of three phases: lexical, structural and hierarchical, which leverage different aspects of the ontologies as they are represented in a generic meta-model. Lexical matching identifies concepts with similar names. Structural matching identifies concepts whose neighbors are similar. Finally, hierarchical matching identifies concepts with similar descendants. We conclude by reporting on the lessons we learned.

No abstract available.

Model management aims at reducing the amount of programming needed for the development of metadata-intensive applications. We present a first complete prototype of a generic model management system, in which high-level operators are used to manipulate models and mappings between models. We define the key conceptual structures: models, morphisms, and selectors, and describe their use and implementation. We specify the semantics of the known model-management operators applied to these structures, suggest new ones, and develop new algorithms for implementing the individual operators. We examine the solutions for two model-management tasks that involve manipulations of relational schemas, XML schemas, and SQL views.

This paper describes the version and workspace features of Microsoft Repository, a layer that implements fine-grained objects and relationships on top of Microsoft SQL Server. It supports branching and merging of versions, delta storage, checkout-checkin, and single-version views for version-unaware applications.

ANSI SQL-92 [MS, ANSI] defines Isolation Levels in terms of phenomena: Dirty Reads, Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and the ANSI SQL definitions fail to properly characterize several popular isolation levels, including the standard locking implementations of the levels covered. Ambiguity in the statement of the phenomena is investigated and a more formal statement is arrived at; in addition new phenomena that better characterize isolation types are introduced. Finally, an important multiversion isolation type, called Snapshot Isolation, is defined.

Transactions have been rigorously defined and extensively studied in the database and transaction processing literature, but little has been said about the handling of the requests for transaction execution in commercial TP systems, especially distributed ones, managing the flow of requests is often as important as executing the transactions themselves.

Today's standard model for database concurrency control, called serializability theory, represents executions of transactions as partial orders of operations. The theory tells when an execution is serializable, that is, when the set of operations of a transaction execute atomically with respect to those of other transactions. It has been used successfully to prove correctness of most database concurrency control algorithms. Its most serious limitation is its inability to represent nested computations conveniently. This paper presents a more general model that permits nested transactions. In this model, transactions may execute subtransactions, giving rise to tree-structured computations. A serializability theory is developed for this model, which can be used to prove the correctness of concurrency control algorithms for nested transactions and for multilevel database systems. The theory is based on an abstract model of computation that allows arbitrary operations, and parallel and even nondeterministic programs. Axioms are presented that express the basic properties that programs that manage or access data need to satisfy. We use these axioms to derive proof techniques. One new technique—substitution—shows the equivalence of two executions by substituting one subcomputation by another, usually shallower (i.e., less nested), one. Our proof techniques are illustrated by applying them to several well-known concurrency control problems.

This paper studies the problem of query optimization in a distributed database. Assuming a linear additive cost function (in volume of data moved), we present a fast algorithm for finding the optimal program that answers a class of common queries, called chain queries. The key to the problem formulation and to the derivation of an efficient algorithm is an elegant parameterization of the database state against which the query is to be answered. This parameterization then enables us to characterize the set of potentially optimal programs, which in turn leads to a fast dynamic programming algorithm. Since in practice the needed parameters may not be available to the database system, we also discuss how to deal with partial parameterizations of the database state.

In a one-copy distributed database, each data item is stored at exactly one site. In a replicated database, some data items may be stored at multiple sites. The main motivation is improved reliability: by storing important data at multiple sites, the DBS can operate even though some sites have failed. This paper describes an algorithm for handling replicated data, which allows users to operate on data so long as one copy is “available.” A copy is “available” when (i) its site is up, and (ii) the copy is not out-of-date because of an earlier crash. The algorithm handles clean, detectable site failures, but not Byzantine failures or network partitions.

Site initialization is the problem of integrating a new site into a running distributed database system (DDBS). Site recovery is the problem of integrating an old site into a DDBS when the site recovers from failure. Site backup is the problem of creating a static backup copy of a database for archival or query purposes. We present an algorithm that solves the site initialization problem. By modifying the algorithm slightly, we get solutions to the other two problems as well. Our algorithm exploits the fact that a correct DDBS must run a serializable concurrency control algorithm. Our algorithm relies on the concurrency control algorithm to handle all intersite synchronization.

Concurrency control is the activity of synchronizing transactions that access shared data. A concurrency control algorithm is regarded as correct if it ensures that any interleaved execution of transactions is equivalent to a serial one. Such executions are called serializable. Serializability theory provides a method for modelling and analyzing the correctness of concurrency control algorithms [BSW, Pa].The concept of nested transaction has recently received much attention [GR], [Mo]. In a nested transaction model, each transaction can invoke sub- transactions, which can invoke sub-subtransactions, and so on. The natural modelling concept is the tree log. The leaves of a tree log are atomic operations executed by the underlying system. Internal nodes are operations (as seen by their parents) implemented as transactions (as seen by their children). Nodes are related by a partial order

A replicated database is a distributed database in which some data items are stored redundantly at multiple sites. The main goal is to improve system reliability. By storing critical data at multiple sites, the system can operate even though some sites have failed. However, few distributed database systems support replicated data, because it is difficult to manage as sites fail and recover.

No abstract available.

Concurrency control is the activity of synchronizing operations issued by concurrently executing programs on a shared database. The goal is to produce an execution that has the same effect as a serial (noninterleaved) one. In a multiversion database system, each write on a data item produces a new copy (or version ) of that data item. This paper presents a theory for analyzing the correctness of concurrency control algorithms for multiversion database systems. We use the theory to analyze some new algorithms and some previously published ones.

Concurrency control algorithms for database systems are usually regarded as methods for synchronizing Read and Write operations. Such methods are judged to be correct if they only produce serializable executions. However, Reads and Writes are sometimes inaccurate models of the operations executed by a database system. In such cases, serializability does not capture all aspects of concurrency control executions. To capture these aspects, we describe a proof schema for analyzing concurrency control correctness. We illustrate the proof schema by presenting two new concurrency algorithms for distributed database systems.

Concurrency control is the activity of synchronizing operations issued by concurrently executing programs on a shared database. The goal is to produce an execution that has the same effect as a serial (noninterleaved) one.

Semantic integrity assertions are predicates that define consistent states. A database system enforces assertions by ensuring that consistency is maintained as the database is updated.Most research on the efficient enforcement of assertions has concentrated on assertion simplification algorithms --- algorithms that produce simplified assertions that can be evaluated before the update is executed. This paper describes a strategy for further improving the efficiency of assertion enforcement.We develop an efficient algorithm for evaluating an assertion produced by an assertion simplification algorithm. We characterize a class of assertions that can be evaluated using a simple two-step procedure. The first step defines and evaluates simple selection queries on each relation. The second step applies set emptiness tests to the results of these selections. We also show how these techniques may be used to improve the efficiency of evaluating assertions outside our class.

Most relational database systems provide a facility for supporting user views. Permitting this level of abstraction has the danger, however, that update requests issued by a user within the context of his view may not translate correctly into equivalent updates on the underlying database. The purpose of this paper is to formalize the notion of update translation and derive conditions under which translation procedures will produce correct translations of view updates.

The semi-join is a relational algebraic operation that selects a set of tuples in one relation that match one or more tuples of another relation on the joining domains.Semi-joins have been used as a basic ingredient in query processing strategies for a number of hardware and software database systems.However, not all queries can be solved entirely using semi-joins.In this paper the exact class of relational queries that can be solved using semi-joins is shown.It is also shown that queries outside of this class may not even be partially solvable using "short" semi-join programs.In addition, a linear-time membership test for this class is presented.

A semijoin is a relational operator that is used to reduce the cost of processing queries in the SDD-1 distributed database system, the RAP database machine, and similar systems. Semijoin is used in these systems as part of a query pre-processing phase; its function is to “reduce” the database by delimiting those portions of the database that contain data relevant to the query. For some queries, there exist sequences of semijoins that “fully reduce” the database; those sequences delimit the exact portions of the database needed to answer the query in the sense that if any less data were delimited then the query would produce a different answer. Such sequences are called full reducers. This paper characterizes the queries for which full reducers exist and presents an efficient algorithm for constructing full reducers where they do exist. This paper extends the results of Bernstein and Chiu [J. Assoc. Comput. Mach., 28 (1981), pp. 25–40] by considering a more powerful semijoin operator. We consider “natural” semijoins instead of the “single attribute” semijoins of Bernstein and Chiu. A novel feature of our treatment is an extensive use of the “tableau methodology” of Aho, Sagiv and Ullman [SIAM J. Comput., 8 (1979), pp. 218–246] to prove the nonexistence of full reducers for a broad class of queries.

This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each Datalanguage query into a relational calculus form called an envelope , which is essentially an aggregate-free QUEL query. This paper is primarily concerned with the optimization of envelopes. Envelopes are processed in two phases. The first phase executes relational operations at various sites of the distributed database in order to delimit a subset of the database that contains all data relevant to the envelope. This subset is called a reduction of the database. The second phase transmits the reduction to one designated site, and the query is executed locally at that site. The critical optimization problem is to perform the reduction phase efficiently. Success depends on designing a good repertoire of operators to use during this phase, and an effective algorithm for deciding which of these operators to use in processing a given envelope against a given database. The principal reduction operator that we employ is called a semijoin . In this paper we define the semijoin operator, explain why semijoin is an effective reduction operator, and present an algorithm that constructs a cost-effective program of semijoins, given an envelope and a database.

This paper presents a formal analysis of the concurrency control strategy of SDD-1. SDD-1, a System for Distributed Databases, is a prototype distributed database system being developed by Computer Corporation of America. In SDD-1, portions of data distributed throughout a network may be replicated at multiple sites. The SDD-1 concurrency control guarantees database consistency in the face of such distribution and replication. This paper is one of a series of companion papers on SDD-1 [2, 8].

This paper presents the concurrency control strategy of SDD-1. SDD-1, a System for Distributed Databases, is a prototype distributed database system being developed by Computer Corporation of America. In SDD-1, portions of data distributed throughout a network may be replicated at multiple sites. The SDD-1 concurrency control guarantees database consistency in the face of such distribution and replication. This paper is one of a series of companion papers on SDD-1 [4, 10, 12, 21].

TAXIS, a language for the design of interactive information systems (e.g., credit card verification, student-course registration, and airline reservations) is described. TAXIS offers (relational) database management facilities, a means of specifying semantic integrity constraints, and an exception-handling mechanism, integrated into a single language through the concepts of class, property , and the IS-A (generalization) relationship . A description of the main constructs of TAXIS is included and their usefulness illustrated with examples.

The declining cost of computer hardware and the increasing data processing needs of geographically dispersed organizations have led to substantial interest in distributed data management. SDD-1 is a distributed database management system currently being developed by Computer Corporation of America. Users interact with SDD-1 precisely as if it were a nondistributed database system because SDD-1 handles all issues arising from the distribution of data. These issues include distributed concurrency control, distributed query processing, resiliency to component failure, and distributed directory management. This paper presents an overview of the SDD-1 design and its solutions to the above problems. This paper is the first of a series of companion papers on SDD-1 (Bernstein and Shipman [2], Bernstein et al. [4], and Hammer and Shipman [14]).

A formal system for proving properties of programs accessing a database is introduced. Proving that a program preserves consistency of the database is one of the possible applications of the system. The formal system is a variant of dynamic logic and incorporates a data definition language (DDL) for describing relational databases and a data manipulation language (DML) whose programs access data in a database. The DDL is a many-sorted first-order language that accounts for data aggregations. The DML features a many-sorted assignment in place of the usual data manipulation statements, in addition to the normal programming language constructs.

The cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. It is shown that the obvious strategy—trying to balance the sums of probabilities of the keys mapped to any given address—may be suboptimal; however, the difference from the exactly optimal distribution cannot be large.

A logic for a relational data manipulation language is defined by augmenting a known logic of programs with rules for two new statements: the relational assignment, which assign a relational expression to a relation, and the random tuple selection, which extracts an arbitrary tuple from a relation. The usual operations on relations-retrieve, insert, delete, update-are then defined as special cases of the relational assignment, and the for-each construct scanning a relation tuple by tuple is introduced with the help of the random tuple selection.

We study the following database design problem. Given a universal relation scheme 〈U, F〉 where F is a set of functional dependencies, find an in some way normalized database schema D = {〈X1, F1〉,..., 〈Xn, Fn〉} where Xi ⊂ U and Fi is inherited from F, such that D is an independent representation of the universal scheme 〈U, F〉. This means that D has both the lossless join property and the faithful closure property, (***** Fi)+ = F+, where + denotes the closure of a set of functional dependencies. We show that this goal can easily be achieved by an extension of the well-known synthetic approach of Bernstein and others to database design. We merely have to check whether the usual synthesis procedure has produced a key component 〈Xi, Fi〉 such that Xi → U ε F+; in case this is true the output of the synthesis procedure is actually an independent (and not only faithful) representation, otherwise we only have to add one further component, namely just a key. These claims are proved by a careful inspection of the Aho/Beeri/Ullman algorithm to test for losslessness. Finally, we show how to use our method to synthesize minimal independent third normal form schemas.

Problems related to functional dependencies and the algorithmic design of relational schemas are examined. Specifically, the following results are presented: (1) a tree model of derivations of functional dependencies from other functional dependencies; (2) a linear-time algorithm to test if a functional dependency is in the closure of a set of functional dependencies; (3) a quadratic-time implementation of Bernstein's third normal form schema synthesis algorithm. Furthermore, it is shown that most interesting algorithmic questions about Boyce-Codd normal form and keys are NP -complete and are therefore probably not amenable to fast algorithmic solutions.

No abstract available.

An arbitrary interleaved execution of transactions in a database system can lead to an inconsistent database state. A number of synchronization mechanisms have been proposed to prevent such spurious behavior. To gain insight into these mechanisms, we analyze them in a simple centralized system that permits one read operation and one write operation per transaction. We show why locking mechanisms lead to correct operation, we show that two proposed mechanisms for distributed environments are special cases of locking, and we present a new version of lockdng that alows more concurrency than past methods. We also examine conflict graph analysis, the method used in the SDD-1 distributed database system, we prove its correctness, and we show that it can be used to substantially improve the performance of almost any synchronization mechanisn.

This paper describes TAXIS, a language for the design of Interactive Information Systems (e.g., credit card varification, student-course registration and airline reservations). TAXIS offers (relational) database management facilities, a means of specifying semantic integrity constraints and an exception-handling mechanism, integrated into a single language through the concepts of class, property and the ISA (generalization) relationship. The paper includes a description of the main constructs of TAXIS and illustrates their usefulness with examples.

SDD-1, A System for Distributed Databases, is a distributed database system being developed by Computer Corporation of America (CCA), Cambridge, MA. SDD-1 permits data to be stored redundantly at several database sites in order to enhance the reliability and responsiveness of the system and to facilitate upward scaling of system capacity. This paper describes the method used by SDD-1 for updating data that are stored redundantly.

It has been proposed that the description of a relational database can be formulated as a set of functional relationships among database attributes. These functional relationships can then be used to synthesize algorithmically a relational scheme. It is the purpose of this paper to present an effective procedure for performing such a synthesis. The schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations. Problems with earlier attempts to construct such a procedure are also discussed.

In Codd's relational model, the relation name groups together a family of functional dependencies over a set of attributes. For integrity and for maintenance purposes it is important to eliminate inherent redundancy within a relation due to the repetition of instances of a functional connection between attributes. This led Codd to propose a series of three normalizations. The manipulation of normal forms is governed by functional dependencies that are explicitly declared to exist within the relation. Since functional dependencies completely govern the decomposition rules of normalization, perhaps it is more sensible to take them as the elementary notions to be later synthesized into more complex structures, such as relations. Our goals, then are twofold. First, we will discuss how the use of functional dependencies lends itself to a rigorous and correct, yet clear and simple description of complex data relationships. Second, we will outline some new computational techniques to map functional dependencies into normal form relations algorithmically, thus allowing us to use the dependencies as a basic unit on the implementation as well as conceptual level.

Most of the literature on implementation of relations has been directed toward user features, with little attention paid to an overall conceptual view of underlying structures. Performance oriented considerations have been treated only for isolated problems.