Article Free Access Share on Transaction restarts in Prolog database systems Authors: Shridhar Acharya Department of Computer Science, State University of New York, Stony Brook, NY Department of Computer Science, State University of New York, Stony Brook, NYView Profile , Gael Buckley Department of Computer Science, State University of New York, Stony Brook, NY Department of Computer Science, State University of New York, Stony Brook, NYView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 364–373https://doi.org/10.1145/318898.318986Published:01 May 1985Publication History 1citation238DownloadsMetricsTotal Citations1Total Downloads238Last 12 Months17Last 6 weeks2 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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

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.