留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用地图文档模拟的地图编辑事务模型

何列松 刘海砚 黄利民 吴芳华 魏斌

何列松, 刘海砚, 黄利民, 吴芳华, 魏斌. 利用地图文档模拟的地图编辑事务模型[J]. 武汉大学学报 ● 信息科学版, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
引用本文: 何列松, 刘海砚, 黄利民, 吴芳华, 魏斌. 利用地图文档模拟的地图编辑事务模型[J]. 武汉大学学报 ● 信息科学版, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
HE Liesong, LIU Haiyan, HUANG Limin, WU Fanghua, WEI Bin. A Map Editing Transaction Model Simulated by Map Document Status Change[J]. Geomatics and Information Science of Wuhan University, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
Citation: HE Liesong, LIU Haiyan, HUANG Limin, WU Fanghua, WEI Bin. A Map Editing Transaction Model Simulated by Map Document Status Change[J]. Geomatics and Information Science of Wuhan University, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150

利用地图文档模拟的地图编辑事务模型

doi: 10.13203/j.whugis20190150
基金项目: 

国家自然科学基金 41301527

国家973计划 613317

详细信息
    作者简介:

    何列松,博士,助理研究员,主要研究方向为地图制图处理的理论与方法研究。bealiouve@163.com

    通讯作者: 刘海砚,博士,教授,博士生导师。liu2000@vip.sina.com
  • 中图分类号: P285

A Map Editing Transaction Model Simulated by Map Document Status Change

Funds: 

The National Natural Science Foundation of China 41301527

the National Basic Research Program of China 613317

