A new approach to the problem of achieving serializability for real-time transaction systems is presented. It is shown that certain properties that have been claimed to be characteristic of real-time systems are sufficient in themselves to guarantee that the system will run serializably, without any extra effort having to be taken. These systems can be said to achieve serializability "for free.".>

The maintenance problem of a database scheme is the following decision problem: Given a consistent database state ρ and a new tuple u over some relation scheme of ρ, is the modified state ρ ∪ { u } still consistent? A database scheme is said to be constant-time-maintainable(ctm) if there exists an algorithm that solves its maintenance problem by making a fixed number of tuple retrievals. We present a practically useful algorithm, called the canonical maintenance algorithm , that solves the maintenance problem of all ctm database schemes within a "not too large" bound. A number of interesting properties are shown for ctm database schemes, among them that non-ctm database schemes are not maintainable in less than a linear time in the state size. A test method is given when only cover embedded functional dependencies (fds) appear. When the given dependencies consist of fds and the join dependency (jd) ⋈ R of the database scheme, testing whether a database scheme is ctm is reduced to the case of cover embedded fds. When dependency-preserving database schemes with only equality-generating dependencies (egds) are considered, it is shown that every ctm database scheme has a set of dependencies that is equivalent to a set of embedded fds, and thus, our test method for the case of embedded fds can be applied. In particular, this includes the important case of lossless database schemes with only egds.

The question “Is a given join dependency equivalent to some set of multivalued dependencies?” led to the development of acyclicity theory [1]. The central question of this paper is: “Is a given equality-generating dependency equivalent to a set of functional dependencies?” An algorithm is presented that answers that question in polynomial time without using the chase process and, in the case of a “yes” answer, can be used to find (a cover of) the set of functional dependencies involved. This question is also related to the similar question about join dependencies and multivalued dependencies by proving a result about the hypergraph representation of an egd. It is interesting to note that a minimal representation of an egd must be β-acyclic for the egd to be equivalent to a set of fd's, in contrast to the jd/mvd case, in which only α-acyclicity is needed. The β-acyclicity of an egd not necessarily minimal is always sufficient for the egd to be equivalent to a set of fd's as shown. Finally, the algorithm is extended for a single egd to answer the question whether a set of egd's with the same right-hand-side column is equivalent to a set of fd's.

Article Free Access Share on Constant time maintenance or the triumph of the FD. Authors: Marc H. Graham Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile , Ke Wang Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985 Pages 202–216https://doi.org/10.1145/6012.6017Published:01 June 1985Publication History 13citation193DownloadsMetricsTotal Citations13Total Downloads193Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract. There are many examples of actions on abstract data types which can be correctly implemented with nonserralizable and nonrecoverable schedules of reads and writes We examme a model of multiple lay-ers of abstraction that explains this phenomenon and suggests an approach to burldmg layered systems with transaction oriented synchromzatron and roll back Our model may make rt easier to provide the high data m-tegrrty of reliable database transaction processmg m a broader class of mformatron systems We concentrate on the recovery aspects here, a technical report [Moss et al 851 has a more complete drscussron of concurrency control 1

Two notions of dependency satisfaction, consistency and completeness , are introduced. Consistency is the natural generalization of weak-instance satisfaction and seems appropriate when only equality-generating dependencies are given, but disagrees with the standard notion in the presence of tuple-generating dependencies. Completeness is based on the intuitive semantics of tuple-generating dependencies but differs from the standard notion for equality-generating dependencies. It is argued that neither approach is the correct one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances. Consistency and completeness of a state are characterized in terms of the tableau associated with the state and in terms of logical properties of a set of first-order sentences associated with the state. A close relation between the problems of testing for consistency and completeness and of testing implication of dependencies is established, leading to lower and upper bounds for the complexity of consistency and completeness. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined.

Article Free Access Share on Reliable scheduling of database transactions for unreliable systems Authors: Marc H. Graham Georgia Institute of Technology, Atlanta, Georgia Georgia Institute of Technology, Atlanta, GeorgiaView Profile , Nancy Griffeth Georgia Institute of Technology, Atlanta, Georgia Georgia Institute of Technology, Atlanta, GeorgiaView Profile , Barbara Smith-Thomas University of North Carolina at Greensboro, Greensboro, North Carolina University of North Carolina at Greensboro, Greensboro, North CarolinaView Profile Authors Info & Claims PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systemsApril 1984Pages 300–310https://doi.org/10.1145/588011.588055Published:02 April 1984Publication History 6citation199DownloadsMetricsTotal Citations6Total Downloads199Last 12 Months18Last 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

