陈旭, 张富, 曹东霞
东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2017-05-16
基金项目：国家自然科学基金资助项目(61672139)。
作者简介：陈旭(1979－)，男，宁夏银川人，东北大学博士研究生。

摘要：现实世界中存在大量的时空数据, 时空数据的管理对时空建模提出了更高的要求, 因此成为当前许多领域的研究热点.UML作为众多领域广泛使用的统一建模语言, 基于UML的时空扩展模型也成为许多领域时空建模的重要形式.为此, 本文提出一种时空UML模型, 该模型能够表示与处理时空对象的多种时空拓扑关系(包括RCC-8空间和Allen-13时态拓扑关系)以及它们之间的复杂语义关系(例如关联、聚合、泛化和依赖)；同时给出了时空UML的形式化表示形式和语义解释方法.最后结合地籍变更的实例说明了所提方法的可行性和实用性.
关键词：UML模型RCC-8空间拓扑Allen-13时态拓扑时空数据建模
Spatio-Temporal Model Based on UML
CHEN Xu, ZHANG Fu, CAO Dong-xia
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: ZHANG Fu, E-mail: zhangfu@cse.neu.edu.cn
Abstract: There are a lot of spatio-temporal data in the real world. The management of spatio-temporal data has proposed higher requirements for spatio-temporal modeling, which has become a hotspot in many fields. UML is a widely used unified modeling language, and the spatio-temporal extension model based on UML has become an important spatio-temporal modeling approach of many fields. This paper presents a spatio-temporal UML model, which can deal with a variety of spatio-temporal topology relationships (including RCC-8 spatial topology and Allen-13 temporal topology relationships) and the complex semantic relations among the spatio-temporal objects. In addition, this paper provides a formal definition and semantic interpretation of spatio-temporal UML model. Finally, an example of cadastral change is provided to demonstrate the feasibility and practicability of the proposed model.
Key words: UML modelRCC-8 spatial topologyAllen-13 temporal topologyspatio-temporal datamodeling
现实世界的许多领域^[1]都涉及时间和空间信息, 尤其是在地理信息系统GIS(geographic information system)中, 对时间和空间信息的表达尤为重要, 因此建立一种合理通用的时空数据模型对GIS的研究起着至关重要的作用^[2].RCC-8理论^[3]和Allen-13区间代数理论^[4]都是非常经典的空间和时间拓扑关系模型.此外, 还有时空结合的数据模型, 从时空数据的存储方式可以分为基于矢量的时空数据模型和栅格数据模型; 从概念建模的角度可以分为基于ER/EER的时空数据模型^[5]、基于面向对象的时空数据模型等^[6-7].
在上述多种时空模型中, 面向对象方法在表达复杂对象以及对象之间复杂语义关系等方面具有独特优势, 因此也被广泛应用于时空建模.尤其是, 统一建模语言UML(unified modeling language)^[8]作为一种功能强大的面向对象可视化系统分析建模语言, 基于UML的时空扩展成为时空建模的重要手段.当前存在的基于UML的时空扩展模型^[9-10], 其中大部分模型都是利用UML的扩展机制来添加时空对象及其属性, 并利用UML中广泛使用的类图来表示时空对象之间的关系, 但仍缺少一种完整的UML模型来全面地表示时空对象之间的时态和空间关系, 同时也缺少UML时空模型的形式化表示定义^[11]和语义解释方法.
为此, 本文在已有UML时空模型的基础上对时空对象间的时态关系和空间关系进行细分, 利用RCC-8理论和Allen-13区间代数理论将时空对象间的空间拓扑关系分为8种, 时态拓扑关系分为13种, 进而提出一种时空UML模型, 该模型能够表示与处理时空对象的多种时空拓扑关系以及它们之间的复杂语义关系, 比如时空数据的关联、泛化等关系, 与此同时提出了时空模型的形式化表示和语义解释方法.最后, 结合地籍变更的实例说明了所提模型的可行性和实用性.
1 已有时空数据模型现状分析为了进行时空建模, 提出了多种时空数据模型, 比如时间快照模型^{[6, 12]}、时空复合数据模型^[13]、基于简单时间戳的数据模型^[14]、基于事件的模型^[15]、时空立方体模型^[6]、时空ER模型^[5].此外, UML作为一种基于面向对象的统一时空建模语言, 已经成为众多领域广泛使用的建模标准.随着时空建模的需求, 基于UML的时空扩展模型也成为许多领域时空建模的重要形式.文献[9]给出了一种时空UML建模手段, 利用UML的扩展机制定义了时空类、属性、关系等构造型, 通过在类图中使用这些构造型表示一个小型的房屋市场系统, 并通过例图、活动图从不同的角度刻画系统; 文献[10]给出了另一种UML时空建模手段, 用图形表示法来代替UML中的构造型, 通过增加5种图形标号来扩展时空UML, 并且通过增加一个规格说明盒来描述由这5种图形标号表示的时空数据的语义.
综上，现有的几种时空UML建模方法不能满足各个应用领域的需要和挑战, 对UML时空建模与扩展的相关研究也从未停止过, 因此使得时空建模的研究得到了快速的发展.上述已有的几种时空UML建模方法不能够表示与处理同时含有多种空间和时态拓扑关系(例如较为经典的RCC-8空间拓扑关系和Allen-13时态拓扑关系)的时空对象以及它们之间的复杂语义关系; 再者, 现有的建模方法未能给出UML时空模型的形式化表示及体现UML时空模型丰富的语义表达能力.在此基础上, 本文提出了一种新的UML时空模型, 该模型能够表示与处理时空对象间的多种时空拓扑关系, 同时给出了时空UML的形式化表示方法和语义解释，最后针对一个小型地籍变更系统的实例，给出相对应的时空UML类图，验证了模型的有效性.
2 时空UML模型时空UML, 即在UML的基础上加入时间和空间概念, 以及地理对象的属性等信息.本文利用UML的扩展性结合时空概念进行时空数据建模.
2.1 时空UML类在时空建模中, 具有相同特性的时空对象构成一个时空类, 具体划分为以下三种:
1) 空间类:类的位置和空间范围相关.形式上, 用《spatial cla》构造型表示该类为空间类.
2) 时态类:类和时间戳有关, 随着时间的变化而变化.形式上, 用《temporal cla》构造型表示该类为空间类.
3) 时空类:是空间类和时态类的结合, 即该类与空间范围和时间戳相关, 用《spatio-temporal cla》构造型表示该类为时空类.
上述三种类的UML表示形式如图 1所示.
图 1(Fig. 1)

