Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0624.68087
Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis
On the desirability of acyclic database schemes. (English)
[J] J. Assoc. Comput. Mach. 30, 479-513 (1983). ISSN 0004-5411

A class of database schemes, called acyclic, 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 in very different terms are all shown to be equivalent to acyclicity. In addition, several equivalent characterizations of the class in terms of graphs and hypergraphs are given, and a simple algorithm for determining acyclicity is presented. Also given are several equivalent characterizations of those sets M of multivalued dependencies such that M is the set of multivalued dependencies that are the consequences of a given join dependency. Several characterizations for a conflict-free (in the sense of Lien) set of multivalued dependencies are provided.

MSC 2000:: *68P20 Information storage and retrieval
05C65 Hypergraphs

Keywords: relational database; conflict-freedom; database schemes; acyclicity; hypergraphs; multivalued dependencies; join dependency

Cited in: Zbl 0643.68173

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]