# On the Desirability of Acyclic Database Schemes

@article{Beeri1983OnTD, title={On the Desirability of Acyclic Database Schemes}, author={Catriel Beeri and Ronald Fagin and David Maier and Mihalis Yannakakis}, journal={J. ACM}, year={1983}, volume={30}, pages={479-513} }

A class of database schemes, called acychc, was recently introduced. It is shown that this class has a number of desirable properties. In particular, several desirable properties that have been studied by other researchers m very different terms are all shown to be eqmvalent to acydicity. In addition, several equivalent charactenzauons of the class m terms of graphs and hypergraphs are given, and a smaple algorithm for determining acychclty is presented. Also given are several eqmvalent… Expand

#### 784 Citations

Degrees of acyclicity for hypergraphs and relational database schemes

- Mathematics, Computer Science
- JACM
- 1983

Various desirable properties of database schemes are constdered and it is shown that they fall into several equivalence classes, each completely characterized by the degree of acycliclty of the scheme. Expand

Dependency characterizations for acyclic database schemes

- Computer Science
- PODS '84
- 1984

Characterizations for β-, γ- and Berge-acyclic database schemes are provided: thus they should be useful for the database designer. Expand

On the recognition of coverings of acyclic database hypergraphs

- Computer Science
- PODS '83
- 1983

The normallzatlon processes proposed In the literature, which represent a first solution to the problem of designing acyclic database schemata that do not lead to undesirable anomalies, are presented. Expand

Recognition and Top-Down Generation of beta-Acyclic Database Schemes

- Computer Science
- FSTTCS
- 1984

Two complementary approaches to designing β-acyclic database schemes have been presented and a criterion for β- Stacyclicity is developed and is shown equivalent to the existing definitions of β-ACYclicity. Expand

On the recognition and design of acyclic databases

- Mathematics, Computer Science
- PODS '84
- 1984

In this paper a simple and homogeneous way to characterize the acyclicity degree of a database scheme is given, based on the existence in all acYclic database schemes of a nonempty set of relation schemes that satisfy a "pruning predicate", which is a property similar to the property satisfied by the leaves in an ordinary tree. Expand

Acyclic Database Schemes (of Various Degrees): A Painless Introduction

- Computer Science
- CAAP
- 1983

This paper is intended to be an informal introduction, in which the focus is mainly on the originally studied (and least restrictive) degree of acyclicity. Expand

On Acyclic Database Decompositions

- Computer Science, Mathematics
- Inf. Control.
- 1984

It is shown that there is a polynomial time algorithm to test for injectiveness of decompositions and it is proved that when the decomposition, viewed as a hypergraph, is acyclic and the given dependencies are full implicational dependencies, then the reconstruction map is the natural join. Expand

Elimination of intersection amomalies from database schemes

- Mathematics, Computer Science
- PODS '83
- 1983

This work analyzes the repetitive use of the basic step and proves that the transformation so defined removes all intersection anomalies, and characterize a class of attributes that can be removed from the final scheme, leaving it acyclic. Expand

Independence-reducible database schemes

- Mathematics, Computer Science
- JACM
- 1991

A generahzatlon of Sagiv-independent database schemes, called (key-equivalent) independence-reducible schemes, is defined, and it is shown that it 1s highly desirable with respect to query answering… Expand

Characterization of desirable properties of general database decompositions

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2005

The classical notions of “pairwise consistency implies global consistency” and “hypergraph acyclicity” are not equivalent in the general case, but rather are independent of each other, and may be considered separately or in combination, to yield varying strengths of desirability. Expand

#### References

SHOWING 1-10 OF 101 REFERENCES

Degrees of acyclicity for hypergraphs and relational database schemes

- Mathematics, Computer Science
- JACM
- 1983

Various desirable properties of database schemes are constdered and it is shown that they fall into several equivalence classes, each completely characterized by the degree of acycliclty of the scheme. Expand

Properties of acyclic database schemes

- Computer Science
- STOC '81
- 1981

The purpose of this paper is to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. Expand

Equivalence of Relational Database Schemes

- Mathematics, Computer Science
- SIAM J. Comput.
- 1981

It is argued that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question, and the “update sets” approach to database design is introduced. Expand

On the Equivalence of Database Models

- Computer Science
- JACM
- 1982

It is proved that network databases with loop-free Bachman diagrams are superior to relational databases which are free of conflicts and contenUons and shown that the decomposition approach can be apphed to conflictand contention-free relational databases without any of these problems. Expand

A simplied universal relation assumption and its properties

- Computer Science
- TODS
- 1982

This work proposes a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency, and characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Expand

On equivalences of database schemes

- Computer Science
- PODS
- 1982

This paper proposes a new definition of equivalence between database schemes that requires in an explicit manner the existence of common universal relations, namely the joins, through which the two schemes exchange information, and the resulting “fiipoint” equivalence is a strong one. Expand

Real-world MVD's

- Computer Science
- SIGMOD '81
- 1981

This paper investigates how much complexity is actually needed in real-world situations by showing that every "natural" set of mvd's must belong to a class of m DVD's called conflict-free, and it is shown that adding semantic concepts amounts to making the set ofmvd's conflict- free. Expand

Theory of Relations for Databases - A Tutorial Survey

- Computer Science
- MFCS
- 1978

This is an account of a theory of relations that has advanced from Codd's relational model of data for databases that deals with syntactic characterizations of the closed families of functional, multivalued, and general join dependencies that hold in relations. Expand

Decision Problems for Multivalued Dependencies in Relational Databases

- Mathematics, Computer Science
- SIAM J. Comput.
- 1979

In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M ofMultivalued dependencies on a set U of attributes, whose running time is proportional to min. Expand

Power of Natural Semijoins

- Computer Science
- SIAM J. Comput.
- 1981

This paper characterizes the queries for which full reducer exist and presents an efficient algorithm for constructing full reducers where they do exist and considers “natural” semijoin operator, which is used in the SDD-1 distributed database system. Expand