图 1 时空UML类的表示形式Fig.1 Expression of spatio-temporal UML classes

2.2 时空UML属性在时空建模中, 与时间或空间相关的属性构成一个时空属性, 具体划分为以下三种:
1) 空间属性:该属性的取值是一个空间范围值, 形式上, 用《spatial att》构造型表示该属性为空间属性.
2) 时态属性:该属性的取值与时间戳有关, 属性值可能随着时间变化.形式上, 用《temporal att》构造型表示该属性为时态属性.
3) 时空属性:该属性的取值与一个空间范围以及时间戳有关.形式上, 用《spatio-temporal att》构造型表示该属性为时空属性.
上述三种时空属性的UML表示如图 2所示, 以时空属性为例.
图 2(Fig. 2)

图 2 时空UML属性的表示形式Fig.2 Expression of spatio-temporal UML attributes

2.3 时空UML关联关系在时空建模中, 时空对象之间的关系随时间或空间变化, 具体划分为以下三种:
1) 空间关联关系:即一个关联关系和空间范围相关, 表示该关联关系在一定的空间范围内存在, 而且会随着空间的变化而变化，形式上用《spatial asc》构造型表示.此外, 针对具体的8种RCC-8空间关系(DC, EC, PO, TPP, TPPi, NTPP, NTPPi, EQ), 形式上分别用8种构造型来表示, 即《spa-DC asc》, 《spa-EC asc》, 《spa-PO asc》, 《spa-TPP asc》, 《spa-TPPi asc》, 《spa-NTPP asc》, 《spa-NTPPi asc》, 《spa-EQ asc》.
图 3给出RCC-8空间关联关系对应的UML表示方法, 以《spa-DC asc》为例.
图 3(Fig. 3)

