On Quasi Cycles in Hypergraph Databases

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 <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-cycle(s) and the set of <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-nodes in hypergraphs, which are based on the existence of an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>&#x2013;cycle(s). Then, it is proved that a hypergraph is acyclic if and only if it does not contain any <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-nodes. Moreover, a polynomial-time algorithm is proposed to detect the set of <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-nodes based on the existence of Quasi <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-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 <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-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.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.