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

@inproceedings{Fagin1983AcyclicDS, title={Acyclic Database Schemes (of Various Degrees): A Painless Introduction}, author={Ronald Fagin}, booktitle={CAAP}, year={1983} }

Database schemes (which, intuitively, are collections of table skeletons) can be viewed 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.) Unlike the situation for ordinary undirected graphs, there are several natural, nonequivalent notions of acyclicity for hypergraphs (and hence for database schemes). A large number of desirable properties of… Expand

#### Figures and Topics from this paper

#### 42 Citations

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

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

Alpha-acyclic decompositions of relational database schemes

- Computer Science
- PODS '86
- 1985

We consider the design of database schemes satisfying the following three design properties: lossless join, Boyce-Codd normal form, and a-acyclicity. In particular the problem is investigated to… 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

Acyclic Hypergraphs and Relational Databases (A Survey)

- Computer Science
- CISM - Advances in Database Systems
- 1993

The survey summarizes results of acyclic hypergraphs and database investigations and gives short comparative analysis of different approaches. Expand

Minimal Coverings of Acyclic Database Schemata

- Computer Science
- Advances in Data Base Theory
- 1982

In this chapter classes of acyclic hypergraphs associated with classes of relational database schemata are investigated and several results concerning the computational complexity of determining minimal coverings are provided. Expand

Minimal Directed Hypergraphs

- 2004

In this paper we deal with directed hypergraphs. a generalization of directed graphs previously introduced in the literature. In parucular, we investigate the problem of maintaining efficiently… Expand

On the decomposition of join dependencies

- Computer Science, Mathematics
- PODS '84
- 1984

This paper recalls this decomposition methodology and its most important properties, and introduces a subclass of jd's, the unambiguous jd’s, which represents exactly thosejd's that have a unique decomposition (which can be obtained by this method). Expand

On the complexity of join dependencies

- Computer Science
- TODS
- 1986

In [10] a method is proposed for decomposing join dependencies (jds) in a relational database using the notion of a hinge. This method was subsequently studied in [11] and [12]. We show how the… Expand

Towards Designing Acyclic Database Schemes

- Computer Science
- Advances in Data Base Theory
- 1982

A modification of the synthesizing method to produce a third normal form, dependency preserving, lossless join decomposition of a universal relation scheme which is additionally acyclic and presents a decomposition theorem for acYclic database schemes. Expand

#### References

SHOWING 1-10 OF 47 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

Connections in Acyclic Hypergraphs

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

A sense in which the equivalence between blocks and biconnected components that holds in ordinary graph theory can be generalized to hypergraphs is demonstrated. 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

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

Acyclic Join Dependency and Data Base Projections

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1981

A new characterization of acyclic join dependency, based on “structured edge-trees,” is given and is used to obtain a variety of results on acy Cleric join dependency and a modification of the Graham reduction process. Expand

Algorithms for Acyclic Database Schemes

- Computer Science
- VLDB
- 1981

The purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction. Expand

Minimal Coverings of Acyclic Database Schemata

- Computer Science
- Advances in Data Base Theory
- 1982

In this chapter classes of acyclic hypergraphs associated with classes of relational database schemata are investigated and several results concerning the computational complexity of determining minimal coverings are provided. 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 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