Editing Hypergraph (section)

===α-acyclicity===
The definition of Berge-acyclicity might seem to be very restrictive: for instance, if a hypergraph has some pair <math>v \neq v'</math> of vertices and some pair <math>f \neq f'</math> of hyperedges such that <math>v, v' \in f</math> and <math>v, v' \in f'</math>, then it is Berge-cyclic. 

We can define a weaker notion of hypergraph acyclicity,<ref name=database>{{cite journal |first1=C. |last1=Beeri |author-link2=Ronald Fagin |first2=R. |last2=Fagin |first3=D. |last3=Maier |author-link4=Mihalis Yannakakis |first4=M. |last4=Yannakakis |title=On the Desirability of Acyclic Database Schemes |journal=Journal of the ACM |volume=30 |issue=3 |pages=479–513 |year=1983 |doi=10.1145/2402.322389 |s2cid=2418740 |url=http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |access-date=2021-01-03 |archive-date=2021-04-21 |archive-url=https://web.archive.org/web/20210421203326/http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |url-status=live }}</ref> later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being [[chordal graph|chordal]]; it is also equivalent to reducibility to the empty graph through the [[GYO algorithm]]<ref>{{cite journal |first1=C. T. |last1=Yu |first2=M. Z. |last2=Özsoyoğlu |url=https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |title=An algorithm for tree-query membership of a distributed query |journal=Proc. IEEE COMPSAC |pages=306–312 |year=1979 |doi=10.1109/CMPSAC.1979.762509 |access-date=2018-09-02 |archive-date=2018-09-02 |archive-url=https://web.archive.org/web/20180902151638/https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |url-status=live }}</ref><ref name="graham1979universal">{{cite journal |first=M. H. |last=Graham |title=On the universal relation |journal=Technical Report |publisher=University of Toronto |location=Toronto, Ontario, Canada |year=1979 }}</ref> (also known as Graham's algorithm), a [[confluence (abstract rewriting)|confluent]] iterative process which removes hyperedges using a generalized definition of [[ear (graph theory)|ears]]. In the domain of [[database theory]], it is known that a [[database schema]] enjoys certain desirable properties if its underlying hypergraph is α-acyclic.<ref>{{cite book |author-link=Serge Abiteboul |first1=S. |last1=Abiteboul |author-link2=Richard B. Hull |first2=R. B. |last2=Hull |author-link3=Victor Vianu |first3=V. |last3=Vianu |title=Foundations of Databases |publisher=Addison-Wesley |year=1995 |isbn=0-201-53771-0 }}</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

We can test in [[linear time]] if a hypergraph is α-acyclic.<ref>{{cite journal |author-link=Robert Tarjan |first1=R. E. |last1=Tarjan |author-link2=Mihalis Yannakakis |first2=M. |last2=Yannakakis |title=Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs |journal=SIAM Journal on Computing |volume=13 |issue=3 |pages=566–579 |year=1984 |doi=10.1137/0213035 }}</ref>

Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, [[Ronald Fagin]]<ref name="fagin1983degrees">{{cite journal |first=Ronald |last=Fagin |title=Degrees of Acyclicity for Hypergraphs and Relational Database Schemes |journal=Journal of the ACM |year=1983 |volume=30 |issue=3 |pages=514–550 |doi=10.1145/2402.322390 |s2cid=597990 |doi-access=free }}</ref> defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent<ref name="fagin1983degrees" /> to an earlier definition by Graham.<ref name="graham1979universal" /> The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to [[Bachman diagram]]s. Both β-acyclicity and γ-acyclicity can be tested in [[PTIME|polynomial time]].

Those four notions of acyclicity are comparable: γ-acyclicity which implies β-acyclicity which implies α-acyclicity. Moreover, Berge-acyclicity implies all of them. None of the reverse implications hold including the Berge one. In other words, these four notions are different.<ref name="fagin1983degrees" />