Thumbnail
Access Restriction
Subscribed

Author Sacc, Domenico
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1985
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A hypergraph formalism is introduced to represent database schemata. In particular, a database schema $\textit{B},$ described by one full join dependency and a set of functional dependencies, is represented by a (database) hypergraph $\textit{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: $\textit{e}-acyclic$ hypergraphs and $\textit{e}-independent$ hypergraphs. A hypergraph is $\textit{e}-acyclic$ if it is equivalent to some acyclic hypergraph; it is $\textit{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 $\textit{e}-acyclic$ $(\textit{e}-independent)$ hypergraphs are equivalent if and only if they have the same closure. Moreover, a hypergraph is $\textit{e}-acyclic$ $(\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 4
Page Count 30
Starting Page 774
Ending Page 803


Open content in new tab

   Open content in new tab
Source: ACM Digital Library