用线图模型在分部式环境中识别数据库模式的四种非环性

Recognizing Four type Acyclic Database Schemes by Using the Line Graph of the Scheme in a Distributed Environment

介绍一个在分部式环境下，用线图模型识别数据库模式的四种常见非环性（即，Ａｌｐｈａ，Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ非环性）的算法ＤＰＲＥ，并证明该算法的最坏消息复杂度为Ｏ（｜Ｅ｜），其中｜Ｅ｜表示数据库中有公共属性的关系对之总数．

We gave a new algorithm for recognizing four type acyclic database schemes(namely: Alpha-,Beta-,Gamma-,Berge-acyclicity) by using the line graph of the scheme in a distributed environment. The algorithm has a worst-case message complexity O(|E|),where |E| is the number of pairs of relations of the database scheme with at least one attribute in common.