On Quasi Cycles in Hypergraph Databases
Published: 10 August 2020
in IEEE Access
IEEE Access pp 1-1; doi:10.1109/access.2020.3015654
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.
Keywords: urban areas / systematics / minimization / Relational databases / query processing / licenses
Scifeed alert for new publicationsNever miss any articles matching your research from any publisher
- Get alerts for new papers matching your research
- Find out the new papers from selected authors
- Updated daily for 49'000+ journals and 6000+ publishers
- Define your Scifeed now
Click here to see the statistics on "IEEE Access" .