As data becomes increasingly distributed, traditional RPC and data serialization limits performance, result in rigidity, and hamper expressivity. We believe that technology trends including high-density persistent memory, high-speed networks, and programmable switches make this the right time to revisit prior research on distributed shared memory, global addressing, and content-based networking. Our vision combines the code mobility of RPC with first-class data references in a global address space by co-designing the OS and the network around pervasive data identity. We have initial results showing the promise of the proposed co-design.

In 2009 we explored the feasibility of building a hybrid SQL data analysis system that takes the best features from two competing technologies: large-scale data processing systems (such as Google MapReduce and Apache Hadoop) and parallel database management systems (such as Greenplum and Vertica). We built a prototype, HadoopDB, and demonstrated that it can deliver the high SQL query performance and efficiency of parallel database management systems while still providing the scalability, fault tolerance, and flexibility of large-scale data processing systems. Subsequently, HadoopDB grew into a commercial product, Hadapt, whose technology was eventually acquired by Teradata. In this paper, we provide an overview of HadoopDB's original design, and its evolution during the subsequent ten years of research and development effort. We describe how the project innovated both in the research lab, and as a commercial product at Hadapt and Teradata. We then discuss the current vibrant ecosystem of software projects (most of which are open source) that continued HadoopDB's legacy of implementing a systems level integration of large-scale data processing systems and parallel database technology.

We propose an efficient remote biometric authentication protocol that gives strong protection to the user’s biometric data in case of two common kinds of security breaches: (1) loss or theft of the user’s token (smart card, handheld device, etc.), giving the attacker full access to any secrets embedded within it; (2) total penetration of the server. Only if both client and server are simultaneously compromised is the user’s biometric data vulnerable to exposure. The protocol works by encrypting the user’s biometric template in a way that allows it to be used for authentication without being decrypted by either token or server. Further, the encrypted template never leaves the token, and only the server has the information that would enable it to be decrypted. We have implemented our protocol using two iris recognition libraries and evaluated its performance. The overall efficiency and recognition performance is essentially the same compared to an unprotected biometric system.

Commercial analytical database systems suffer from a high "time-to-first-analysis": before data can be processed, it must be modeled and schematized (a human effort), transferred into the database's storage layer, and optionally clustered and indexed (a computational effort). For many types of structured data, this upfront effort is unjustifiable, so the data are processed directly over the file system using the Hadoop framework, despite the cumulative performance benefits of processing this data in an analytical database system. In this paper we describe a system that achieves the immediate gratification of running MapReduce jobs directly over a file system, while still making progress towards the long-term performance benefits of database systems. The basic idea is to piggyback on MapReduce jobs, leverage their parsing and tuple extraction operations to incrementally load and organize tuples into a database system, while simultaneously processing the file system data. We call this scheme Invisible Loading, as we load fractions of data at a time at almost no marginal cost in query latency, but still allow future queries to run much faster.

To help a user specify and verify quantified queries --- a class of database queries known to be very challenging for all but the most expert users --- one can question the user on whether certain data objects are answers or non-answers to her intended query. In this paper, we analyze the number of questions needed to learn or verify qhorn queries, a special class of Boolean quantified queries whose underlying form is conjunctions of quantified Horn expressions. We provide optimal polynomial-question and polynomial-time learning and verification algorithms for two subclasses of the class qhorn with upper constant limits on a query's causal density.

Writing complex queries in SQL is a challenge for users. Prior work has developed several techniques to ease query specification but none of these techniques are applicable to a particularly difficult class of queries: quantified queries. Our hypothesis is that users prefer to specify quantified queries interactively by trial-and-error. We identify two impediments to this form of interactive trial-and-error query specification in SQL: (i) changing quantifiers often requires global syntactical query restructuring, and (ii) the absence of non-answers from SQL's results makes verifying query correctness difficult. We remedy these issues with DataPlay, a query tool with an underlying graphical query language, a unique data model and a graphical interface. DataPlay provides two interaction features that support trial-and-error query specification. First, DataPlay allows users to directly manipulate a graphical query by changing quantifiers and modifying dependencies between constraints. Users receive real-time feedback in the form of updated answers and non-answers. Second, DataPlay can auto-correct a user's query, based on user feedback about which tuples to keep or drop from the answers and non-answers. We evaluated the effectiveness of each interaction feature with a user study and we found that direct query manipulation is more effective than auto-correction for simple queries but auto-correction is more effective than direct query manipulation for more complex queries.

DataPlay is a query tool that encourages a trial-and-error approach to query specification. DataPlay uses a graphical query language to make a particularly challenging query specification task - quantification - easier. It constrains the relational data model to enable the presentation of non-answers, in addition to answers, to aid query interpretation. Two novel features of DataPlay are suggesting semantic variations to a query and correcting queries by example. We introduce DataPlay as a sophisticated query specification tool and demonstrate its unique interaction models.

Hadapt is a start-up company currently commercializing the Yale University research project called HadoopDB. The company focuses on building a platform for Big Data analytics in the cloud by introducing a storage layer optimized for structured data and by providing a framework for executing SQL queries efficiently. This work considers processing data warehousing queries over very large datasets. Our goal is to maximize perfor mance while, at the same time, not giving up fault tolerance and scalability. We analyze the complexity of this problem in the split execution environment of HadoopDB. Here, incoming queries are examined; parts of the query are pushed down and executed inside the higher performing database layer; and the rest of the query is processed in a more generic MapReduce framework.

HadoopDB is a hybrid of MapReduce and DBMS technologies, designed to meet the growing demand of analyzing massive datasets on very large clusters of machines. Our previous work has shown that HadoopDB approaches parallel databases in performance and still yields the scalability and fault tolerance of MapReduce-based systems. In this demonstration, we focus on HadoopDB's flexible architecture and versatility with two real world application scenarios: a semantic web data application for protein sequence analysis and a business data warehousing application based on TPC-H. The demonstration offers a thorough walk-through of how to easily build applications on top of HadoopDB.

The production environment for analytical data management applications is rapidly changing. Many enterprises are shifting away from deploying their analytical databases on high-end proprietary machines, and moving towards cheaper, lower-end, commodity hardware, typically arranged in a shared-nothing MPP architecture, often in a virtualized environment inside public or private "clouds". At the same time, the amount of data that needs to be analyzed is exploding, requiring hundreds to thousands of machines to work in parallel to perform the analysis. There tend to be two schools of thought regarding what technology to use for data analysis in such an environment. Proponents of parallel databases argue that the strong emphasis on performance and efficiency of parallel databases makes them well-suited to perform such analysis. On the other hand, others argue that MapReduce-based systems are better suited due to their superior scalability, fault tolerance, and flexibility to handle unstructured data. In this paper, we explore the feasibility of building a hybrid system that takes the best features from both technologies; the prototype we built approaches parallel databases in performance and efficiency, yet still yields the scalability, fault tolerance, and flexibility of MapReduce-based systems.

