优先图在冲突可串行化判断中的应用

Application of Precedence Graph to Judge Conflict-Serializability

在对数据库同时进行读写的多个事务调度中,为了保证所有事务的并发执行,一个重要条件就是各个事务之间是否可串行化或冲突可串行化。然而,当事务较多较复杂时,要准确判断事务调度是否满足这些条件,难度较大。优先图通过事务内部的本征关系表征各个事务之间的逻辑顺序,根据优先图内有环或无环可准确判断调度是否可串行化或冲突可串行化。

In muhi-tasks database accessing scheduling process, an important rule was given to decide whether or not tasks or conflicts could be serialized so as to guarantee concurrent operation. It is too difficult to strictly conform this rule to find solution when too many tasks with much complex correlations in themselves. The precedence graph was designed to characterize the logic sequences of tasks in such circumstance. Whether the tasks and conflicts be serialized or not could be accurately decided with this method simply by discerning there be or not circulars in the precedence graph.