更改

We can define a weaker notion of hypergraph acyclicity,<ref>C. Beeri, [[Ronald Fagin|R. Fagin]], D. Maier, [[Mihalis Yannakakis|M. Yannakakis]], ''On the Desirability of Acyclic Database Schemes''</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>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 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>[[Serge Abiteboul|S. Abiteboul]], [[Richard B. Hull|R. B. Hull]], [[Victor Vianu|V. Vianu]], ''Foundations of Databases''</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

We can define a weaker notion of hypergraph acyclicity,<ref>C. Beeri, [[Ronald Fagin|R. Fagin]], D. Maier, [[Mihalis Yannakakis|M. Yannakakis]], ''On the Desirability of Acyclic Database Schemes''</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>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 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>[[Serge Abiteboul|S. Abiteboul]], [[Richard B. Hull|R. B. Hull]], [[Victor Vianu|V. Vianu]], ''Foundations of Databases''</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

此处，我们可以定义一个减弱的超图无环性的概念<ref>C. Beeri, Ronald Fagin|R. Fagin, D. Maier, Mihalis Yannakakis|M. Yannakakis, ''On the Desirability of Acyclic Database Schemes''</ref>，后来被称为 <math> {\alpha}</math>-无环性  <math> {\alpha}</math> acyclicity。 这个无环性的概念等价于超图是同构的(原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 chordal graph ; 它也等价于通过 GYO 算法 Graham-Yu-Ozsoyoglu Algorithm （也称为格雷厄姆算法 Graham's algorithm) 得到具有可约性的空图<ref>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979</ref>。GYO 算法是一个合流 confluence（抽象重写 abstract rewriting）迭代过程，该算法中使用耳朵 ear的广义定义去除超边 (图论中的耳朵就定义为一条路径，其中除了端点外的点的度数均为 2（端点可以重合），而且删去后不破坏图的连通性)。众所周知， 在数据库理论  database theory 的领域中，如果一个数据库模式 database schema的底层超图是<math> {\alpha}</math>无环的，那么它就具有某些理想的性质。 <ref>Serge Abiteboul, Richard B. Hull, Victor Vianu|V. Vianu, ''Foundations of Databases''</ref> 除此之外,<math> {\alpha}</math>无环性也与一阶逻辑 first-order logic 保护的片段 guarded fragment 的表达能力有关。

此处，我们可以定义一个减弱的超图无环性的概念<ref>C. Beeri, Ronald Fagin|R. Fagin, D. Maier, Mihalis Yannakakis|M. Yannakakis, ''On the Desirability of Acyclic Database Schemes''</ref>，后来被称为 <math> {\alpha}</math>-无环性  <math> {\alpha}</math> acyclicity。 这个无环性的概念等价于超图是同形的 conformal (原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 chordal graph ; 它也等价于通过 GYO 算法 Graham-Yu-Ozsoyoglu Algorithm （也称为格雷厄姆算法 Graham's algorithm) 得到具有可约性的空图<ref>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979</ref>。GYO 算法是一个合流 confluence（抽象重写 abstract rewriting）迭代过程，该算法中使用耳朵 ear的广义定义去除超边 (图论中的耳朵就定义为一条路径，其中除了端点外的点的度数均为 2（端点可以重合），而且删去后不破坏图的连通性)。众所周知， 在数据库理论  database theory 的领域中，如果一个数据库模式 database schema的底层超图是<math> {\alpha}</math>无环的，那么它就具有某些理想的性质。 <ref>Serge Abiteboul, Richard B. Hull, Victor Vianu|V. Vianu, ''Foundations of Databases''</ref> 除此之外,<math> {\alpha}</math>无环性也与一阶逻辑 first-order logic 保护的片段 guarded fragment 的表达能力有关。