Data sparsity and schema evolution issues affecting clinical informatics and bioinformatics communities have led to the adoption of vertical or object-attribute-value-based database schemas to overcome limitations posed when using conventional relational database technology. This paper explores these issues and discusses why biomedical data are difficult to model using conventional relational techniques. The authors propose a solution to these obstacles based on a relational database engine using a sparse, column-store architecture. The authors provide benchmarks comparing the performance of queries and schema-modification operations using three different strategies: (1) the standard conventional relational design; (2) past approaches used by biomedical informatics researchers; and (3) their sparse, column-store architecture. The performance results show that their architecture is a promising technique for storing and processing many types of data that are not handled well by the other two semantic data models.

We present a general model of interdomain route selection to study interdomain traffic engineering. In this model, the routing of multiple destinations can be coordinated. Thus the model can capture general traffic engineering behaviors such as load balancing and link capacity constraints. We first identify potential routing instability and inefficiency of interdomain traffic engineering. We then derive a sufficient condition to guarantee convergence. We also show that the constraints on local policies imposed by business considerations in the Internet can guarantee stability without global coordination. Using realistic Internet topology, we evaluate the extent to which routing instability of interdomain traffic engineering can happen when the constraints are violated.

The recent discovery of instability caused by the interaction of local routing policies of multiple ASes has led to extensive research on the subject. However, previous studies analyze stability under a specific route selection algorithm. In this paper, instead of studying a specific route selection algorithm, we study a general class of route selection algorithms which we call rational route selection algorithms. We present a sufficient condition to guarantee routing convergence in a heterogeneous network where each AS runs any rational route selection algorithm. Applying our general results, we study the potential instability of a network where the preference of an AS depends on not only its egress routes to the destinations but also its inbound traffic patterns (i.e., the distribution of incoming traffic from its neighbors). We show that there exist networks which will have persistent route oscillations even when the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.

Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.

Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either 1) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored, or 2) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of the NetInventory topology-discovery tool that has been tested on Lucent's own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology with reasonably small running-time requirements even for fairly large network configurations.

Increasingly, for extensibility and performance, special purpose application code is being integrated with database system code. Such application code has direct access to database system buffers, and as a result, the danger of data being corrupted due to inadvertent application writes is increased. Previously proposed hardware techniques to protect from corruption require system calls, and their performance depends on details of the hardware architecture. We investigate an alternative approach which uses codewords associated with regions of data to detect corruption and to prevent corrupted data from being used by subsequent transactions. We develop several such techniques which vary in the level of protection, space overhead, performance, and impact on concurrency. These techniques are implemented in the Dali main-memory storage manager, and the performance impact of each on normal processing is evaluated. Novel techniques are developed to recover when a transaction has read corrupted data caused by a bad write and gone on to write other data in the database. These techniques use limited and relatively low-cost logging of transaction reads to trace the corruption and may also prove useful when resolving problems caused by incorrect data entry and other logical errors.

