更改

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">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</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]].

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">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</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]].

注意到<math> {\alpha}</math>-无环性似乎直觉不相符，即<math> {\alpha}</math>-成环超图添加超边可能使其成为<math> {\alpha}</math>-无环的（例如，添加一条包含超图所有顶点的超边总能其成为<math> {\alpha}</math>-无环的）。 为了克服这个缺点，Ronald Fagin<ref name="fagin1983degrees">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</ref>  定义了更强的 <math> {\beta}</math>-无环性  <math> {\beta}</math>-acylicity 和 <math> {\gamma}</math>无环性  <math> {\gamma}</math>-acylicity 概念。 应当指出：<math> {\gamma}</math>无环超图是推出其所有子超图都是<math> {\alpha}</math>无环的必要条件，这与 Graham 的早期定义<ref name="graham1979universal"/> 等价。  <math> {\gamma}</math>无环性的概念是一个更加严苛的条件，它等价于数据库模式的几个理想性质，并且与Bachman 图 Bachman diagrams有关. <math> {\beta}</math>-无环性 和 <math> {\gamma}</math>无环性  都可以在多项式时间 polynomial time(PTIME)内完成检测。

注意到<math> {\alpha}</math>-无环性似乎与直觉不相符，即<math> {\alpha}</math>-成环超图添加超边可能使其成为<math> {\alpha}</math>-无环的（例如，添加一条包含超图所有顶点的超边总能其成为<math> {\alpha}</math>-无环的）。 为了克服这个缺点，Ronald Fagin<ref name="fagin1983degrees">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</ref>  定义了更强的 <math> {\beta}</math>-无环性  <math> {\beta}</math>-acylicity 和 <math> {\gamma}</math>无环性  <math> {\gamma}</math>-acylicity 概念。 应当指出：<math> {\gamma}</math>无环超图是推出其所有子超图都是<math> {\alpha}</math>无环的必要条件，这与 Graham 的早期定义<ref name="graham1979universal"/> 等价。  <math> {\gamma}</math>无环性的概念是一个更加严苛的条件，它等价于数据库模式的几个理想性质，并且与Bachman 图 Bachman diagrams有关. <math> {\beta}</math>-无环性 和 <math> {\gamma}</math>无环性  都可以在多项式时间 polynomial time(PTIME)内完成检测。

Those four notions of acyclicity are comparable: Berge-acyclicity implies γ-acyclicity which implies β-acyclicity which implies α-acyclicity. However, none of the reverse implications hold, so those four notions are different.<ref name="fagin1983degrees" />

Those four notions of acyclicity are comparable: Berge-acyclicity implies γ-acyclicity which implies β-acyclicity which implies α-acyclicity. However, none of the reverse implications hold, so those four notions are different.<ref name="fagin1983degrees" />