On Quasi Cycles in Hypergraph Databases

Abstract

The notion of hypergraph cyclicity is important in numerous fields of application of hypergraph theory in computer science and relational database theory. The database scheme and query can be represented as a hypergraph. The database scheme (or query) has a cycle if the corresponding hypergraph has a cycle. An Acyclic database has several desired computational properties such as making query optimization easier and can be recognized in linear time. In this paper, we introduce a new type of cyclicity in hypergraphs via the notions of Quasi α-cycle(s) and the set of α-nodes in hypergraphs, which are based on the existence of an α–cycle(s). Then, it is proved that a hypergraph is acyclic if and only if it does not contain any α-nodes. Moreover, a polynomial-time algorithm is proposed to detect the set of α-nodes based on the existence of Quasi α-cycle(s), or otherwise claims the acyclicity of the hypergraph. Finally, a systematic discussion is given to show how to use the detected set of α-nodes to convert the cyclic hypergraph into acyclic one if the conversion is possible. The acyclic database and acyclic query enjoy time and/or space-efficient access paths for answering a query.