Virtual private networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. We develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP-hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is O(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints.

The proliferation of e-commerce has enabled a new set of applications that allow globally distributed purchasing of commodities such as books, CDs, travel tickets, etc., over the Internet. These commodities can be represented online by tokens, which can be distributed among servers to enhance the performance and availability of such applications. There are two fundamental approaches for distributing such tokens-partitioning and replication. Partitioning-based approaches eliminate the need for tight quorum synchronization required by replication-based approaches. The effectiveness of partitioning, however, relies on token redistribution techniques that allow dynamic migration of tokens to where they are needed. We propose pair-wise token redistribution strategies to support applications that involve wide-area commodity distribution. Using a detailed simulation model and real Internet message traces, we investigate the performance of our redistribution strategies and a previously proposed replication based scheme. Our results reveal that, for the types of applications and environment we address, partitioning-based approaches perform superior primarily due to their ability to provide higher server autonomy.

Effective monitoring of network utilization and performance indicators is a key enabling technology for proactive and reactive resource management, flexible accounting, and intelligent planning in next-generation IP networks. In this paper, we address the challenging problem of efficiently monitoring bandwidth utilization and path latencies in an IP data network. Unlike earlier approaches, our measurement architecture assumes a single point-of-control in the network (corresponding to the network operations center) that is responsible for gathering bandwidth and latency information using widely-deployed management tools, like SNMP, RMON/NetFlow, and explicitly-routed IP probe packets. Our goal is to identify effective techniques for monitoring (a) bandwidth usage for a given set of links or packet flows, and (b) path latencies for a given set of paths, while minimizing the overhead imposed by the management tools on the underlying production network. We demonstrate that minimizing overheads under our measurement model gives rise to new combinatorial optimization problems, most of which prove to be NP-hard. We also propose novel approximation algorithms for these optimization problems and prove guaranteed upper bounds on their worst-case performance. Our simulation results validate our approach, demonstrating the effectiveness of our novel monitoring algorithms over a wide range of network topologies.

Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. In this paper, we develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is O (mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints.

Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either: (a) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored; or (b) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of a topology discovery tool that has been tested on Lucent's own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology in time that is roughly quadratic in the number of network elements.

Increasingly, for extensibility and performance, special-purpose application code is being integrated with database system code. Such application code has direct access to database system buffers and, as a result, the danger of data being corrupted due to inadvertent application writes is increased. Previously proposed hardware techniques to protect data from corruption required system calls, and their performance depended on the details of the hardware architecture. We investigate an alternative approach which uses codewords associated with regions of data to detect corruption and to prevent corrupted data from being used by subsequent transactions. We develop several such techniques which vary in the level of protection, space overhead, performance and impact on concurrency. These techniques are implemented in the Dali/spl acute/ main-memory storage manager, and the performance impact of each on normal processing is evaluated. Novel techniques are developed to recover when a transaction has read corrupted data caused by a bad write, and then gone on to write other data in the database. These techniques use limited and relatively low-cost logging of transaction reads to trace the corruption, and may also prove useful when resolving problems caused by incorrect data entry and other logical errors.

An increasing number of database applications require online access to massive amounts of data. Since large scale storage systems implemented entirely on magnetic disk can be impractical or too costly for many applications, tape jukeboxes can provide an attractive solution. The paper shows how the performance of tape jukeboxes can be improved across a broad parameter space via a new scheduling algorithm and schemes for the placement and replication of hot data. We substantiate our claim by an extensive simulation study that quantifies the improvements obtained over a wide variety of workload characteristics. Our experiments suggest that system throughput increases when replicas of hot data are placed at the tape ends (not in the middle or at the beginning). As a result, the proposed replication techniques can be used to fill existing spare capacity in a tape jukebox, thus improving the performance of the jukebox "for free".

No abstract available.

Replication is often used in many distributed systems to provide a higher level of performance, reliability and availability. Lazy replica update protocols, which propagate updates to replicas through independent transactions after the original transaction commits, have become popular with database vendors due to their superior performance characteristics. However, if lazy protocols are used indiscriminately, they can result in non-serializable executions. In this paper, we propose two new lazy update protocols that guarantee serializability but impose a much weaker requirement on data placement than earlier protocols. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to eliminate all requirements on data placement. The extension is a hybrid protocol that propagates as many updates as possible in a lazy fashion. We implemented our protocols on the Datablitz database system product developed at Bell Labs. We also conducted an extensive performance study which shows that our protocols outperform existing protocols over a wide range of workloads.

We study the problem of discovering association rules that display regular cyclic variation over time. For example, if we compute association rules over monthly sales data, we may observe seasonal variation where certain rules are true at approximately the same month each year. Similarly, association rules can also display regular hourly, daily, weekly, etc., variation that is cyclical in nature. We demonstrate that existing methods cannot be naively extended to solve this problem of cyclic association rules. We then present two new algorithms for discovering such rules. The first one, which we call the sequential algorithm, treats association rules and cycles more or less independently. By studying the interaction between association rules and time, we devise a new technique called cycle pruning, which reduces the amount of time needed to find cyclic association rules. The second algorithm, which we call the interleaved algorithm, uses cycle pruning and other optimization techniques for discovering cyclic association rules. We demonstrate the effectiveness of the interleaved algorithm through a series of experiments. These experiments show that the interleaved algorithm can yield significant performance benefits when compared to the sequential algorithm. Performance improvements range from 5% to several hundred percent.

Multimedia applications require a guaranteed level of service for accessing Continuous Media (CM) data, such asvideo and audio. To obtain such guarantees, the database server where the data is residing must employ an admission control scheme to limit the number of clients that can be served concurrently. We investigate the problem of on-line admission control where the decision on whether to accept or reject a request must be made without any knowledge about future requests. Employing competitive analysis techniques, we address the problem in its most general form with the following key contributions: (1) we prove a tight upper bound on the competitive ratio of the conventional Work-Conserving (WC) policy, showing that it is within a factor 1+ of the 1; optimal clairvoyant strategy that knows the entire request

The concept of serializability has been the traditionally accepted correctness criterion in database systems. However in multidatabase systems (MDBSs), ensuring global serializability is a difficult task. The difficulty arises due to the heterogeneity of the concurrency control protocols used by the participating local database management systems (DBMSs), and the desire to preserve the autonomy of the local DBMSs. In general, solutions to the global serializability problem result in executions with a low degree of concurrency. The alternative, relaxed serializability, may result in data inconsistency. In this article, we introduce a systematic approach to relaxing the serializability requirement in MDBS environments. Our approach exploits the structure of the integrity constraints and the nature of transaction programs to ensure consistency without requiring executions to be serializable. We develop a simple yet powerful classification of MDBSs based on the nature of integrity constraints and transaction programs. For each of the identified models we show how consistency can be preserved by ensuring that executions are two-level serializable (2LSR). 2LSR is a correctness criterion for MDBS environments weaker than serializability. What makes our approach interesting is that unlike global serializability, ensuring 2LSR in MDBS environments is relatively simple and protocols to ensure 2LSR permit a high degree of concurrency. Furthermore, we believe the range of models we consider cover many practical MDBS environments to which the results of this article can be applied to preserve database consistency.

In last year’s ICDE panel in New Orleans [l], we examined the question of whether database research is able to provide leadership to database industries. There was a consensus that with the maturing of the field, we should now focus on new areas where we can leverage off our rich experience in database research. The question of what problem to work on next has always been a difficult one to answer and we suspect that it will not get easier. Even then, it will be rewarding to examine the question of how the successful and not so successful threads of research came into being and what caught our fancy and why. Specifically, we will seek the perspective of the panelists on the following questions:

A growing number of applications need access to video data stored in digital form on secondary storage devices (e.g., video-on-demand, multimedia messaging). As a result, video servers that are responsible for the storage and retrieval, at fixed rates, of hundreds of videos from disks are becoming increasingly important. Since video data tends to be voluminous, several disks are usually used in order to store the videos. A challenge is to devise schemes for the storage and retrieval of videos that distribute the workload evenly across disks, reduce the cost of the server and at the same time, provide good response times to client requests for video data. In this paper we present schemes that retrieve videos periodically from disks in order to provide better response times to client requests. We present two schemes that stripe videos across multiple disks in order to distribute the workload uniformly among them. For the two striping schemes, we show that the problem of retrieving videos periodically is equivalent to that of scheduling periodic tasks on a multiprocessor. For the multiprocessor scheduling problems, we present and compare schemes for computing start times for the tasks, if it is determined that they are schedulable.

The following are two possible approaches to providing database functionality for multimedia data: a) the multimedia data as well as the metadata for it is stored together in a single database system, and b) the multimedia data is stored in a separate file system while the corresponding metadata for it is stored in a database system. Both approaches have their advantages and disadvantages. The first approach implies that databases need to be redesigned to support multimedia data along with conventional data. Since this requires modifications to existing databases, businesses may not be convinced to replace their databases with a new one to accommodate multimedia. Furthermore, this integrated approach might be a burden for users who do not need full-fledged multimedia support. The second approach allows businesses to capitalize on their existing base and purchase a multimedia storage system and the necessary glue to integrate their databases with the multimedia storage system. This approach, however, may complicate the implementation of some of the database functionality such as data consistency. The authors provide an overview of a) the issues for supporting content-based queries and a brief survey of research done in this arena, and b) the issues related to the storage and retrieval of continuous media data.

In order to support multiple real-time applications on a single platform, ,the operating system must provide Quality of Service (&OS) guarantees so that the system resources can be provisioned among applications to achieve desired levels of predictable performance.The traditional QoS parameters include fairness, delay, and throughput.In this paper we introduce a new QoS criterion called cumulative service.The cumulative service criterion relates the total service obtained by a process under a scheduling policy to the ideal service that the process would have accumulated by executing on each resource at a reserued rate.We say that a scheuling policy provides a cumulative service guarantee if the performance of the real system differs from the ideal system by at most a constant amount.A cumulative service guarantee is vital for applications (e.g., a continous media file service) that require multiple resources and demand predictable aggregated throughput over aII these resources.E.xisting scheduling algorithms that guarantee traditional QoS paramaters do not provide cumulative service guarantees.We present a new scheduling algorithm called Move-To-Rear List Scheduling which provides a cumulative service guarantee as well as the traditional guarantees such as fairness (proportional sharing) and bounded delay.The complexity of MTR-LS is o(ln(n))where n is the number of processes.

