A hypergraph formalism is introduced to represent database schemata. In particular, a database schema B, described by one full join dependency and a set of functional dependencies, is represented by a (database) hypergraph H, containing both undirected and directed hyperedges. Undirected hyperedges correspond to the relations in the join dependency, and directed hyperedges correspond to the functional dependencies. In addition, two classes of database hypergraphs are defined: e-acyclic hypergraphs and e-independent hypergraphs. A hypergraph is e-acyclic if it is equivalent to some acyclic hypergraph; it is e-independent if it is equivalent to some independent (i.e., cover-embedding) hypergraph. Furthermore, the closure of a database hypergraph is defined as the extension of the transitive closure of a graph. By using a lower bound and an upper bound of the hypergraph closure (called L-closure and U-closure, respectively), it is proved that two e-acyclic (e-independent) hypergraphs are equivalent if and only if they have the same closure. Moreover, a hypergraph is e-acyclic (e-independent) if and only if its closure is acyclic (independent) and, in most cases, such a recognition can be done in polynomial time. Finally, it is shown how to use the database hypergraph closure to solve some database design problems.

Closures of database hypergraphs / Sacca', Domenico. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - 32:4(1985), pp. 774-803.

Closures of database hypergraphs

SACCA', Domenico
1985

Abstract

A hypergraph formalism is introduced to represent database schemata. In particular, a database schema B, described by one full join dependency and a set of functional dependencies, is represented by a (database) hypergraph H, containing both undirected and directed hyperedges. Undirected hyperedges correspond to the relations in the join dependency, and directed hyperedges correspond to the functional dependencies. In addition, two classes of database hypergraphs are defined: e-acyclic hypergraphs and e-independent hypergraphs. A hypergraph is e-acyclic if it is equivalent to some acyclic hypergraph; it is e-independent if it is equivalent to some independent (i.e., cover-embedding) hypergraph. Furthermore, the closure of a database hypergraph is defined as the extension of the transitive closure of a graph. By using a lower bound and an upper bound of the hypergraph closure (called L-closure and U-closure, respectively), it is proved that two e-acyclic (e-independent) hypergraphs are equivalent if and only if they have the same closure. Moreover, a hypergraph is e-acyclic (e-independent) if and only if its closure is acyclic (independent) and, in most cases, such a recognition can be done in polynomial time. Finally, it is shown how to use the database hypergraph closure to solve some database design problems.
Database systems; database theory; hypergraph theory
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/143352
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 13
social impact