On Quasi Cycles in Hypergraph Databases
Open Access
- 10 August 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 147560-147568
- https://doi.org/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.This publication has 24 references indexed in Scilit:
- Arboricity: An acyclic hypergraph decomposition problem motivated by database theoryDiscrete Applied Mathematics, 2011
- On the notion of cycles in hypergraphsDiscrete Mathematics, 2009
- Query answering exploiting structural propertiesACM SIGMOD Record, 2005
- Hypertree Decompositions and Tractable QueriesJournal of Computer and System Sciences, 2002
- Conjunctive query containment revisitedTheoretical Computer Science, 2000
- On the Complexity of Database QueriesJournal of Computer and System Sciences, 1999
- Semantic database modeling: survey, applications, and research issuesACM Computing Surveys, 1987
- Connections in acyclic hypergraphsTheoretical Computer Science, 1984
- On the Desirability of Acyclic Database SchemesJournal of the ACM, 1983
- Degrees of acyclicity for hypergraphs and relational database schemesJournal of the ACM, 1983