Next generation database systems will need to provide support for both textual data and other types of multimedia data (e.g., images, video, audio).These two types of data differ in their characteristics, and hence require different techniques for their organization and management.For example, continuous media data (e.g., video, audio) requires a guaranteed transfer rate.In thii paper, we provide an overview of 1) how database systems can be architectured to support multimedia data, and 2) what are the main challenges in devising new algorithms to manage multimedia data.In order to provide rate guarantees for continuous media data, an admission controZscheme must be employed that determines, for each client, whether there are sufficient resources available to service that client.To maximize the number of clients that can be admitted concurrently, the various system resources must be allocated and scheduled carefully.In terms of disks, we use algorithms for retrieving/storing data from/to disks that reduce seek latency time and eliminate rotational delay, thereby providing high throughput.In terms of main-memory, we use buffer management schemes that exploit the sequential access patterns for continuous media data, thereby resulting in efficient replacement of buffer pages from the cache.In addition to discussing resource scheduling, we also present schemes for the storage layout of data on disks and schemes that provide fault-tolerance by ensuring uninterrupted service in the presence of disk failures.

New applications require online access to many terabytes of data, but a magnetic disk storage system this large requires thousands of drives. Magnetic tape is be a good alternative, except that the application demand for transparent data retrieval is not met by current tape systems because of their high access latency. This latency can be significantly improved by good retrieval scheduling. A fundamental prerequisite to efficient scheduling is the ability to estimate the amount of time required for tape positioning operations (the locate time). For serpentine tape, which is the most common mass storage tape technology, this estimation is subtle and complex. The main contribution of this paper is a locate-time model for a DLT4000 tape drive. The accuracy of the model is evaluated by measurements, and the utility of the model is demonstrated through a model-driven simulation of retrieval scheduling, validated by measurements and sensitivity testing. In brief, the locate-time model is accurate to within a few percent, which enables the production of efficient schedules.

This paper introduces bifocal sampling, a new technique for estimating the size of an equi-join of two relations. Bifocal sampling classifies tuples in each relation into two groups, sparse and dense, based on the number of tuples with the same join value. Distinct estimation procedures are employed that focus on various combinations for joining tuples (e.g., for estimating the number of joining tuples that are dense in both relations). This combination of estimation procedures overcomes some well-known problems in previous schemes, enabling good estimates with no a priori knowledge about the data distribution. The estimate obtained by the bifocal sampling algorithm is proven to lie with high probability within a small constant factor of the actual join size, regardless of the skew, as long as the join size is Ω(n lg n), for relations consisting of n tuples. The algorithm requires a sample of size at most O(√n lg n). By contrast, previous algorithms using a sample of similar size may require the join size to be Ω(n√n) to guarantee an accurate estimate. Experimental results support the theoretical claims and show that bifocal sampling is practical and effective.

New database applications that require the storage and retrieval of many terabytes of data are reaching the limits for disk-based storage systems, in terms of both cost and scalability. These limits provide a strong incentive for the development of databases that augment disk storage with technologies better suited to large volumes of data. In particular, the seamless incorporation of tape storage into database systems would be of great value. Tape storage is two orders of magnitude more efficient than disk in terms of cost per terabyte and physical volume per terabyte; however, a key problem is that the random access latency of tape is three to four orders of magnitude slower than disk. Thus, to incorporate a tape bulk store in an online storage system, the problem of tape access latency must be solved. One approach to reducing the latency is careful I/O scheduling. The focus of this paper is on efficient random I/O scheduling for tape drives that use a serpentine track layout, such as the Quantum DLT and the IBM 3480 and 3590. For serpentine tape, I/O scheduling is problematic because of the complex relationships between logical block numbers, their physical positions on tape, and the time required for tape positioning between these physical positions. The results in this paper show that our scheduling schemes provide a significant improvement in the latency of random access to serpentine tape.

Continuous media servers that provide support for the storage and retrieval of continuous media data (e.g., video, audio) at guaranteed rates are becoming increasingly important. Such servers, typically, rely on several disks to service a large number of clients, and are thus highly susceptible to disk failures. We have developed two fault-tolerant approaches that rely on admission control in order to meet rate guarantees for continuous media requests. The schemes enable data to be retrieved from disks at the required rate even if a certain disk were to fail. For both approaches, we present data placement strategies and admission control algorithms. We also present design techniques for maximizing the number of clients that can be supported by a continuous media server. Finally, through extensive simulations, we demonstrate the effectiveness of our schemes. 1 Introduction Rapid advances in computing and communication technologies have fueled an explosive growth in the multimedia indus...

One of the central problems in the field of knowledge discovery is the development of good measures of interestingness of discovered patterns. Such measures of interestingness are divided into objective measures-those that depend only on the structure of a pattern and the underlying data used in the discovery process, and the subjective measures-those that also depend on the class of users who examine the pattern. The focus of the paper is on studying subjective measures of interestingness. These measures are classified into actionable and unexpected, and the relationship between them is examined. The unexpected measure of interestingness is defined in terms of the belief system that the user has. Interestingness of a pattern is expressed in terms of how it affects the belief system. The paper also discusses how this unexpected measure of interestingness can be used in the discovery process.

Serializability is the traditionally accepted notion of correctness in most database systems. However, in a multidatabase system (MDBS) environment, where a number of pre-existing and autonomous database systems are integrated, requiring serializability could adversely affect the performance of the system. To enhance performance, one of the options is to relax the serializability requirement, and permit certain non-serializable executions. In this paper, we propose a powerful, yet simple mechanism, for specifying the set of non-serializable executions that are unacceptable in an MDBS environment. The undesirable interleavings among transactions are specified using regular expressions over transaction types. The mechanism facilitates the development of efficient graph-based schemes for ensuring that the concurrent execution of transactions meet the specifications. We analyze the complexities of the developed schemes and show that they are easily implementable in an MDBS environment.

To meet the stringent performance requirements of transaction recording systems, much of the recording and query processing functionality, which should preferably be in the database, is actually implemented in the procedural application code, with the attendant difficulties in development, modularization, maintenance, and evolution.To combat this deficiency, we propose a new data model, the chronicle model, which permits the capture, within the data model, Queries over the stored sequence of transaction records, with stringent response time requirements.Of particular interest are summary queries, that access summarization, or aggregation information of past transactional activity.For example, a cellular phone company may want to provide a facility for a summary query that computes the total number of minutes of calls made in the current billing month from a phone number.This query could be executed whenever a cellular phone is turned on, and the result could be displayed on the customer's phone instrument.Another example of a summary query that a customer care agent in the cellular company may want to execute is: What is the total number of minutes of calls made from a given cellular number since the number was assigned to the current customer.These applications can be (and are) implemented using commercially available relational databases.However, the relational model is not suitable to capture and exploit the peculiar characteristics of a transaction recording system.For example, there is no support for answering a summary query over a sequence that is not