A database is consistent with respect to a set σ of dependencies if it has a weak instance. A weak instance is a universal relation that satisfies Σ, and whose projections on the relation schemes are supersets of the relations in the database. In this paper we investigate the complexity of testing consistency and the logics that can axiomatize consistency, relative to a fixed set Σ of dependencies. If Σ is allowed to include embedded dependencies, then consistency can be non-recursive. If Σ consists only of total dependencies, then consistency can be tested in polynomial time. The degree of the polynomial can, however, be arbitrarily high. Consistency can be axiomatized but not finitely axiomatized by equality generating dependencies. If embedded dependencies are allowed then consistency cannot be finitely axiomatized by any effective logic. If, on the other hand, only total dependencies are allowed then consistency can be finitely axiomatized by fixpoint logic.

Article Free Access Share on Path expressions in databases Author: Marc H. Graham Georgia Institute of Technology, Atlanta, Georgia Georgia Institute of Technology, Atlanta, GeorgiaView Profile Authors Info & Claims PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1983 Pages 366–378https://doi.org/10.1145/588058.588101Online:21 March 1983Publication History 2citation164DownloadsMetricsTotal Citations2Total Downloads164Last 12 Months6Last 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study how functional dependencies affect the cyclicity of a database scheme; in particular, when does a set of functional dependencies make a cyclic database scheme behave like an acyclic one.A database scheme is fd-acyclic if every pairwise-consistent database state that satisfies the fd's is join-consistent. We give a simple characterization of fd-acyclicity over a restricted class of database schemes. We then give a tableau-based characterization for the general case that leads to an algorithm for testing fd-acyclicity. This algorithm actually solves the more general problem of query equivalence under functional dependencies and typed inclusion dependencies.

We discuss the objectives of including functional dependencies in the definition of a relational database. We find two distinct objectives. The appearance of a dependency in the definition of a database indicates that the states of the database are to encode a function. A method based on the chase of calculating the function encoded by a particular state is given and compared to methods utilizing derivations of the dependency. A test for deciding whether the states of a schema may encode a nonempty function is presented as is a characterization of the class of schemas which are capable of encoding nonempty functions for all the dependencies in the definition. This class is the class of dependency preserving schemas as defined by Beeri et al. and is strictly larger than the class presented by Bernstein. The second objective of including a functional dependency in the definition of a database is that the dependency be capable of constraining the states of the database; that is, capable of uncovering input errors made by the users. We show that this capability is weaker than the first objective; thus, even dependencies whose functions are everywhere empty may still act as constraints. Bounds on the requirements for a dependency to act as a constraint are derived. These results are founded on the notion of a weak instance for a database state, which replaces the universal relation instance assumption and is both intuitively and computationally more nearly acceptable.

Two notions of dependency satisfaction, consistency and completeness, are introduced. Consistency is the natural generalization of weak satisfaction and seems appropriate when only equality-generating dependencies are given, but disagrees with the standard notion in the presence of tuple-generating dependencies. Completeness is based on the intuitive semantics of tuple-generating dependencies but appears unnatural for equality-generating dependencies. It is argued that neither approach is the correct one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances. Consistency and completeness of a state are characterized in terms of the tableau associated with the state and in terms of logical properties of a set of first-order sentences associated with the state. A close relation between the problems of testing for consistency and completeness and of testing implication of dependencies is established. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined.

Article Free Access Share on Independent database schemas Authors: Marc H. Graham University of Toronto, Toronto, Canada University of Toronto, Toronto, CanadaSearch about this author , Mihalis Yannakakis Bell Laboratories, Murray Hill, N.J. Bell Laboratories, Murray Hill, N.J.Search about this author Authors Info & Claims PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1982Pages 199–204https://doi.org/10.1145/588111.588144Published:29 March 1982Publication History 12citation246DownloadsMetricsTotal Citations12Total Downloads246Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF