协同组编辑环境中的数据一致性维护方法

1、协同组编辑环境中的数据一致性维护方法学生：杨江明导师：顾 宁 教授计算机与信息技术系 2022年4月19日2022年4月19日复旦大学信息科学与工程学院2内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院3内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院4背景及问题的提出n协同组编辑是一个抽象的研究模型l传统的协同组编辑。oGroupSketch（Greenberg

2、and Bohnet）、Grove（Ellis, Gibbs, and Rein）、ShrEdit（McGuffin and Olson）、DistEdit（Knister and Prakash）、REDUCE(Sub and Ellis)l单机软件的协同化。oICT(D. Li and R. Li)、CoWord & CoPowerpoint(Xia et al.)、CoAutoCAD(Gu et al.)l基于Web2.0的非实时组编辑。oCDVE 2007(Shen and Sun)2022年4月19日复旦大学信息科学与工程学院5背景及问题的提出n协同组编辑环境下问题l结果的一

3、致性问题。o如果操作是不可交互的，则不同的操作执行顺序会导致不同的结果。l操作的依赖性问题。o需要保证操作的执行条件l操作的意愿维护问题。o假设初始状态为“ABC”。在SR1，O3为Insert“d”,1，即将”d“插入到位置1(即A和B之间)；而在SR3，O1为Insert”e“,2，即将”e“插入到位置2(即B和C之间)。当O1 到达SR1 时，该站点已经被操作O3修改成”AdBC“，直接执行O1会把字符e插入到字符d和B之间，这显然是错误的。l事务的支持性问题。2022年4月19日复旦大学信息科学与工程学院6内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相

4、关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院7数据及操作表示n线性结构l线性结构是多种数据类型的抽象表示。直观上的线性结构包括：字符串，链表等数据结构。但事实上，线性结构维护的是多个对象间的一个全序关系，而这样一种全序关系是广泛存在的。l全序关系的维护是协同环境下一致性维护的基础。n树型结构l一些主流的文档类型需要树型结构的表示。l通过XML可以支持基于关系的操作，是Web应用的需求。2022年4月19日复旦大学信息科学与工程学院8一致性模型n因果关系维护（Causality preservation）：所有操作的执行顺序都按照它们之间的因果关系。对于任

5、意的两个操作O1和O2，如果O1O2，则在所有的站点，操作O1都在操作O2之前执行。n一致性维护（Convergence）：当相同的操作在所有的站点都执行完成之后，所有的数据副本保持一致。n意愿维护（Intention preservation）：任何一个操作在任何站点的执行效果都保持和它产生站点一致。2022年4月19日复旦大学信息科学与工程学院9内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院10回溯思想2022年4月19日复旦大学信息科学与工程学院11线性结构的回溯过程20

6、22年4月19日复旦大学信息科学与工程学院12线性结构的回溯过程n对难题的解决l操作转换方法中TP2条件维护的困难ldOPT难题o假设几个插入操作都是面向相同的位置，操作之间满足因果顺序或者是并发的。仅仅依靠强制规定操作间的优先级是无法保证结果的收敛性的。lFalse-tie难题o假设两个并发的插入操作可能会因为在它们之间一个并发的删除操作，而丢失它们之间的左右位置关系，并且可能得到一个相反的结果。n证明过程l2个操作lN个操作2022年4月19日复旦大学信息科学与工程学院13树型结构的回溯过程2022年4月19日复旦大学信息科学与工程学院14树型结构的回溯过程n已有方法的不足l操作转换方法（

7、Operation Transformation）方法无法支持关系操作。l基于锁和序列化的方法无法满足操作的响应时间和自由度。n证明过程l2个操作lN个操作2022年4月19日复旦大学信息科学与工程学院15内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院16一致性维护的相关问题n操作的历史队列l通过状态向量表，精简操作的历史队列nUndo 操作支持l通过在回溯过程添加计数器，是回溯过程可以考虑Undo操作n支持单站点并发操作的时间戳模型l通过分离考虑操作间关系和操作的执行状态，引

8、入两个时间戳，支持操作的并发执行。n事务操作的支持2022年4月19日复旦大学信息科学与工程学院17事务操作的支持2022年4月19日复旦大学信息科学与工程学院18内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结与展望2022年4月19日复旦大学信息科学与工程学院19线性结构效率分析n线性结构优化，通过调整数据结构，可以优化计数效率n平摊效率l插入操作的开销可以表示为O(hlogn + logn + dh + h + d + m) ，l删除操作的开销为O(hlogn + logn + dh + h + d)l其中h为历史队列长度，