The problem of mapping the parallel bottom up execution of Datalog programs to an interconnected network of processors is studied. The parallelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an environment where the number of processors and the interconnection topology is known, and communication between program segments residing at non-adjacent processors is not permitted. An algorithm is presented that decides whether a given Datalog program can be mapped onto such an architecture. We then relax the constraint on the architecture by allowing program segments residing at non-adjacent processors to communicate, A theory of approximate mappings is developed, and an algorithm to obtain the closest approximate mapping of a given Datalog program onto a given architecture is presented.>

Real-time database systems associate the concept of deadlines with transaction executions. Previous approaches use "best effort" techniques to schedule a given set of transactions to meet the deadlines as well as to ensure the consistency of the database. However, such approaches are inadequate for target applications which have "hard" real-time deadlines that need to be met in the event of crisis situations. In such cases, it is important to obtain contingency plans that may be invoked with guaranteed execution time characteristics. This paper presents an alternative model for real-time database systems in which deadlines are associated with "contingency" constraints rather than directly with transactions. Our approach leads to a predicate-based model that intrinsically incorporates both triggering and relative timing constraints regarding the transaction executions. We exhibit that selecting contingency plans with respect to various optimality criteria has inherent computational inefficiencies. We study the issues in scheduling of the selected plans with the focus on the contention among the transactions for data resources. Our results exhibit that the data contention, by itself, has a severe adverse impact on the schedulability of the deadline-constrained transactions. We discuss some of the practical implications of our results, and we suggest some counter-measures to handle the computational complexities.>

Continuous media applications, which require a guaranteed transfer rate of the data, are becoming an integral part of daily computational life. However, conventional file systems do not provide rate guarantees, and are therefore not suitable for the storage and retrieval of continuous media data (e.g., audio, video). To meet the demands of these new applications, continuous media file systems, which provide rate guarantees by managing critical storage resources such as memory and disks, must be designed.

Distributed real-time transaction systems are useful for both real-time and high-performance database applications. Standard transaction management approaches that use the two-phase commit protocol suffer from its high costs and blocking behavior which is problematic in real-time computing environments. Our approach in this paper is to identify ways in which a commit protocol can be made adaptive in the sense that under situations that demand it, such as a transient local overload, the system can dynamically change to a different commitment strategy. The decision to do so can be taken autonomously at any site. The different commitment strategies exploit a trade-off between the cost of commitment and the obtained degree of atomicity. Our protocols are based on optimistic commitment strategies, and they rely on local compensatory actions to recover from non-atomic executions. We provide the necessary framework to study the logical and temporal correctness criteria, and we describe examples to illustrate the use of our strategies.

Article Free Access Share on Strict histories in object-based database systems Authors: Rajeev Rastogi View Profile , Henry F. Korth View Profile , Abraham Silberschatz View Profile Authors Info & Claims PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsAugust 1993 Pages 288–299https://doi.org/10.1145/153850.153934Published:01 August 1993Publication History 9citation293DownloadsMetricsTotal Citations9Total Downloads293Last 12 Months13Last 6 weeks0 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

In a number of application environments #e.g., computer aided design#, serializability, the traditionally accepted notion of correctness has been found to be too restrictive, and a number of alternate criteria have been proposed in the literature. One such criterion is predicate-wise serializability #PWSR#, which requires only restrictions of schedules that access subsets of the database over whichintegrity constraints are de#ned, to be serializable. In this paper, we identify restrictions on the structure of transaction programs, their concurrent execution and their access characteristics under which PWSR schedules preserve database consistency. Keywords: Transactions, Schedules, Concurrency Control, Integrity Constraints, Database States. Note: Preprint of the version that appears in Journal of Computer Systems and Software #JCSS# 2 1 Introduction In the standard transaction model #3#, a database state is said to be consistent if all database integrity constraints are satis#ed. ...

A transaction model for multidatabase system (MDBS) applications in which global subtransactions may be either compensatable or retriable is presented. In this model compensation and retrying are used for recovery purposes. However, since such executions may no longer consist of atomic transactions, a correctness criterion that ensures that transactions see consistent database states is necessary. A commit protocol and a concurrency control scheme that ensures that all generated schedules are correct are also presented. The commit protocol eliminates the problem of blocking, which is characteristics of the standard 2PC protocol. The concurrency control protocol can be used in any MDBS environment irrespective of the concurrency control protocol followed by the local DBMSs in order to ensure serializability.>

In this paper we study the problem of ensuring atomicity of transactions in a multidatabase system (MDBS).

A Multidatabase System (MDBS) is a collection of local database management systems, each of which may follow a different concurrency control protocol. This heterogeneity makes the task of ensuring global serializability in an MDBS environment difficult. In this paper, we reduce the problem of ensuring global serializability to the problem of ensuring serializability in a centralized database system. We identify characteristics of the concurrency control problem in an MDBS environment, and additional requirements on concurrency control schemes for ensuring global serializability. We then develop a range of concurrency control schemes that ensure global serializability in an MDBS environment, and at the same time meet the requirements. Finally, we study the tradeoffs between the complexities of the various schemes and the degree of concurrency provided by each of them.

Recovery activities, like checkpointing and restart, in traditional database management systems are performed in a quiescent state where no transactions are active. This approach impairs the performance of online transaction processing systems, especially when a large volatile memory is used. An incremental scheme for performing recovery in main memory database systems (MMDBs), in parallel with transaction execution, is presented. A page-based incremental restart algorithm that enables the resumption of transaction processing as soon as the system is up is proposed. Pages are recovered individually and according to the demands of the post-crash transactions. A method for propagating updates from main memory to the backup database on disk is also provided. The emphasis is on decoupling the I/O activities related to the propagation to disk from the forward transaction execution in memory. The authors also construct a high-level recovery manager based on operation logging on top of the page-based algorithms. The proposed algorithms are motivated by the characteristics of large MMDBs, and exploit the technology of nonvolatile RAM.>

A novel experimental procedure, based on a standard statistical estimation procedure, is presented to estimate the performance of transitive closure algorithms. This experimental procedure has been exemplified in three contexts: (1) comparison of a suite of algorithms: (2) analysis of one particular algorithm; and (3) analysis of the transitive closure problem itself. It is shown that the number of duplicate edges generated (by most algorithms) can be more than ten times the size of the transitive closure, even for small graphs. The majority of these duplicates are due to the existence of strongly connected components in the graph. This experimental approach can be generalized to estimate various performance metrics for a large class of database queries. It is both simple and general and provides the necessary ingredients for a guess-and-verify paradigm of testing hypotheses.>

An alternative approach to distributed transaction processing based on the unilateral commit paradigm (UCP) and on persistent transmission is proposed. Instead of executing a unit of work as a single distributed transaction, as in the traditional transaction execution paradigm, opportunities are looked for to execute it as a structured set or a sequence of smaller, possibly single-site atomic transactions. Each such transaction, once executed, is committed independently of other transactions in the task. A method for rigorously maintaining the linkage between the steps is provided for by a persistent transmission mechanism. It is argued that UCP is especially attractive since it relies on a site's ability to execute conventional flat local transactions and does not require additional capabilities such as the ability to execute nested transactions.>