图 3 空间关联关系表示Fig.3 Expression of the spatial association relationship

2) 时态关联关系:即一个关联关系和时间戳有关, 该关联关系可能随时间的变化而变化，形式上用《temporal asc》构造型表示.又因为时态关系具体可分为Allen区间代数的13种关系(before, after, equal, meets, met-by, overlaps, overlapped-by, during, includes, starts, started-by, finishes, fished-by), 针对这13种时态关系分别给出对应的构造型表示方法, 即《tem-before asc》, 《tem-after asc》, 《tem-equal asc》, 《tem-meets asc》, 《tem-met-by asc》, 《tem-overlaps asc》, 《tem-overlapped-by asc》, 《tem-during asc》, 《tem-includes asc》, 《tem-starts asc》, 《tem-started-by asc》, 《tem-finishes asc》, 《tem-finished-by asc》.
图 4给出Allen-13时态关联关系对应的UML表示方法, 以《tem-before asc》为例.
图 4(Fig. 4)

图 4 时态关联关系表示Fig.4 Expression of the temporal association relationship

3) 时空关联关系:每个关联关系都和一个空间范围以及时间戳有关.形式上, 用《spatio-temporal asc》构造型表示该关联关系为时空关联关系.
2.4 其他时空UML关系2.4.1 聚合关系聚合关系也可以定义为组合关系, 它们都是关联关系的特例, 假如类与类之间的特点是“整体与部分”, 就可以把这种特殊的的关联关系定义为聚合关系, 其表示方法如图 5所示.
图 5(Fig. 5)

图 5 聚合关系表示Fig.5 Expression of the aggregation relationship

2.4.2 泛化关系泛化关系是用来描述类的一般和具体之间的关系.在泛化关系中, 一般描述的类被称作“父类”, 具体描述的类被称作“子类”.泛化关系表示方法如图 6所示.
图 6(Fig. 6)

图 6 泛化关系表示Fig.6 Expression of the generalization relationship

2.4.3 依赖关系将两个及以上的多个元素进行连接, 这种连接不需要用实例来表达其本身的意思, 其中一个是客户, 另外一个是服务者, 依赖关系表示方法如图 7所示.
图 7(Fig. 7)

图 7 依赖关系表示Fig.7 Expression of the dependence relationship