More Information
    Author Bio:

    HE Liesong, PhD, assistant researcher, specializes in theories and methods of cartography processing. E-mail: bealiouve@163.com

    Corresponding author: LIU Haiyan, PhD, professor. E-mail: liu2000@vip.sina.com
  • 摘要: 随着数字地图与地理信息服务的需求增长,快速高效的地图制图和地理信息更新技术需求迫切,协同制图是提高地图制图工作效率、快速更新地图和地理空间数据库的有效方法。针对基于空间数据库的地图编辑事务执行效率低、并发控制复杂、地图数据一致性维护困难的问题,提出一种利用地图文档模拟的地图编辑事务模型,它支持空间坐标、属性、几何、关系等定义,用地图文档状态变化描述地图编辑事务,利用地图文档备份数据和变化数据来存储组织地图编辑事务,为协同制图提供了一种高效事务处理手段。试验表明,该模型使地图编辑过程不受数据库管理系统(database management system,DBMS)执行效率的限制,且严格保持了地图编辑事务的原子性、一致性、隔离性、持久性(atomicity, consistency, isolation, durability,ACID)特性,很好地支持了“你见即我见”的协同制图用户视图同步显示,相比基于DBMS的地图数据库具备更高的执行效率和事务管理能力,可用于地理空间数据库和制图数据库快速更新。
  • 图  1  单备份模型地图文档状态

    Figure  1.  Map Document Status of Single Backup Model

    图  2  静态多备份模型地图文档状态

    Figure  2.  Map Document Status of Static Multi-backup Model

    图  3  回退/重做地图编辑内部调用流程

    Figure  3.  Internal Call Process of Undo/Redo Map Editing

    图  4  地图编辑事务列表管理

    Figure  4.  Transactions List Management of Map Editing

    图  5  地图文档模型

    Figure  5.  Map Document Model

    图  6  临时单备份模型的多事务运行效率

    Figure  6.  Multi-transaction Operation Efficiency of Temporary Single Backup Model

    图  7  静态多备份模型的多事务运行效率

    Figure  7.  Multi-transaction Operation Efficiency of Static Multi-backup Model

    图  8  局域网协同制图案例网络结构

    Figure  8.  Net Structure of LAN-Based Collaborative Mapping Case

    图  9  6个用户协同制图的地图视图

    Figure  9.  Six Users' Map Views of Collaborative Mapping

    表  1  对象类型编码

    Table  1.   Encoding of Object Types

    对象类型 编码
    文档地图 001
    图层列表 002
    图层 003
    列表要素 004
    要素 005
    下载: 导出CSV

    表  2  操作类型编码

    Table  2.   Encoding of Operation Types

    操作类型 编码 操作类型 编码
    创建 001 移动 008
    删除 002 合并 009
    修改名称 003 拆分 010
    修改值 004 修改属性 011
    装载数据 005 修改坐标 012
    卸载数据 006 修改关系 013
    调整顺序 007
    下载: 导出CSV

    表  3  地理要素编辑事务并发处理规则

    Table  3.   Rules for Geographic Elements Edit Transactions Concurrent Processing

    后三元组L 前三元组F
    (005, ID, 008) (005, ID, 009) (005, ID, 010) (005, ID, 011) (005, ID, 012) (005, ID, 013)
    (005, ID, 008) 优化 丢弃L 丢弃L - 优化 丢弃L
    (005, ID, 009) - 丢弃L 丢弃L 合并 丢弃L 丢弃L
    (005, ID, 010) 合并 丢弃L 丢弃L - - -
    (005, ID, 011) - - - 合并 - -
    (005, ID, 012) 优化 - - - 合并 -
    (005, ID, 013) - - - - - -
    下载: 导出CSV
  • [1] 杨春成, 何列松, 周校东, 等. 基于VMP与SEH的地图编辑回退/重做机制[J]. 测绘科学技术学报, 2013, 30(2): 168-171 doi:  10.3969/j.issn.1673-6338.2013.02.014

    Yang Chuncheng, He Liesong, Zhou Xiaodong, et al. A Redo/Undo Mechanism on Map Editing Based on VMP and SEH[J]. Journal of Geomatics Science and Technology, 2013, 30(2): 168-171 doi:  10.3969/j.issn.1673-6338.2013.02.014
    [2] 郭庆胜, 黄鹤声, 王琳, 等. 顾及制图规则的地图多要素协同移位方法[J]. 武汉大学学报·信息科学版, 2018, 43(5): 726-731 doi:  10.13203/j.whugis20160362

    Guo Qingsheng, Huang Hesheng, Wang Lin, et al. Method on Collaborative Displacement of Map Features Considering with Cartographic Rules[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 726-731 doi:  10.13203/j.whugis20160362
    [3] 上官博屹, 刘威, 乐鹏, 等. 一种面向空间信息网络的星地协同计算迁移方法[J]. 武汉大学学报·信息科学版, 2019, 44(3): 459-466 doi:  10.13203/j.whugis20170269

    Shangguan Boyi, Liu Wei, Yue Peng, et al. An Approach of Spatial Information Network Oriented Satellite-Ground Collaborative Computing Migration[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 459-466 doi:  10.13203/j.whugis20170269
    [4] 徐永红, 徐颖. 面向长事务的基础地理数据库建设[J]. 地理空间信息, 2006, 4(5): 66-68 doi:  10.3969/j.issn.1672-4623.2006.05.025

    Xu Yonghong, Xu Ying. Construction of Fundamental Geographic Database Based on Surveying and Mapping[J]. Geospatial Information, 2006, 4(5): 66-68 doi:  10.3969/j.issn.1672-4623.2006.05.025
    [5] 吴信才. 面向网络的新一代地理信息系统[M]. 北京: 科学出版社, 2009

    Wu Xincai. A New Generation of Network-Oriented Geographic Information System[M]. Beijing: Science Press, 2009
    [6] 唐飞龙, 李明禄, 曹健. 一个Web服务事务处理模型: 结构、算法和事务补偿[J]. 电子学报, 2003, 31(z1): 2 074-2 078 doi:  10.3321/j.issn:0372-2112.2003.z1.030

    Tang Feilong, Li Minglu, Cao Jian. A Transaction Model for Web Services: Architecture, Algorithms and Transaction Compensation[J]. Acta Electronica Sinica, 2003, 31(z1): 2 074-2 078 doi:  10.3321/j.issn:0372-2112.2003.z1.030
    [7] 胡秋翔, 崇殿兵, 毕思斯. 基于锁定机制的电网GIS多用户协同编辑研究[J]. 计算机系统应用, 2018, 27(4): 237-242 https://www.cnki.com.cn/Article/CJFDTOTAL-XTYY201804038.htm

    Hu Qiuxiang, Chong Dianbing, Bi Sisi. Multi-User Cooperative Editing of Power Grid GIS Based on Locking Mechanism[J]. Computer Systems & App-lications, 2018, 27(4): 237-242 https://www.cnki.com.cn/Article/CJFDTOTAL-XTYY201804038.htm
    [8] 吴娟. 地理要素的并发编辑研究[D]. 南京: 南京师范大学, 2008

    Wu Juan. Research on the Compilation of Geographical Elements[D]. Nanjing: Nanjing Normal University, 2008
    [9] 陈波, 周顺平, 万波, 等. GIS中长事务模型[J]. 地球科学, 2006, 31(5): 605-608 doi:  10.3321/j.issn:1000-2383.2006.05.005

    Chen Bo, Zhou Shunping, Wan Bo, et al. Long Transactions in GIS[J]. Earth Science, 2006, 31(5): 605-608 doi:  10.3321/j.issn:1000-2383.2006.05.005
    [10] 曹双, 刘琳岚, 张恒锋. 一种多步流程回退方法的研究与实现[J]. 计算机工程, 2010, 36(21): 67-70 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC201021025.htm

    Cao Shuang, Liu Linlan, Zhang Hengfeng. Research and Implementation of Multi-Step Process Rollback Method[J]. Computer Engineering, 2010, 36(21): 67-70 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC201021025.htm
    [11] 刘云华, 何苗, 罗年猛. CAX系统中智能Undo/Redo操作的研究[J]. 计算机工程与应用, 2012, 48(4): 61-64 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201204021.htm

    Liu Yunhua, He Miao, Luo Nianmeng. Research of Undo/Redo Operations in CAX Systems[J]. Computer Engineering and Applications, 2012, 48(4): 61-64 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201204021.htm
    [12] 刘涛, 程耀东, 杨树文, 等. 基于工作流的协同专题制图[J]. 测绘与空间地理信息, 2011, 34(1): 18-21 https://www.cnki.com.cn/Article/CJFDTOTAL-DBCH201101006.htm

    Liu Tao, Cheng Yaodong, Yang Shuwen, et al. Cooperative Thematic Mapping Based on Workflow Model[J]. Geomatics & Spatial Information Technology, 2011, 34(1): 18-21 https://www.cnki.com.cn/Article/CJFDTOTAL-DBCH201101006.htm
    [13] 王华敏, 沈志东. GIS工作流系统的长事务处理研究[J]. 测绘地理信息, 2005, 30(3): 23-24 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXG200503011.htm

    Wang Huamin, Shen Zhidong. Long Transactional Processing of GIS Workflow System[J]. Journal of Geomatics, 2005, 30(3): 23-24 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXG200503011.htm
    [14] 张平. 基于GIS的空间信息多级网格数据协同更新管理系统研究[J]. 测绘地理信息, 2018, 43(4): 95-100 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXG201804025.htm

    Zhang Ping. Research on Collaborative Updating System of Spatial Information Multi-Grids Based on GIS[J]. Journal of Geomatics, 2018, 43(4): 95-100 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXG201804025.htm
    [15] 吴劲雄. 基于Web的多视图实时协同GIS研究与实现[D]. 徐州: 中国矿业大学, 2018

    Wu Jinxiong. Research on Web-Based Multi-View Real-Time Cooperative GIS[D]. Xuzhou: China University of Mining and Technology, 2018
  • [1] 李雅彦, 杜清运, 蔡忠亮, 张磊, 张铭晓.  一种采用PostScript成像模型的高质量地图制图方法 . 武汉大学学报 ● 信息科学版, 2018, 43(3): 379-384. doi: 10.13203/j.whugis20150139
    [2] 徐丙立, 饶毅, 陈宇婷, 游兰, 林珲.  使用角色构建虚拟地理环境群体协同方法 . 武汉大学学报 ● 信息科学版, 2018, 43(10): 1580-1587. doi: 10.13203/j.whugis20160499
    [3] 郭庆胜, 黄鹤声, 王琳, 刘远刚.  顾及制图规则的地图多要素协同移位方法 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 726-731. doi: 10.13203/j.whugis20160362
    [4] 曾兴国, 杜清运, 任 福.  一种采用mashup的网络地图多变量制图方法 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1215-1219. doi: 10.13203/j .whu g is20130468
    [5] 张珣, 钟耳顺, 张小虎, 王少华, 李绍俊.  一种尺度效应指数修正的格网数据示意地图制图算法 . 武汉大学学报 ● 信息科学版, 2015, 40(8): 1100-1104. doi: 10.13203/j.whugis20130370
    [6] 曾兴国, 任福, 杜清运, 唐岭军.  公众参与式地图制图服务的设计与实现 . 武汉大学学报 ● 信息科学版, 2013, 38(8): 950-953.
    [7] 车森, 孙群, 刘海砚.  参数控制的地图符号编辑器设计 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1326-1329.
    [8] 王唤良, 朱建军.  交互式地图绘制与SVG格式文档的生成 . 武汉大学学报 ● 信息科学版, 2011, 36(8): 995-998.
    [9] 杨勇, 李霖, 王红, 朱海红.  基于国家基础地理信息数据的地图制图系统 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 261-264.
    [10] 李文航, 龚建华, 周洁萍.  协同虚拟地理教学环境的设计与实现 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 289-292.
    [11] 文航, 龚建华, 张利辉, 周洁萍.  面向移动的协同虚拟地理研讨室 . 武汉大学学报 ● 信息科学版, 2007, 32(9): 817-820.
    [12] 钟业勋.  模拟与虚拟地图符号及地理虚拟空间的数学定义 . 武汉大学学报 ● 信息科学版, 2005, 30(6): 557-559.
    [13] 李占元, 钟业勋.  地图编绘的布尔代数运算原理及制图综合算子数学模 . 武汉大学学报 ● 信息科学版, 2005, 30(5): 431-434.
    [14] 李雯静, 毋河海.  地图目标在制图综合中的分形衰减机理研究 . 武汉大学学报 ● 信息科学版, 2005, 30(4): 309-312.
    [15] 张保钢.  图形编辑软件的优化设计 . 武汉大学学报 ● 信息科学版, 1995, 20(2): 135-140.
    [16] 钟业勋, 胡毓钜.  地图模糊矩阵模型与制图术语表述数学化研究 . 武汉大学学报 ● 信息科学版, 1993, 18(4): 1-12.
    [17] 何宗宜.  视错觉在地图制图中应用的研究 . 武汉大学学报 ● 信息科学版, 1991, 16(3): 22-30.
    [18] 张克权, 祝国瑞.  试论地图制图学的理论体系 . 武汉大学学报 ● 信息科学版, 1990, 15(2): 28-33.
    [19] 冯可君.  模式识别之重心法则及其在地图制图中运用一例 . 武汉大学学报 ● 信息科学版, 1989, 14(1): 89-95.
    [20] 黄伟.  三维地图的机助制图试验 . 武汉大学学报 ● 信息科学版, 1982, 7(1): 91-100.
  • 加载中
图(9) / 表(3)
计量
  • 文章访问数:  365
  • HTML全文浏览量:  116
  • PDF下载量:  37
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-05-08
  • 刊出日期:  2021-04-05

利用地图文档模拟的地图编辑事务模型

doi: 10.13203/j.whugis20190150
    基金项目:

    国家自然科学基金 41301527

    国家973计划 613317

    作者简介:

    何列松,博士,助理研究员,主要研究方向为地图制图处理的理论与方法研究。bealiouve@163.com

    通讯作者: 刘海砚,博士,教授,博士生导师。liu2000@vip.sina.com
  • 中图分类号: P285

摘要: 随着数字地图与地理信息服务的需求增长,快速高效的地图制图和地理信息更新技术需求迫切,协同制图是提高地图制图工作效率、快速更新地图和地理空间数据库的有效方法。针对基于空间数据库的地图编辑事务执行效率低、并发控制复杂、地图数据一致性维护困难的问题,提出一种利用地图文档模拟的地图编辑事务模型,它支持空间坐标、属性、几何、关系等定义,用地图文档状态变化描述地图编辑事务,利用地图文档备份数据和变化数据来存储组织地图编辑事务,为协同制图提供了一种高效事务处理手段。试验表明,该模型使地图编辑过程不受数据库管理系统(database management system,DBMS)执行效率的限制,且严格保持了地图编辑事务的原子性、一致性、隔离性、持久性(atomicity, consistency, isolation, durability,ACID)特性,很好地支持了“你见即我见”的协同制图用户视图同步显示,相比基于DBMS的地图数据库具备更高的执行效率和事务管理能力,可用于地理空间数据库和制图数据库快速更新。

English Abstract

何列松, 刘海砚, 黄利民, 吴芳华, 魏斌. 利用地图文档模拟的地图编辑事务模型[J]. 武汉大学学报 ● 信息科学版, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
引用本文: 何列松, 刘海砚, 黄利民, 吴芳华, 魏斌. 利用地图文档模拟的地图编辑事务模型[J]. 武汉大学学报 ● 信息科学版, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
HE Liesong, LIU Haiyan, HUANG Limin, WU Fanghua, WEI Bin. A Map Editing Transaction Model Simulated by Map Document Status Change[J]. Geomatics and Information Science of Wuhan University, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
Citation: HE Liesong, LIU Haiyan, HUANG Limin, WU Fanghua, WEI Bin. A Map Editing Transaction Model Simulated by Map Document Status Change[J]. Geomatics and Information Science of Wuhan University, 2021, 46(4): 561-569. doi: 10.13203/j.whugis20190150
  • 移动互联网时代,人们对数字地图与地理信息服务的需求迅猛增长。地理环境随人类活动不断发生变化,用户对地图现势性要求越来越高。地图制图从数据获取到地图设计与编制,其中大部分时间都是在进行地图编辑处理工作,地图编辑成为繁重的、反复的“数字化劳动”[1]。协同制图是提高地图制图工作效率,快速更新地图和地理空间数据库的有效方法。基于地理空间数据库的地图协同制图与长事务处理,可满足地图协同编辑和地理空间数据库一致性的需要[2-3]。但“执行”“提交”“回滚”等操作均由数据库管理系统(database management system,DBMS)代理完成,这些操作并不是在瞬间完成的,短事务最长可能需要数秒才能执行完毕,长事务[4-5]结构更为复杂,可能包含多个子事务、嵌套事务或者循环事务,它的执行时间等于所有原子事务执行时间之和加上长事务失败后进行事务补偿[6]的时间,可能长达几天或者数周。原因在于将含有复杂关系的地理要素变更,交由不善于空间数据管理的DBMS来实现,尤其是事务锁定[7]和冲突消解[8]过程的代价太大,无法有效满足地图快速更新和协同制图等方面的需求。即使采用多版本模型[9]的网络制图,其后台数据库执行多版本更新的过程也缓慢而复杂。因此DBMS的事务执行效率成为制约地图协同编辑效率的瓶颈。事实上,由于计算机中任何状态的变化都可描述为事务,地图文档中地理对象状态变化也可以描述为编辑事务,而基于文档的状态改变可以由程序迅速完成。单个地图文档的数据量通常不大,基于共享地图文档的快速事务操作是可能的。通过程序来模拟地图编辑长事务,不仅可以获得很高的效率,而且这种程序模拟本身就有更自由的操控性,没有诸如数据库事务对数据定义语言(data definition language,DDL)操作的限制。

    真正具备原子性、一致性、隔离性、持久性(atomicity,consistency,isolation,durability,ACID)的事务模拟实现困难。基于过程式的编程方法或者大型开发语言开放的类库直接模拟地图编辑事务,通常存在下列不足:(1)需要使用大量类库,地图编辑操作自由性受限;(2)当在地图文档中删除某些对象时,它们仍需保留在内存中,既增加了开销,也约束了行为[10-11];(3)某些方法需要重复复制整个地图文档对象,以内存占用来换取操作简化;(4)工作流方式[12-13]不适合地图编辑业务。为克服上述不足,杨春成等[1]提出了基于虚拟内存保护(virtual memory protection,VMP)与结构化异常处理(structured exception handing,SEH)的地图编辑回退/重做机制,即一种“备份数据”+“状态变化数据增量”计算任意时刻文档状态的方法,可确保地图编辑事务的ACID特性并支持地图编辑事务高效执行,但对地图编辑操作类型没有明确分类,且地图文档内存的管理是单备份的。因此,本文在该方法的基础上,针对地图数据的特点,构建支持地图编辑事务的地图文档相关模型,改进基于单备份的地图编辑事务数据组织方式。研究支持ACID特性的高效地图编辑事务模型,不仅在降低地图制图工作成本和保持数据一致性上具有重要意义,还为分布式空间数据网络协同更新提供了技术手段与方法[14]

    • 由于异或(⊕)操作可以快速得到地图文档前后状态,事务的回退/重做可快速完成。显然存储变化数据D比存储地图文档状态数据S显著节省存储空间,因此本文采用地图文档状态备份与状态变化增量备份的方式存储并组织地图编辑事务。其中变化数据D可采用无损压缩方法进一步压缩存储空间。地图编辑操作过程中任一步骤完成时刻的文档状态及其变化可描述为:

      $$ \left\{ {\begin{array}{*{20}{l}} {{D_1} = {S_1} \oplus {S_0}, {S_0} = {S_1} \oplus {D_1}, {S_1} = {S_0} \oplus {D_1}}\\ {{D_2} = {S_2} \oplus {S_1}, {S_1} = {S_2} \oplus {D_2}, {S_2} = {S_1} \oplus {D_2}}\\ {\;\;\;\;\;\;\;\;\;\; \vdots }\\ {{D_n} = {S_n} \oplus {S_{n - 1}}, {S_{n - 1}} = {S_n} \oplus {D_n}, {S_n} = {S_{n - 1}} \oplus {D_n}} \end{array}} \right. $$ (1)

      若当前状态位于Si,事务管理器管理了从D1Dn的全部变化,则恢复到之前(回退,undo)文档某个状态Su的表达式为:

      $$ {S_u} = {S_i} \oplus {D_i} \oplus {D_{i - 1}} \cdots {D_{u + 1}}\left( {0 < u < i} \right) $$ (2)

      恢复到之后(重做,redo)文档某个状态Sr的表达式为:

      $$ {S_r} = {S_i} \oplus {D_{i + 1}} \oplus \cdots {D_r}\left( {i < r < n} \right) $$ (3)

      支持上述事务组织模式的地图文档模型简称为单备份模型。单备份模型备份一个当前地图文档状态Sin个状态变化(D1Dn),有效节约了存储资源(如图 1所示)。但因该单备份在每次单步骤事务执行(回退或者重做)中都要重新备份新数据和清除旧数据,它并不是一个静态备份,仅仅是一个临时备份,因而长距离的检索变化状态和重构状态过程计算时间长,简称其为临时单备份模型。若能增加地图文档状态的静态备份(或称永久备份),则能够显著减小起始状态和目标状态的距离,缩短检索变化状态和重构状态计算时间。因此,可根据管理事务数量的能力,确定地图文档状态备份的事务间隔,以确保存储资源和计算资源的平衡使用,本文把这种基于多个地图文档状态静态备份的模式简称为静态多备份模型(如图 2所示)。

      图  1  单备份模型地图文档状态

      Figure 1.  Map Document Status of Single Backup Model

      图  2  静态多备份模型地图文档状态

      Figure 2.  Map Document Status of Static Multi-backup Model

      静态多备份模型假定地图文档在每k个状态变化后存储一个永久备份Sj·k,为与临时单备份模型表示区别,将基于永久备份Sj·k产生的变化数据用F表示,则Fi=SiSj·k,其中jki < (j+1)k。共存储备份m+1个,其中0≤jm,其地图文档状态图如图 2所示。

      f=[u/k],Su前第一个永久备份为Sf·k,则恢复到之前(回退,undo)文档某个状态Su的表达式为:

      $$ {S_u} = {S_{f \cdot k}} \oplus {F_u} $$ (4)

      p=[r/k],Sr前第一个永久备份为Sp·k,则恢复到之后(重做,redo)文档某个状态Sr的表达式为:

      $$ {S_r} = {S_{p \cdot k}} \oplus {F_r} $$ (5)
    • 用户首先创建一个地图文档,在计算机内存或虚拟内存中为新建的地图文档开辟一定大小的存储空间。在进行地图编辑修改处理时需要开启一个事务,事务负责地图编辑修改开始与结束的周期。如果一个新地图编辑事务被提交,在内存中备份这个事务,只存储地图文档中数据改动的增量,而且由压缩算法进行压缩;如果新事务没有被取消,则直接返回,如图 3所示。

      图  3  回退/重做地图编辑内部调用流程

      Figure 3.  Internal Call Process of Undo/Redo Map Editing

    • 1)虚拟内存存储

      目的在于快速探测变化和存储管理变化数据。使用Windows的虚拟内存函数可在虚拟内存空间中分配、保护和重新分配地址空间。当把需要控制的虚拟内存的操作权限设置为“只读”时,任何试图对该块内存进行“写”操作都将产生存取异常事件,并传递给相应的异常过滤器处理,该机制可有效探测地图文档状态变化[1]。使用异或(⊕)操作得到变化数据后,压缩存储。

      2)普通内存存储

      目的在于更自由地控制事务管理。相比虚拟内存,直接使用计算机内存可克服以下缺点:不同操作系统平台需配置虚拟内存;地图文档数据装载过程因数据量变化较大必须作为事务进行管理;对地图文档模型中变长对象支持,需要定义复杂类型及其增加或释放内存的操作方法。

    • 地理编辑事务表如图 4所示。使用回退列表和重做列表双列表对地图编辑事务进行管理,见图 4(a),两个均采用先进后出的列表数据结构,分别使用push_back和pop_back函数将事务加入列表末尾或者从末尾移出。其中回退列表存储事务的顺序为距离当前状态越靠近的事务,在列表越靠末端;重做列表存储事务的顺序为距离当前状态越靠近的事务,在列表越靠末端。当用户调用回退操作时,回退列表最后一个事务被移出回退列表,置于重做列表的最末端;当调用重做操作时,重做列表最后一个事务被移出,置于回退列表的最末端。为提高运算速度并简化管理,双列表管理事务可改造为单列表管理,见图 4(b)

      图  4  地图编辑事务列表管理

      Figure 4.  Transactions List Management of Map Editing

      用户不论调用回退操作还是重做操作,仅需重新标记当前状态处于事务列表的具体位置序号,处于当前状态之前的事务属于回退段,处于当前状态之后的事务属于重做段。由于临时单备份模型长距离回退/重做事务时,需要每个状态依次重构,宜采用双列表管理事务;而静态多备份模型任意距离回退/重做事务时,直接基于某个备份重构一次,更适宜采用单列表管理事务,以避免多步骤回退/重做时双列表重新排序的运算。

    • 地图编辑根据操作对象的不同,可分为地理要素编辑、符号图形编辑、文字注记编辑等,以地理要素编辑为例,支持地理要素编辑操作的地图文档模型如图 5所示。

      图  5  地图文档模型

      Figure 5.  Map Document Model

      地图文档通常包含一个图层列表,用来管理地理图层;图层包含要素列表,用来管理地理要素;要素包含属性列表、坐标串和关系列表。属性列表中包含了名称、等级等不同的属性值,坐标串中存储了要素的地理坐标值,关系列表中管理了要素与其他要素的各种关系,尤其是制图关系在地图编辑中不可或缺。在存储层,若基于虚拟内存存储地图文档状态及其变化数据,则该地图文档模型的定义略为复杂。

    • 基于虚拟内存的地图文档模型变量定义通常使用以下数据类型:

      1)定长基本数据类型、结构体、静态数组。这些类型定义的变量在虚拟内存中所需的大小是固定的,当地图文档申请完自己的内存空间后,它占用了文档内部固定长度的虚拟内存空间,而且所占内存的位置也是固定的。因此在执行地图文档的编辑事务时,虚拟内存中存储的值被更新。例如属性Atrribute、二维点Point2D的定义如下:

      class Attribute

      {char m_cName[128]; int m_nType; byte m_bVal[256]; }

      class Point2D

      {double x; double y; }

      2)动态申请内存数组、类。若将它们作为成员变量定义在地图文档中,地图文档只能为它们申请指向它们指针地址的虚拟内存大小,在文档虚拟内存的某个固定位置上只存储了它们的指针地址,在执行地图事务操作时,它们的地址被更改,而不是它们指向的值被更改,因此,地图文档本身不能管理和操作它们的值。

    • 地图文档中经常会遇到动态加载地图数据,为了解决虚拟内存难以存储和操作变长变量的问题,地图文档的定义必须符合下列情形:(1)内部变量改为§2.1中的类型1);(2)内部变量中存储的是值而不是地址;(3)内部变量内存动态扩展必须在文档的虚拟内存上进行。因此用C++语言增加定义数据类型如下:

      1)对象串类型MmgStlString。其定义如下:

      template < class _E,class_Tr = char_traits < _E>,

      class _A = SPo_Allocator < _E> >

      class MmgStlString:public basic_string < _E,_Tr,_A>

      该类型定义的变量在动态增加元素时调用它的append(_A element)函数。它的动态申请虚拟内存的过程在形参转实参的过程中由SPo_Allocator的构造函数完成,而SPo_Allocator的构造函数确保了虚拟内存是在MmgStlString对象所在内存区上扩展而来。

      2)字符串类型MmgString。其定义如下:

      typedef MmgStlString < char> MmgString

      该类型是用char定义的MmgStlString的一种特殊类型。

      3)链表MmgVector。其定义如下:

      template < class _Ty,class _A = SPo_Allocator < _Ty> > class MmgVector:public vector < _Ty,_A>

      该类型定义的变量在动态增加元素时调用push_back(_A element)函数,其动态申请虚拟内存的过程同样是在形参转实参的过程中由SPo_Allocator的构造函数完成,确保虚拟内存是在MmgVector对象所在内存区上扩展而来。

      扩展的虚拟内存直到地图文档最后销毁时才被释放,如果在中间某个时刻被释放,则地图编辑事务操作更新数据时会导致内存不足而出现异常。利用SPo_Allocator构造函数实现了虚拟内存自动扩展的优点,极大简化了程序设计。地图文档虚拟内存只在文档保存后并调用销毁文档内存时才能从系统资源中释放。例如,层列表LayerList和坐标串CoordinateString的定义如下:

      class LayerList

      {MmgVector < Layer> m_vLayers;…}

      class CoordinateString

      {MmgStlString < Point2D> m_Cds;…}

      根据上述数据类型定义可知,图 5地图文档模型中虚线对象为字节大小可扩的对象,实线对象为固定字节大小的对象。

    • 为了区分编辑事务类型和标识编辑事务操作的对象,需要对事务类型和地理对象进行编码。因此,地图编辑事务需包含一个基本的事务三元组(对象类型码,对象ID,事务类型码),即Tu(oType,oID,tType)。为了标识地图编辑事务操作的对象及其层次关系,需要对地图文档内部对象分类编码。对象定义粒度大小取决于编辑事务操作对象的粒度大小(如果粒度定位于要素,则事务仅能在要素以上操作,若粒度定位于每个属性、坐标和关系,则事务操作对象更具体)。地图文档状态和地图编辑事务三元组模型结合,使得地图编辑事务不仅能在整个文档层面进行操作,也能在地理实体对象、图层等更小粒度进行事务操控。本文制定了地图编辑事务的对象类型编码表(如表 1所示)和操作类型编码表(如表 2所示),地图编辑中涉及的事务类型构成的三元组列表如表 3所示(可扩展)。

      表 1  对象类型编码

      Table 1.  Encoding of Object Types

      对象类型 编码
      文档地图 001
      图层列表 002
      图层 003
      列表要素 004
      要素 005

      表 2  操作类型编码

      Table 2.  Encoding of Operation Types

      操作类型 编码 操作类型 编码
      创建 001 移动 008
      删除 002 合并 009
      修改名称 003 拆分 010
      修改值 004 修改属性 011
      装载数据 005 修改坐标 012
      卸载数据 006 修改关系 013
      调整顺序 007

      表 3  地理要素编辑事务并发处理规则

      Table 3.  Rules for Geographic Elements Edit Transactions Concurrent Processing

      后三元组L 前三元组F
      (005, ID, 008) (005, ID, 009) (005, ID, 010) (005, ID, 011) (005, ID, 012) (005, ID, 013)
      (005, ID, 008) 优化 丢弃L 丢弃L - 优化 丢弃L
      (005, ID, 009) - 丢弃L 丢弃L 合并 丢弃L 丢弃L
      (005, ID, 010) 合并 丢弃L 丢弃L - - -
      (005, ID, 011) - - - 合并 - -
      (005, ID, 012) 优化 - - - 合并 -
      (005, ID, 013) - - - - - -

      使用三元组地图编码模型不仅可以记录事务中有关地图编辑对象及其操作信息,还能支持临近事务的简化、合并等计算。尤其是面向协同制图时,来自不同客户端的事务请求在服务端于不同时刻接收,自动进入一个串行化的事务三元组列表,而并发处理仅需考虑接收时刻非常接近的堆砌事务。当顾及此类地图编辑事务并发处理时,协同制图的地图编辑事务处理可采用基于三元组模型的丢弃、合并及优化流程。

    • 利用地图文档模拟的地图编辑事务模型,在普通配置的计算机中存储地图文档及其变化数据,使用6幅地形图数据,数据量分别为3.595 MB、4.316 MB、8.911 MB、9.406 MB、11.578 MB、19.288 MB,比例尺分别为1∶1万、1∶1万、1∶5万、1∶5万、1∶5万、1∶5万,采用临时单备份模型和静态多备份模型分别测试了回退和重做1万个、5万个、10万个、20万个地理要素坐标位置移动的编辑事务。测试分单备份模型和静态多备份模型两组,每组用6幅地图数据分别试验,每幅地图数据条件下一次性回退和重做1万个、5万个、10万个、20万个事务共8次测试,每次测试先随机选择一个面状居民地要素,每个事务利用随机函数产生在图幅范围内XY方向移动的有效距离,并将该要素的全部坐标点位置按照移动距离移动到图幅范围内有效位置,用系统的时钟函数clock()计算所用平均时间,得到的运行效率如图 6图 7所示。

      图  6  临时单备份模型的多事务运行效率

      Figure 6.  Multi-transaction Operation Efficiency of Temporary Single Backup Model

      图  7  静态多备份模型的多事务运行效率

      Figure 7.  Multi-transaction Operation Efficiency of Static Multi-backup Model

      图 6是临时单备份模型使用虚拟内存运行的测试结果,虽然在运行少量事务时效率较高,但随着管理事务数量的增大,运行效率显著降低。图 7是静态多备份模型在普通内存中运行的测试结果(不计内存申请时间),其中地图文档备份间隔为N/10个事务(N表示管理最大事务数量的限值),虽然在运行大量事务时效率稍不稳定,但总体运行效率不会降低,不会因为管理事务数量庞大而显著降低性能。将试验的地图编辑事务类型替换为随机修改要素属性值、随机移动要素单点坐标等,试验结果相当。

    • 利用本文提出的静态多备份地图编辑事务模型构建协同制图试验软件,在1 000 MB局域网环境中的6台工作站上启动该软件,并建立协同制图工作组。首先搭建协同制图工作环境,在用户1上打开地图样例数据,地图文件装载完成后,显示在用户1的试验软件窗口中,此时用户1将本机作为地图编辑任务启动的服务器,其他5个用户在各自打开的试验软件中,通过填写用户1上的IP地址和端口信息关联到用户1,作为协同制图的客户端,系统自动更新窗口视图,显示与用户1相同的地图(用户1本身也作为一个编辑客户端),建立的协同制图网络结构如图 8所示。协同工作环境搭建完成后,6个工作站用户开始分别基于各自的地图窗口及编辑工具,开始具体编辑地图的操作(增加、删除、移动地图符号等)。图 9表示用户1在“水峪村”注记附近移动一个居民地要素后,6个协同用户的地图视图。

      图  8  局域网协同制图案例网络结构

      Figure 8.  Net Structure of LAN-Based Collaborative Mapping Case

      图  9  6个用户协同制图的地图视图

      Figure 9.  Six Users' Map Views of Collaborative Mapping

      每个地图编辑事务都按时间序列被发送到用户1的服务器中进行集中组织和管理。此时,只有作为服务器端的用户1可以管理并操作全部地图编辑事务。当所有地图编辑工作完成后,服务器端(用户1)管理的地图文档就是协同制图工作组的最终地图编辑成果。该试验案例同样适用于临时单备份模型,本文模型的特点主要包括:(1)地图文档数据和地图编辑事务数据缓存于用户1的磁盘中,因此每个用户地图编辑事务提交后执行效率较基于数据库(例如Oracle 11g)的地图编辑事务执行效率更高;(2)依托事务提交和执行效率上的优势,6个用户的全部地图编辑事务在用户1的服务器端进行串行化组织,简化了事务并发处理过程,而基于数据库的地图编辑事务在矛盾发生时,需要复杂的事务锁或者额外增加事务补偿,而基于本文模型的串行化事务列表,单个事务要么在提交后执行成功,要么不成功(地图文档不做任何改动);(3)任一地图编辑事务成功提交后,服务器向各个用户统一广播更新显示地图消息,每个客户端按其接收到的最后一个更新消息,在本机地图编辑操作闲时(而非正在编辑地图的忙时)更新本机地图。因此各客户端上地图虽然显示位置、大小各不相同,但地图内容是相同的,而不是各个用户编辑各自的地图文档版本,也不会产生多视图操作冲突[15],从而实现协同制图用户编辑地图“你见即我见”的高效同步显示。

    • 本文建立了利用地图文档状态变化的地图编辑事务模型,采用数据备份和状态重构方法,既不损失数据精度,还能将记录于地图文档中的各类空间关系快速重构,使地图编辑过程不受DBMS执行效率的限制,严格保持地图编辑事务的ACID特性,相比基于DBMS的地图数据库,具备更高的执行效率和事务管理能力。开发者和用户可基于本文模型自定义地图编辑长事务,解决了DBMS长事务执行时间长的问题,进而使多并行地图编辑事务和长事务适于串行化处理,克服了协同制图并发控制过程复杂的瓶颈,为网络协同制图与地理空间数据库快速更新提供了一种有效方法。

参考文献 (15)

目录

    /

    返回文章
    返回