# Degrees of acyclicity for hypergraphs and relational database schemes

@article{Fagin1983DegreesOA, title={Degrees of acyclicity for hypergraphs and relational database schemes}, author={Ronald Fagin}, journal={J. ACM}, year={1983}, volume={30}, pages={514-550} }

Database schemes (winch, intuitively, are collecuons of table skeletons) can be wewed as hypergraphs (A hypergraph Is a generalization of an ordinary undirected graph, such that an edge need not contain exactly two nodes, but can instead contain an arbitrary nonzero number of nodes.) A class of "acychc" database schemes was recently introduced. A number of basic desirable propemes of database schemes have been shown to be equivalent to acyclicity This shows the naturalness of the concept… Expand

#### Figures and Topics from this paper

#### 427 Citations

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

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

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

Interval Graphs and Hypergraph Acyclicity Degree

- Mathematics
- 1991

Abstract : In recent years much research has been devoted to the study of hypergraphs and their utility as relational database scheme models. It has been shown that such schemes enjoy certain… Expand

On the Existence of Acyclic Views in a Database Scheme

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1985

It is shown that the problem of deciding whether there exists a Berge-, γ-, or α-acyclic view in a general database scheme is NP-complete and that the Problem of decidingWhether there exists an Berge- or γ-acyClic view on an α-ACYclic scheme is also computationally intractable. Expand

On the Desirability of Acyclic Database Schemes

- Mathematics, Computer Science
- JACM
- 1983

It is shown that this class of database schemes, called acychc, has a number of desirable properties that have been studied by other researchers and are shown to be eqmvalent to acydicity. 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

On the Desirability of gamma-Acyclic BCNF Database Schemes

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1988

This paper proves that γ-acyclic Boyce-Codd Normal Form database schemes are highly desirable with respect to query processing and updates, and derives a simple and efficient algorithm that determines if an updated state is consistent. Expand

Binary Decompositions and Acyclic Schemes

- Computer Science
- FSTTCS
- 1986

This paper proposes the formalism of "binary decompositions", which describes design sequences that exactly generate θ-acyclic schemes, for θ = α,β, and demonstrates its power by showing that it leads to a significant simplification of the proofs of some previous results connecting sets of multivalued dependencies and acyclic join dependencies. Expand

#### References

SHOWING 1-10 OF 75 REFERENCES

On the Desirability of Acyclic Database Schemes

- Mathematics, Computer Science
- JACM
- 1983

It is shown that this class of database schemes, called acychc, has a number of desirable properties that have been studied by other researchers and are shown to be eqmvalent to acydicity. 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

Join Graphs and Acyclic Database Schemes

- Computer Science
- VLDB
- 1981

This paper provides a sufficient condition for a join dependency to be acyclic and an algorithm that can aid a database designer and gives two distinct methods that the designer can use to solve this problem. Expand

Tree queries: a simple class of relational queries

- Computer Science
- TODS
- 1982

It is argued, qualitatively, that queries which imply a tree schema are easier to process than those implying a cyclic schema, and the study of the semijoin operator is extended. Expand

Equivalence of relational database schemes

- Computer Science
- STOC
- 1979

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

Assumptions in relational database theory

- Computer Science
- PODS
- 1982

The purpose of the present paper is to clarify many of the existing assumptions, and point out weaknesses, and to evaluate recent suggestions that certain assumptions may be useful for modeling "real world" databases. Expand

The revenge of the JD

- Mathematics, Computer Science
- PODS '83
- 1983

If the user's view is the representative instance, then the ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme. 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

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