3 时空UML形式化表示本节将给出时空UML模型的形式化表示, 并给出相应的语义解释.
有限集合X和Y, 函数T(由X到Y)若满足:任意?x_i∈X, 有T(x_i)=y_i∈Y, 则T为Y上的X标记元组, 同时标记为T(X, Y)或者[x₁:y₁, …, x_k:y_k].
定义1 ?一个时空UML模型可以用一个元组ST_UML=(L, att, ass, agg, gene, dep, mult)表示.其中:L= C_ST∪A_ST∪S_ST∪S_C-ST∪R_ST∪D_ST是词汇表, C_ST是一个时空类标识符的集合, A_ST是时空属性的标识符集合, S_ST是时空关联的标识符集合, S_C-ST是时空关联类的标识符集合, R_ST是角色标识符集合, D_ST表示域标识符集合; att:C→T(A, D)和S_C→T(A, D)是从时空类C∈C_ST和时空关联类S_C∈S_C-ST到T(A, D)的一个函数, 其中属性A∈A_ST, 域D∈D_ST, 即将时空类C或时空关联类S_C映射为D上的属性A标记的元组，形式上att(C)=[…, A:D, …]或att(S_C)=[…, A:D, …]用于表示时空类或时空关联类的属性; ass:S→T(R, C)表示时空类关联关系的一个函数, 即将时空关联S映射为时空类C上的角色R标记的元组, 形式上ass(S)=[…, R:C, …]; agg?C×(C₁, C₂, …, C_n), 是定义在时空类上的一个关系, 用于表示一个类C和一组类(C₁, C₂, …, C_n)之间的聚合关系; gene?C₁×C₂表示子类与父类的泛化关系, 是时空类C上的二元关系; dep?C₁×C₂表示目标与源类的依赖关系, 也是定义在时空类C上二元关系; mult是一个从C×S×R到N₀×(N₀ ∪ {∞})函数, 必须要满足以下的条件:对S∈S_ST且ass(S)=[r₁:c₁, …, r_n:c_n], 定义mult(c_i, s, r_i)=(mult_min(c_i, s, r_i), mult_max(c_i, s, r_i)), 其中r_i∈R_ST, c_i∈C_ST.mult_min(c_i, s, r_i)表示类c_i的一个实例通过角色r_i参与关联s的最小次数(0表示无约束), mult_max(c_i, s, r_i)表示最大约束(∞表示无约束).
通过指定时空数据库状态STD(spatial temporal database state)与相应的UML模型可以给出形式化的语义, 下面给出时空UML模型的语义解释方法.
定义2 ?给定任意时空UML模型ST_UML=(L, att, ass, agg, gene, dep, mult), 与ST_UML相对应的时空数据库状态STB=(Δ^STB, ·^STB), 其中Δ^STB是所有时空集的集合, ·^STB是一个函数.
1) 对任意域标识符D∈D_ST, 函数·^STB将D映射为相应的基本域D^STB.
2) 对任意时空类C∈C_ST, 或时空关联类S_C∈S_C-ST, 函数·^STB将C或S_C映射为Δ^STB的一个子集, 即C^STB ?Δ^STB, S_C^STB?Δ^STB, 其中C^STB表示时空类C相应的实例集合, S_C^STB表示时空关联类S_C相应的实例集合.
定义3 ?给定任意时空UML模型ST_UML=(L, att, ass, agg, gene, dep, mult), 与时空UML模型ST_UML相对应的一个时空数据库状态STB是合法的, 当且仅当STB满足下列条件:
1) 对任意时空类C₁, C₂∈ C_ST, 若C₁, C₂为子类与父类关系, 即gene关系, 则C₁^STB?C₂^STB.
2) 对任意时空类C∈ C_ST, 且满足如下关系:att(C)=[A₁:D₁, …, A_K:D_K], 则对任意时空类C∈C^STB, 存在唯一的a_i = < c, d_i>∈A^STB, d_i∈D^STB, 其中i∈{1, …, k}.
4 地籍变更实例地籍管理信息系统是地理信息系统的一个重要领域, 地籍管理信息系统管理的地籍对象是地块, 地块分割与合并的标准是权属或用途的变化, 随着时间推移, 地块的分割与合并不断变化^[5].图 8是一小型地籍变更系统^[6], 从图中可看出随着时间推移, 由于权属或用途变化各地块在不断进行着分割与合并, 使用本文提出的UML时空模型对地籍变更进行建模, 之后提出UML对象图针对图 8中的具体的地籍变更进行分析与建模.
图 8(Fig. 8)

图 8 小型地籍变更系统Fig.8 Small cadastral change system

图 9为地籍变更的时空UML类图, 由图可知, 建立了一个通用的类地块Parcel类, 该类中定义了所有地块类的共有属性, 根据地块权属或用途的变化可分为不同的地块区, 如工业区、居民区、商业区等, 不同用途的地块区分别为不同的类, 都继承Parcel类, 且都有各自的属性, 不同的地块区在时间和空间上存在不同的时态和空间关系.
图 9(Fig. 9)

图 9 地籍变更时空UML图Fig.9 Spatio-temporal UML diagram of cadastral change