Supporting atomicity of multi-site transactions in a distributed transaction management system is equated with long-duration delays, blocking, and loss of autonomy of the individual sites.The two-phase Com-

article An optimistic commit protocol for distributed transaction management Share on Authors: Eliezer Levy Department of Computer Sciences, University of Texas at Austin, Austin, TX Department of Computer Sciences, University of Texas at Austin, Austin, TXView Profile , Henry F. Korth Department of Computer Sciences, University of Texas at Austin, Austin, TX Department of Computer Sciences, University of Texas at Austin, Austin, TXView Profile , Abraham Silberschatz Department of Computer Sciences, University of Texas at Austin, Austin, TX Department of Computer Sciences, University of Texas at Austin, Austin, TXView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 88–97https://doi.org/10.1145/119995.115800Online:01 April 1991Publication History 72citation911DownloadsMetricsTotal Citations72Total Downloads911Last 12 Months19Last 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 SiteGet Access

The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined. This class of transaction management mechanisms is important, because it simplifies transaction management in a multidatabase system environment. The notion of analogous execution and serialization orders of transactions is defined and the concept of strongly recoverable and rigorous execution schedules is introduced. It is then proven that rigorous schedulers always produce analogous execution and serialization orders. It is shown that the systems using the rigorous scheduling can be naturally incorporated in hierarchical transaction management mechanisms. It is proven that several previously proposed multidatabase transaction management mechanisms guarantee global serializability only if all participating databases systems produce rigorous schedules.>

Network Partition failures in traditional Distributed Databases cause severe problems for transaction processing. The only way to overcome the problems of “blocking” behavior for transaction processing in the event of such failures is, effectively, to execute them at single sites. A new approach to data representation and distribution is proposed and it is shown to be suitable for failure-prone environments. We propose techniques for transaction processing, concurrency control and recovery for the new representation. Several properties that arise as a result of these methods, such as non-blocking behavior, independent recovery and high availability, suggest that the techniques could be profitably implemented in a distributed environment.

A model of a multidatabase system is defined in which each local DBMS uses the two-phase locking protocol Locks are released by a global transaction only after the transaction commits or aborts at each local site. Failures may occur during the processing of transactions. We design a fault tolerant transaction management algorithm and recovery procedures that retain global database consistency. We also show that our algorithms ensure freedom from global deadlocks of any kind.

This paper presents several complementary methods for the parallel, bottom-up evaluation of Datalog queries. We introduce the notion of a discriminating predicate, based on hash functions, that partitions the computation between the processors in order to achieve parallelism. A parallelization scheme with the property of non-redundant computation (no duplication of computation by processors) is then studied in detail. The mapping of Datalog programs onto a network of processors, such that the results is a non-redundant computation, is also studied. The methods reported in this paper clearly demonstrate the trade-offs between redundancy and interprocessor-communication for this class of problems.

Abstract Hopfield nets are a class of neural networks that are often applied to optimisation problems. The role played by certain constants appearing in the interconnections are crucial to the computations. A bad choice of constant values results in the convergence of the system to states that represent extraneous results. This paper examines a discrete model of the nets which allows a better characterisation of the constants. The formal approach followed in this paper allows the specification of values to the constants that ensure convergence of the system to states that represent results that are not extraneous. Using the Hopfield nets terminology, we have identified methods to remove extraneous energy minima in the discrete version of the system. Since any simulation study of Hopfield nets on real computers must use discretised approximations to analog values, the results are of interest in a practical domain as well.

A database query is safe if its result consists of a finite set of tuples. If a query is expressed using a set of pure Horn Clauses, the problem of determining query safety is, in general, undecidable. In this paper we consider a slightly stronger notion of safety, called supersafety, for Horn databases in which function symbols are replaced by the abstraction of infinite relations with finiteness constraints [Ramarkrishman et. al 87] We show that the supersafety problem is not only decidable, but also axiomatizable, and the axiomatization yields an effective decision procedure. Although there are safe queries which are not supersafe, we demonstrate that the latter represent quite a large and nontrivial portion of the safe of all safe queries

This paper is concerned with the issue of parallel evaluation of logic programs. To address this issue we define a new concept of predicate decomposability. If a predicate is decomposable, it means that the load of evaluating it can be divided among a number of processors, without a need for communication among them. This in turn results in a very significant speed-up of the evaluation process.

Abstract PICASSO (PICture Aided Sophisticated Sketch Of database queries) is a graphics‐based database query language designed for use with a universal relation database system. The primary objective of PICASSO is ease of use. Graphics are used to provide a simple method of expressing queries and to provide visual feedback to the user about the system's interpretation of the query. Inexperienced users can use the graphical feedback to aid them in formulating queries whereas experienced users can ignore the feedback. Inexperienced users can pose queries without knowing the details of underlying database schema and without learning the formal syntax of SQL‐like query language. This paper presents the syntax of PICASSO queries and compares PICASSO queries with similar queries in standard relational query languages. Comparisons are also made with System/U, a non‐graphical universal relation system on which PICASSO is based. The hypergraph semantics of the universal relation are used as the foundation for PICASSO and their integration with a graphical workstation enhances the usability of database systems.

Relaxing the assumption that relations are always in First-Normal-Form (1NF) necessitates a reexamination of the fundamentals of relational database theory. In this paper we take a first step towards unifying the various theories of ¬1NF databases. We start by determining an appropriate model to couch our formalisms in. We then define an extended relational calculus as the theoretical basis for our ¬1NF database query language. We define a minimal extended relational algebra and prove its equivalence to the ¬1NF relational calculus. We define a class of ¬1NF relations with certain “good” properties and extend our algebra operators to work within this domain. We prove certain desirable equivalences that hold only if we restrict our language to this domain.

A database query is said to be safe if its result consists of a finite set of tuples If a query is expressed using a set of pure Horn Clauses, the problem of determining whether it is safe is in general undecidable In this paper, we show that the problem is decidable when terms involving function symbols (including arithmetic) are represented as distinct occurrences of uninterpreted infinite predicates over which certain finiteness dependencies hold. We present a sufficient condition for safety when some monotonicity constraints also hold.

It has been recognised that languages like Concurrent Prolog and Parlog which use committed choice non-determinism have departed from the original concept of logic programming, but no new paradigm has been suggested. In this paper we propose that programs in such languages be viewed as rewrite rules that hierarchically decompose a process into a network of distributed processes. Logical variables and unification provide a powerful means of communication, and annotations can provide a synchronization mechanism that complements them.

This paper presents a formal model of linear array processors suitable for VLSI implementation as well as graph representations of programs suitable for execution on such a model. A distinction is made between correct mapping and correct execution of such graphs on this model and the structure of correctly mappable graphs are examined. The formalism developed is used to synthesize algorithms for this model.