9、n为文档字符数，d为针对一个节点的操作数2022年4月19日复旦大学信息科学与工程学院20树型结构效率分析2022年4月19日复旦大学信息科学与工程学院21原型系统2022年4月19日复旦大学信息科学与工程学院22内容概要n背景及问题的提出n一致性模型n回溯思想与一致性维护方法n一致性维护的相关问题n效率分析与原型系统n总结2022年4月19日复旦大学信息科学与工程学院23总结n本文的工作l基于状态转换的一致性维护方法l一致性维护的四个相关问题l算法的理论分析和实验lCoAutoCAD 演示系统n进一步的工作l关系数据库的协同化l支持动态性的加入、退出l进一步改善操作执行的并发性l处理用户意愿

10、的矛盾2022年4月19日复旦大学信息科学与工程学院24攻读硕士学位期间的科研工作n读硕士期间已发表和已录用的论文l顾宁，杨江明杨江明，张琦炜. 协同组编辑中基于地址空间转换的一致性维护方法. 计算机学报，第30卷，第5期，2007年5月, 763-774页.l杨江明杨江明，张琦炜，顾宁. 数据网格中复制式数据的一致性维护方法. 华中科技大学学报（自然科学版）. Vol.34, Sup I, 2006年9月, 49-52页.lShichao Zhang, Ning Gu, Jiangming Yang. An Norm-driven State Machine Model for CSCW S

11、ystems. Expert Systems With Applications, Volume 31, Issue 4 , November 2006, Pages 800-807.lJiangming Yang, Qiwei Zhang, Ning Gu. A Consistency Maintenance Approach in Replicated Services. In Proceedings of 2006 IEEE international conference on computer and information technology, Seoul, Korea, Sep

12、t 2006.lQiwei Zhang, Jiangming Yang, Ning Gu, Yuwei Zong, Zhigang Ding, Shaohua Zhang. Dynamic Replica Location Service Supporting Data Grid Systems. In Proceedings of 2006 IEEE international conference on computer and information technology, Seoul, Korea, Sept 2006.lShichao Zhang, Jiangming Yang, N

13、ing Gu. GridSM: a Norm-driven State Machine Model of Grid Workflow. In Proceedings of International Conference on CSCWD 2006, Nanjing, China, May, 2006.l杨江明杨江明，顾宁，吴筱媛. 基于地址空间转换方法的Undo操作支持. 通信学报，第27卷，2006年3月，48-56页。2022年4月19日复旦大学信息科学与工程学院25攻读硕士学位期间的科研工作n读硕士期间已发表和已录用的论文lNing Gu, Jiangming Yang, Qiwei

14、Zhang. Consistency maintenance based on the mark & retrace technique in groupware systems. In Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work, Sanibel Island, USA, pages 264-273, Nov 2005.lNing Gu, Jun Xu, Xiaoyuan Wu, Jiangming Yang, and Wei Ye. Ontology b

15、ased semantic conflicts resolution in collaborative editing of design documents. International Journal of Advanced Engineering Informatics (IJAEI), 19(2), 103-111, 2005. lJiangming Yang, Qiwei Zhang, Ning Gu, Genxing Yang, and Zhenyu Liu. The multi-version and single-display strategy in undo scheme.

16、 In Proceedings of the 5th international conference on computer and information technology, pages 290-296, September 2005, Shanghai, China.l张琦炜，杨江明杨江明，顾宁，杨根兴，刘振宇. 数据网格中的动态分布式多入口技术. 计算机科学，第32卷，2005年7月增刊A，127-131页。lJiangming Yang, Ning Gu and Xiaoyuan Wu. A document mark based on method supporting gro

17、up undo. In International Workshop on Collaborative Editing Systems, ACM CSCW2004, November 2004, Chicago, USA.lNing Gu, Jun Xu, Xiaoyuan Wu and Jiangming Yang. A solution to the semantic conflicts in the collaborative editing of design documents. In Proceedings of International Conference on CSCWD

18、2004, Volume II pages 179-185, May 2004, Xiamen, China.lShuo Wang, Feng Jing, Jianmging Yang, Jibo He. Long Query Suggestion List: Prioritized or Organized? In HCI International Conference 2007. Accepted.2022年4月19日复旦大学信息科学与工程学院26攻读硕士学位期间的科研工作n专利及软件著作权l(专利) 顾宁、张世超、徐寅俊、杨江明杨江明. 一种规范驱动的网格工作流描述和验证方法. 专利申请号：200510027785.2, 专利申请日：2005年7月15日, 公开号：CN1719832l(专利) 顾宁、杨江明杨江明、张琦炜、绍斌. 标记回溯的一致性维护方法. 专利申请号：200610025690.1, 专利申请日：2006年4月13日, 公开号：CN1831776l(专利) 顾宁、杨江明杨江明、张琦炜. 面向XML的标记回溯的一致性维护方法. 专利申请号：200610026459.4, 专利申请日：2006年5月11日, 公开号：CN1845076l(计算机软件著作权) 软件名称：网格工作流管理系统软件V1.0