5 结语本文提出了一个基于UML的时空建模方法, 通过UML的扩展机制构造型添加了有关时空类和时空关系, 并在关联关系的基础上细分了RCC-8空间和Allen-13时态拓扑关系, 完整地表达了时空对象间的时空关系, 之后又提出了该模型的形式化定义, 最后通过一个地籍变更的例子来说明本文所提模型的可行性.在未来的工作中, 将更加深入地研究本文所提模型, 一方面改进本文所提模型的不足, 使模型更加适合于表示时空对象的动态变化; 另一方面, 将本文所提模型转化为描述逻辑, 进行推理.
参考文献

[1]	Wang X Y, Zhou X F, Lu S L.Spatiotemporal data modelling and management: a survey[C]// The 36th International Conference on Technology of Object-Oriented Languages and Systems.Xi′an, 2000: 202-211.
[2]	Song X, Wang Y, Wu G, et al.Base state amendments spatio-temporal data model with dynamic selection of base state[C]// The 4th International Congress on Image and Signal Processing.Xi′an, 2011: 2349-2353.http://ieeexplore.ieee.org/document/6100782/
[3]	Randell D A, Cui Z, Cohn A G.A spatial logic based on regions and connection[C]// The 3rd International Conference on Knowledge Representation and Reasoning. Monterey, 1992: 165-176.
[4]	Allen J F. Maintaining knowledge about temporal intervals[J].Communications of the ACM, 1983, 26(11): 832–843.DOI:10.1145/182.358434
[5]	Hadzilacos T, Tryfona N. An extended entity-relationship model for geographic applications[J].ACM Sigmod Record, 1997, 26(3): 24–29.DOI:10.1145/262762
[6]	Pelekis N, Theodoulidis B, Kopanakis I, et al. Literature review of spatio-temporal database models[J].Knowledge Engineering Review, 2004, 19(3): 235–274.
[7]	陈新保, 朱建军, 陈建群. 时空数据模型综述[J].地理科学进展, 2009, 28(1): 9–17. ( Chen Xin-bao, Zhu Jian-jun, Chen Jian-qun. Spatiotemporal data models and their extensions:a review[J].Progress in Geography, 2009, 28(1): 9–17.)
[8]	Rumbaugh J, Jacobson I, Booch G. Unified modeling language reference manual[M]. 2nd Edition. [S.l.]: Pearson Higher Education, 2004.
[9]	Svinterikou M, Kanaroglou P.A microsimulation approach to the modelling of urban population and housing markets within an object-oriented framework[C]//ERSA Conference Papers.Volos, 2006: 147-154.https://core.ac.uk/display/39435897
[10]	Price R, Tryfona N, Jensen C S. Extending UML for space and time-dependent applications[M]. Hershey: IGI Publishing, Advanced Topics in Database Research, 2002: 342-366.
[11]	张富.模糊数据库支持的模糊描述逻辑与本体知识库抽取和存储关键技术的研究[D].沈阳: 东北大学, 2011. ( Zhang Fu.Studies on key technologies of extracting and storing fuzzy description logic and ontology knowledge bases with fuzzy databases[D].Shenyang: Northeastern University, 2011.)
[12]	Rocha L V D, Edelweiss N, Iochpe C.GeoFrame-T: a temporal conceptual framework for data modeling[C]//Processing of the 9th ACM International Symposium on Advances in Geographic Information Systems.Atlanta, 2001: 124-129.
[13]	Langran G, Chrisman N R. A framework for temporal geographic information[J].International Journal for Geographic Information and Geovisualization, 1988, 25(3): 1–14.DOI:10.3138/K877-7273-2238-5Q6V
[14]	Hunter G J, Williamson I P. The development of a historical digital cadastral database[J].International Journal of Geographical Information System, 1990, 4(2): 169–179.DOI:10.1080/02693799008941538
[15]	Peuquet D J, Duan N. An event-based spatiotemporal data model (ESTDM) for temporal analysis of geographical data[J].International Journal of Geographical Information Systems, 1995, 9(1): 7–24.DOI:10.1080/02693799508902022