Backward error recovery is a popular technique for recovery from unexpected system failures. In a concurrent processing environment, the synchronisation constraints and the propagation of erroneous information between processes tend to make recovery very complex and expensive. In this paper we present a detailed analysis of error propagation and introduce a new classification for variables based upon their error-propagation characteristics. Necessary and sufficient conditions to ensure a finite upper bound on the computation discarded in the course of error recovery are developed. Several other recovery-related issues are also discussed.

Many database systems maintain the consistency of the data by using a locking protocol to restrict access to data items. It has been previously shown that if no information is known about the method of accessing items in the database, then the two-phase protocol is optimal. However, the use of structural information about the database allows development of non-two-phase protocols, called graph protocols , that can potentially increase efficiency. Yannakakis developed a general class of protocols that included many of the graph protocols. Graph protocols either are only usable in certain types of databases or can incur the performance liability of cascading rollback. In this paper, it is demonstrated that if the system has a priori information as to which data items will be locked first by various transactions, a new graph protocol that is outside the previous classes of graph protocols and is applicable to arbitrarily structured databases can be constructed. This new protocol avoids cascading rollback and its accompanying performance degradation, and extends the class of serializable sequences allowed by non-two-phase protocols. This is the first protocol shown to be always as effective as the two-phase protocol, and it can be more effective for certain types of database systems.

A locking protocol is a set of rules governing the manner in which the database entities may be accessed. Such a protocol usually employs several kinds of locks. Most of the previous work in this area has assumed that once a transaction acquires a particular kind of lock on a data item it is not allowed to convert this lock to another kind. In this paper we perform a systematic study of the consequences of allowing lock conversions in non-two-phase locking protocols, and show how this leads to increased concurrency and affects deadlock-freedom. The non-two-phase protocols that we study are the very general guard protocols defined for databases in which a directed acyclic graph structure can be superimposed on the data items. We present very natural generalizations of these protocols, including correctness proofs, and develop deadlock removal methods.

A large number of locking protocols use precedence relations among data items to ensure the serializability of the database system. These protocols have extended the semantics of the exclusive lock from prohibiting access to a data item to prohibiting access to an entire subgraph. In this paper we argue that combining the use of exclusive locks for these different purposes is ill conceived. We present a general theory on how these two distinct functions can be separated into the traditional locks operating on the individual data items, and a corresponding set operating on the edges of graph. This is illustrated by a general transformation from a given graph protocol to the new edge protocol which preserves the major properties of the original protocol. We then give a characterization for a large class of edge lock protocols within a database system, which includes most previous locking protocols defined on databases organized as graphs. We show how this separation increases concurrency, and generalizes previously unrelated concepts, such as using deadlock avoidance locks in general locking protocols.

The heterogeneous guard locking protocol is a general non-two-phase locking protocol that is applicable to database systems organized as rooted directed acyclic graphs. The protocol is one of the few serializable protocols that employs both shared and exclusive locks and yet remains deadlock free. In this note we present the protocol and prove that it ensures freedom from deadlock. This in turn implies that consistency of the database can be maintained without resorting to transaction rollback.

This paper presents a new language construct for distributed computing. This construct, called cell, allows one to simulate a variety of language constructs, Its salient features provide the programmer with: 1) an effective communication and synchronization scheme, 2) a mechanism to control the order in which various activities within a cell should be executed. We demonstrate the usefulness of our concepts by providing solutions to a variety of programming exercises.

This paper is concerned with the problem of developing a family of locking protocols which employ both SHARED and EXCLUSIVE locks and which ensure the consistency of database systems that are accessed concurrently by a number of asynchronously running transactions.First, a general result concerning extensions of all protocols that employ EXCLUSIVE locks only to also employ SHARED locks is presented.Then a famdy of protocols apphcable to database systems that are modeled by directed acydtc graphs Is presented.

Writing distributed algorithms in Hoare's CSP becomes more convenient if output statements are allowed in the guards of alternative and iterative commands.The major drawbacks of the previously published implementations of this construct are discussed.Criteria for an effective implementation are presented, and an algorithm that meets these criteria is constructed.

data types, and in particular those that are designed to provide resources for use by concurrently executable programs, are often designed to be used only in certain ways.The intended constraints on use of an instance of such a type can be expressed in two principal ways: as assertions on the domain of values input to each operator, and as constraints on the sequences in which the operators of the type can be called by a customer process.These constraints must be enforced in the environment in which an instance of the type is used.Nevertheless, they are very much a part of the type specification, for its definition is not complete, nor can the consistency of its representation be proved, without them.A notation is provided in which to express sequential constraints, which are here called accessright expressions.It is suggested that these expressions should be declared in a programming language that supports the definition of monitors or resource managers.Implications for the proof rules of monitors are discussed, and suggestions are made for a programming language implementation.

In his paper "Communicating Sequential Processes," Hoare suggested the use of the input/output construct and Dijkstra's guarded commands for handling the task of communication and synchronization in distributed systems. Hoare's proposal was intended for programming general parallel systems; as a result, little consideration was given by Hoare to the question of how his mechanisms could be utilized in the construction of reliable dynamic resource management schemes. In this paper, we examine this problem and propose several simple extensions to Hoare's constructs that will make the extended Communicating Sequential Processes concept more suitable for the handling of such management schemes.

A transaction is atomic if it can be considered, as far as other transactions are concerned, to be indivisible and instantaneous even in the case of failure. An almost universally accepted way to ensure atomicity is to use a strict two-phase locking protocol with a roll-back scheme for recovery in case of deadlock or failure. In this note, we argue that this method is not the most economical way to achieve this end. We develop a Dependency Graph model which is used to analyze the two-phase and non-two-phase locking schemes. It is shown that one way of choosing between the two types of schemes is to estimate the number of rollbacks required. If this number is large, a two-phase scheme is preferable; if small, a non-two-phase scheme should be selected. We demonstrate that with reasonable discipline, the number of such rollbacks can be minimized. Thus, contrary to common practice and belief, non-two-phase protocols can be effectively used in guaranteeing atomicity.

The multi-version data item concept is a method for increasing concurrency in a database system. All previously proposed schemes utilizing this concept relied on transaction rollback as a means for preserving consistency. These rollbacks require a considerable amount of overhead which degrades performance. In this paper we develop a new scheme that utilizes the multi-version data item concept. Our proposed scheme ensures consistency without the use of rollbacks. It is based upon the non-two phase tree locking protocol previously proposed by Silberschatz and Kedem.

