Interval Graphs and Hypergraph Acyclicity Degree

摘要

In recent years much research has been devoted to the study of hypergraphs andtheir utility as relational database scheme models. It has been shown that such schemes enjoy certain desirable properties (e. g., monotone join expressions); that there is a linear ordering of the strengths; (none of the reverse implications hold); and that strengthening the 'degree' of acyclicity also strengthens the related desirable properties. Furthermore, it is known that a reduced hypergraph is alpha-acyclic if, and only if, it is conformal and its associated graph is chordal (1,4). The purpose of this report is to exhibit that a reduced conformal hypergraph is beta-acyclic if its associated graph is an interval graph. As suggested by the previous theorem, if a collection of data has attributes with a natural interval graph representation, then it is possible to organize these data into a beta acyclic relational scheme (e.g., tracking data collected over time intervals). This may be an expedient design if resource allocation and deconfliction are important (conflicting attributes are in the same relation); frequent join operations are required and/or the databases are distributed.