Research on concurrency control mechanisms for database systems has had as a primary goal the discovery of techniques for allowing increased levels of concurrent execution of transactions. In this paper, we study this problem in the context of non-two-phase locking protocols which are defined for data bases in which a directed acyclic graph structure is superimposed on the data items. We introduce a new lock mode, called INV, with properties fundamentally different from locking modes previously studied and show how this allows increased concurrency. Through the introduction of the INV mode of locking we have enunciated a new principle of the theory of data base concurrency control. This principle involves the separation of the effects of the commutativity and compatibility of data manipulation operations. We then examine how the introduction of such a lock mode affects the occurrence of deadlocks in a system. Certain conditions under which deadlock-freedom is maintained are identified, and simple methods for removing deadlocks in other situations are presented.

In Concurrent Pascal, an explicit hierarchy of access rights to abstract variables is stated in the program text and checked by the compiler. This declarative control of static access rights provides a considerable degree of protection against unauthorized use of an abstract variable by an errant program component. However, there are cases in which the mechanism of Concurrent Pascal falls short of enforcing the principle that each program component should have within its name space only those rights of access to variables that it requires. This paper outlines an extension to the static access control mechanism of Concurrent Pascal that can enforce the need-to-know principle.

This paper is concerned with the problem of ensuring the integrity of database systems that are accessed concurrently by a number of independent asychronously running transactions. It is assumed that the database system is partitioned into small units that are referred to as the database entities. The relation between the entities is represented by a directed acyclic graph in which the vertices correspond to the database entities and the arcs correspond to certain access rights. We develop a family of non-two-phase locking protocols for such systems that will be shown to ensure serializability and deadlock-freedom. This family is sufficientdy general to encompass all the previously developed non-two-phase lose locking protocols as well as a number of new protocols. One of these new protocols that seems to be particularly useful is also presented in this paper.

The problem of removing deadlocks from concurrent database systems using the two-phase locking protocol is considered. In particular, for systems which use no a priori information about transaction behavior in order to avoid deadlocks, it has generally been assumed necessary to totally remove and restart some transaction involved in a deadlock in order to relieve the situation. In this paper, a new approach to deadlock removal in such systems based on partial rollbacks is introduced. This approach does not in general require the total removal of a transaction to eliminate a deadlock. The task of optimizing deadlock removal using this method is discussed for systems allowing both exclusive and shared locking. A method is given for implementing this approach with no more storage overhead than that required for total removal and restart.

Abstract This paper examines various issues that pertain to the access‐control mechanism of the program component manager. We examine such questions as what constitutes an access‐right, what kind of information about managed resources does one need, how revocation keys, right‐sets, and exception conditions are handled, etc. It is argued that most of these issues can be handled by the compiler with no explicit programming required. This simplifies the task of programming and enhances reliability. A possible method for handling these issues which was adopted in our implementation is also described.

The problems of locking and consistency m database systems are examined It is assumed that each transacuon, when executed alone, transforms a consistent state into a consistent state A set of conditions is derived to guarantee that when transactions are processed concurrently, the results are the same as would be obtained by processing the transactmns serially These conditions are used to estabhsh a locking protocol in Merarchmal database systems The locking protocol allows transaeuons to request new locks after releasing a lock.However, a data item may be locked at most once as a result of each transacUon It ~s shown that the protocol ensures consistency and that tt ts deadlock free.

This paper is concerned with the problem of developing locking protocols for ensuring the consistency of database systems that are accessed concurrently by a number of independent transactions. It is assumed that the database is modelled by a directed acyclic graph whose vertices correspond to the database entities, and whose arcs correspond to certain locking restrictions. Several locking protocols are presented. The weak protocol is shown to ensure consistency and deadlock-freedom only for databases that are organized as trees. For the databases that are organized as directed acyclic graphs, the strong protocol is presented. Discussion of SHARED and EXCLUSIVE locks is also included.

In Concurrent PASCAL the peripheral device disc is viewed as an array of pages which can only be accessed via the standard procedure IO. On of the input parameters to the procedure is an index I to indicate which page in the array has to be accessed. The IO procedure can be invoked from any system module and the index I can be set arbitrarily by that module. Hence, one system module can jeopardise the integrity of a system written in this language. This paper proposes an extension to Concurrent PASCAL to resolve this difficulty. In particular, we define a new concept scope which specifies the names of the program components which can declare an instance of a particular type. Given this concept and the program component manager, we devise a mechanism which will be shown to be consistent with the design goals of Concurrent PASCAL and which can be used to enforce processes to use the IO procedure with the index I set to only those pages which they have a legal right to access.

In his recent paper, “Communicating Sequential Processes” ( Comm. ACM 21, 8 (Aug. 1978), 666-677), C.A.R. Hoare outlines a programming language notation for interprocess communication in which processes are synchronized by the messages they exchange. The notation carries with it certain implications for the synchronization protocols required in a message transfer. These are not at all obvious and are made explicit here. An alternative convention is suggested in which communication and synchronization are partially uncoupled from one another.

Recent advances in technology have made the construction of general-purpose systems out of many small independent microprocessors feasible. One of the issue's concerning distributed systems is the question of appropriate language constructs for the handling of communication and synchronization. In his paper, "Communicating sequential processes," Hoare has suggested the use of the input and output constructs and Dijkstra's guarded commands to handle these two issues. This paper examines Hoare's concepts in greater detail by concentrating on the following two issues: 1) allowing both input and output commands to appear in guards, 2) sinple abstract implementation of the input and output constructs.

Synchronous and asynchronous operation of software systems are defined. It is argued that certifying the correct operation of a system in the synchronous mode is significantly simpler than in the asynchronous mode. A series of compile-time and run-time restrictions for systems constructed in Concuirent Pascal are presented which assure equivalent operation in the synchronous and asynchronous modes.

The use of capabilities to control the access of component programs to resources in an operating system is an attractive means by which to provide a uniform protection mechanism. In this paper, a capability is defined as an abstract encapsulation of the data needed to define access to a protected object. We do not assume that capability checking is necessarily concentrated in a protection kernel, nor that capabilities to different types of objects are all of the same degree of complexity. We explore a language-based capability mechanism in which protection environments are established by declaration, enforcement protocols are automatically produced by a compiler, and access control policy is clearly placed in the hands of the system designer. The basic mechanism introduced is a program component called a capability manager that is an extension of the monitor concept. It can be used to realize most of the facilities associated with kernel-based capabilities, including preemptive revocation.

In Concurrent Pascal, the syntactic and semantic definition of the language prevents the inadvertent definition of a program that might violate the integrity of a shared data object. However, the language also does not allow the dynamic allocation of reusable resources among processes, and this restriction seems unnecessarily stingent. This paper proposes the addition to Concurrent Pascal of a new type of program component, to be called a resource manager. By this means, dynamic resource allocation can be accomplished both safely and efficiently. The notion that a process holds access rights to a resource is generalized to the notion that it holds capability rights, but the capability to atually make use of a resource is granted dynamically. The anonymity of dynamically allocatable resources is also guaranteed.