一种基于XML数据模型的时空查询代数探讨

柳晓华，万幼川，黄解军

(1.武汉大学遥感信息工程学院,湖北武汉430079；2.武汉理工大学资源与环境工程学院,湖北武汉430070)

一种基于XML数据模型的时空查询代数探讨

柳晓华1，万幼川1，黄解军2

(1.武汉大学遥感信息工程学院,湖北武汉430079；2.武汉理工大学资源与环境工程学院,湖北武汉430070)

时空查询代数是一种抽象的时空查询语言，它利用时空抽象数据类型的一部分基本的谓词、操作、函数来表达时空查询。而在时空微观运算上采用的数据结构是本源XML数据库 (Native XML Database，NXD)用来存储半结构化数据的XML数据结构，所以对XML查询代数-XQuery FS的数据类型和查询操作做了时空扩展，并引入了GML中描述地理特征及其关系的数据类型，定义了一种新的基于XML数据模型的时空查询代数。

时空查询代数；XML数据模型；XML查询代数

关系代数是一种抽象的查询语言，它利用对关系的运算来表达查询，这些运算除了基本的集合、比较、逻辑运算，最重要是选择、投影、连接等专门的关系运算[1]。与关系代数类似，时空查询代数是针对基于XML数据模型的时空抽象数据类型。它的运算对象是时空对象序列(sequence)，而运算符是以FLOWR表达式[2]为代表的选择、投影、连接运算，运算结果也是时空对象序列。时空查询代数本质上是从时空概念模型中抽取时空抽象数据类型 (ADT)，扩展出一系列关于时间、空间、时空数据类型的专用运算符、函数等运算规则，并能够与基础的代数系统，例如关系代数或者XML代数等结合起来，解决基于时空数据模型的宏观运算的定义（时空查询算法的主干部分），即宏观运算。本文就是对XML查询代数-XQuery-FS的数据类型和查询操作做了时空扩展，并引入了GML中描述地理特征及其关系的数据类型，定义了一种新的基于XML数据模型的时空查询代数。

1 研究进展

从已有的文献来看，时空查询主要集中在以成熟的关系代数为基础进行时空扩展的比较多，以XML查询代数为基础进行时空扩展的几乎没有。例如,文献[3]以时间和空间量子数据类型为基础,提出了一种基于量子时间和空间数据模型的时空关系代数。文献[4]在ODMG数据模型基础上扩展出点、线、区域等空间数据类型和时刻、时段等时间数据类型及其操作，提出了一种面向对象的时空代数。文献 [5]通过引入时态逻辑和空间谓词扩展出了时空谓词，其数据模型是把随时间演化的时空对象看成是时间的函数，从而演变出一系列时空数据类型。

上述国内外已有的时空查询代数利用了成熟的关系代数、对象代数的成果；然而关系代数方法表达的时空语义和时空类型是有限的[6]，同时也摆脱不了基于专题分层的数据组织方式。

众所周知，XML数据模型是一种语义标签，能够表达复杂和不断发展的时空语义，同时基于XML规范定义的地理要素标记语言已经广泛应用。本文借鉴上述时空查询代数扩展方法，以XML数据模型及其查询代数-XQuery FS为基础进行时空扩展。

2 NXD时空数据库系统及其查询框架

NXD是专门为存储XML文档设计，也兼有一般数据库 ACID特性。不同之处在于其内部存储模型是基于XML树模型，而非关系模型或面向对象模型[7]。

在一个NXD时空数据库上进行查询，其语义是指用户应该既能描述检索上下文，又能描述返回上下文[7]。而本文XML查询的返回结果必须包含具有时空语义的地理要素或者包含地理要素的时空过程组成的XML片段。

一个典型NXD时空数据库及其时空数据查询的框架如图1所示。从查询处理的角度来说，XML查询处理过程大致分 2个阶段：第一阶段，将查询语言的表面语法转换成由语义指称物（数学符号构成的有意义的对象）组成的逻辑表示，即逻辑执行计划，便于语法错误和变量静态类型的检查，而这个时候还不依赖XML数据，但有可能会导入XML数据的模式定义，即XMLSchema；第二阶段，查询的动态求值阶段，本阶段基于逻辑表示对查询结果的正确性进行推导和基于查询语义进行查询优化[8]。该阶段涉及到具体的查询策略，例如基于导航、连接、导航和连接混合的XML查询策略，及具体结点集的连接、排序、分组，证据树构造等算法。本文更多的是为第一阶段提供时空查询代数。该阶段侧重于时空数据库的逻辑操作，为时空数据库上的用户查询提供形式化的表示和操作手段，包含时空抽象数据从查询算法的输入状态到要求的结果状态之间的一系列判断、操作、函数等。

图1 时空数据库及其时空数据查询的框架

3 时空查询代数形式化定义

基于文献[9]等，W 3C于2001年公布了一个XML查询代数标准XQuery1.0FormalSemantics，即XQuery-FS[2]。该标准遵循W 3C官方推荐的XDM数据模型[10]和XQuery标准查询处理流程。XQuery-FS采用严格的数学符号对XQuery查询语言的语义进行形式化描述，本文时空查询代数的形式化描述完全可以借用形式化描述，有助于时空查询代数标准化、程序推理和提高软件可靠性。

对XQuery处理策略有2种方法：一种是基于核心语法一次一结点的方法；另一种是基于类似关系代数的查询代数的一次一集合的方法[11]。所谓一次一集合的路线，是一套类似于关系代数的代数体系。每一个代数操作符的输入都是一个或者多个XML树集合，输出也是一个XML树集合，但是其间从初始状态到要求得结果状态通过代数的判断和操作等发生了事先要求的变化，即达到了查询的目的。通常，为了生成XML树集合，从 XQuery语句中生成 1个或多个模式树(pattern tree)，模式树表示了该查询感兴趣的 (包括谓词结点和目标结点)一组有祖先后代关系的变量绑定，然后，用模式树从输入的XML树中抽取实例树[12]。比如，对于查询 Q1，会先抽取模式树 bib(book(price，title))，然后用这个模式树对 XML树 (文档或者片段)进行匹配，得到模式树的实例树集。随后在这个实例树集上进行谓词判断(price<5)，最后输出希望的结果。

Q1:FOR$b in(document("bib.xm l"))/bib/book WHERE$b/price<50

RETURN{$b/title}

可以看出，这种一次一集合的处理方式，它最大的优点是能够对逻辑操作树进行优化。但前提是必须事先存在一个能够参与运算的XML数据模型，这个数据模型涵盖了文档或者片段中的结点对象、结点类型、结点的在文档顺序(documentorder)中的位置及其蕴含的上下文关系 (祖先-后裔:a/d或者父-子:p/c)[12]。当然按照此逻辑模型组织的XML文档数据如何映射到线性的物理存储空间不在本文讨论范围之内。

上述数据模型只是包含了输入的XML文档/片段的数据内容，但并没有给出如何获取单个的文档结点及其文档顺序和关系。定义一套标准的操作符用于对结点进行操作，获取结点及其结构信息，以及构造查询结果。这些操作在谓词判断阶段非常有用，相当于时在实例树的基础上，在进行一次一结点的精细操作，最后得到查询Q1的结果。

一套代数系统包括数据模型和在数据模型上定义的一组运算集合。为遵循一定数据模型的XML文档集合定义一套运算，这就是XML查询代数（Algebra For XML）。

时空查询代数就是在上述XML数据模型 (XDM)和运算集合 (XQuery-FS定义的Functions和Operators)的基础上进行时空扩展，并采用上述一次一集合与一次一结点相结合的策略来处理时空查询代数。其中运算对象和运算结果都是XDM中序列对象的时空扩展类型的变量，而运算符将在Functions和Operators基础上扩展出时空谓词、时空函数、时空操作。序列(sequence)本身是一个容器，它的项 (item)要么是一个XML结点，要么是一个原子数据类型。那么序列当然可以容纳一个地理要素结点，即占据一定空间，有着特殊构造，随时间变化的地理事物或现象在信息世界的模型，即地理实体。

本文将以基于特征的时空数据模型为基础，在数据类型、查询操作符以及形式语义3个方面对XQuery-FS给出的XML查询代数进行了扩展，使其能够适应时空数据的查询。

3.1 时空数据库逻辑结构

一个NXD时空数据库通常是一个由有根、有序、带标签的树构成的森林，其中，每个结点代表一个元素、属性、文本，每一条有向边代表元素之间或者元素与值之间的父子关系[13]。其逻辑结构相关定义如下：。

定义1 XML文档一棵基于标签的有序的根树，用T=（N，E，R）表示被标记的结点和被标记的边，组成的具有以下性质的树：

——任意结点N都有四元组作为它的标记；

——每条边都被pc或者ad标记，其中pc表示2个结点之间是父子关系，ad表示2个结点之间是祖先和后代的关系，这种标记可以通过四元组推算出来，不需要显示记录；

——R是树的根，当R不是INFOSET中定义的文档结点（DOCUMENT）时,XML文档实际上是一个XML片段。

定义2 XML结点XML文档的组成单元，用N= {Label,Type,Value,OID}表示,它是1个四元组。它包括 7类：文档结点、元素结点、属性结点、文本结点、处理指令结点、注释结点，大多数情况下我们只用前 4类。文档结点在所有结点的前面，可以嵌套一个或者多个相互嵌套和并列的元素结点，元素结点可以嵌套零个或多个属性结点或者文本结点，这种嵌套关系是通过XML文档的边（pc或者ad）来表示的。其中：

——Label表示标签，描述结点的意义；

——Type表示对象值的类型，一种为原子型；另一种为复杂类型，在XDM中都有相关定义，或者通过XDM扩展、限制等方式扩展的自定义类型；

——Value表示属性的值或者文本；

——OID表示结点的扩展前缀编码，用来表达该结点的文档顺序，取序列中任2个结点的前缀编码，可以判断这2个结点的相对顺序关系：pc（/）和 ad(//)关系，以及兄弟关系；取任意结点的编码，可以得到一个从根开始到该结点的路径的结点序列。

定义3序列由零个或者多个项（item）组成，而项由零个或者多个原子值或者XML结点组成。序列是有序、异构、项可重复、不可嵌套的。同时他也是所有XQuery表达式的值，他可以作为时空代数操作的中间结果进行序列推理或者直接作为返回结果。它的特点如下：

——一个仅含有一项的序列与这一项本身是等价的，例如：序列（1）与原子值1在W 3C数据模型表示同一个值；

——一个序列不包含另一个序列-即序列只有一层，例如：在W 3C的XQuery数据模型中不存在（l，（2，3），4，5）这样的序列；

——序列中的项可以是原子值和XML结点。

定义4时空数据库模式STM=（F，E，R），其中，F=ST?N，ST是表达时空语义的结点的集合，即时空要素，STM是多个包含时空要素的XML文档T的集合，时空数据模式就是带标签的有序树组成的森林。当序列中包含时空要素结点时，序列相应扩展为时空序列。正如元组和关系是传统关系数据库操作的基本单元一样，XML文档/片段和XML文档集合将是NXD数据库操作的基本单元。

以上引入了时空要素结点，用户可以使用它们表达时空数据和时空变化，并通过特定的时空操作完成时空查询。

3.2 类型系统定义

XQuery查询语言不仅是一种由各种表达式组成的函数式的语言，而且还是一种强类型的语言，有着严格的数据类型系统。其严格的数据类型系统是通过XQuery系列规范中的XDM规定的，是XQuery规范的一部分。XDM规定了所有表达式的输入和输出的数据类型，而且表达式可以嵌套。

XQuery/XPath形式语义和数据模型 (XDM)规范中，数据模型由原子值 (如 boolean、double等数据)、XML结点 (如Document、Element、Attribute等)和序列 (Sequence)组成。而序列的项（Item）可以是原子类型也可以是结点类型。XDM内置定义包括25种基本和派生的类型，但这些类型不足以描述时空数据。而为了扩展XDM并在XDM上定义时空查询代数，我们引入这些数据类型时，必须对其做一些扩展。

空间、时间、地理要素数据类型的在GML中已经给出了标准化的定义。其中地理要素数据类型 gm l:_ Feature[14]是时间、空间、属性的统一体，是基于特征的时空数据模型的核心概念。该模型已经在文献 [15]中进行了阐述，能够表达特征内部和特征级别的时空变化语义，在此不在重复，本文直接将其中的地理要素作为序列的结点类型引入XDM，如图2所示。

图2 时空数据模型数据类型层次图

图2中展示的数据类型名称与GML定义的名称一致，但内容模型都经过了扩展，以表达复杂的时空变化语义，即实体的内部变化和实体的更替变化；另外，图2只给出了部分从GML引用或者扩展出来的时空数据类型，为了保证在扩展的XDM上时空查询代数的封闭性和完备性，实际应用中必须全部引入GML定义的元素和属性。从图 2可以看出，序列的项要么是结点或者在XMLSchema中定义的原子类型，要么是从GML中扩展和引入的复杂类型结点。这些定义在gm l命名空间中的结点与XDM中原有的结点具有同等地位。

在定义图2所示的数据类型的同时，XDM还定义了一系列存取函数，用于在查询处理过程中，查询引擎能够快速获取序列结点的语义信息，这样查询引擎就不会按照XML的语法结构去进行逐结点进行字面匹配，而会按照类型信息或者语义规则进行匹配，从而优化了查询语句。由于引入了图2中的在 gm l命名空间中的时空数据类型，我们必须定义一些针对这些新数据类型的存取函数（见表1），便于是空间查询代数进行语义优化。

表1 新增存取函数

3.3 查询操作定义

XQuery FS自身提供了投影、选择和连接等操作的定义，还引入结构递归、条件判断等编程语言的概念。这些都能应用于基于XDM扩展的时空数据类型，只不过把含有时空数据的XML文档实例当成结构良好的一般XML文档处理，而不能进行时空查询。为了能支持对含有时空数据结构的XML文档实例进行时空查询和时空分析，我们定义了一系列针对时空数据类型的时空关系谓词和时空函数、时空操作符。当然，这些谓词、操作符、函数在基于传统关系数据模型的时空查询中已经定义过了，我们要做的是把它们对应到基于XDM数据模型的时空查询中来。

基于空间数据和时态数据的谓词、操作符、函数定义在相当多的关系数据模型上已经做了详细的阐述，只不过操作数和操作结果由元组变成了结点序列（或者单结点序列），所以本文中不再重复。

本节将主要讨论基于时空数据类型 gm l:_Feature和gm l:_FeatureCollection[15]的构造函数（构造子）及其实体内部变化和实体级别的动态变化的基本操作。

由于XML数据模型的灵活性，基于某个XML模式的数据类型的构造比由简单的几个域组成一个平面化的关系数据模型要复杂。一个地理要素可能是一个要素集合也可能是单个要素，而单个要素是时间、空间、属性及其关系的复合。这种复合会形成一种树型的结构，这种树型结构可以通过有序的序列来构造。而这种有序可以通过某种编码，例如前缀编码来实现[16]。所以我们提供2种时空数据类型的构造子（如表2所示）。

表2 时空数据构造子

实体内部变化的基本操作包括对地理要素的时空属性的获取操作和时空关系操作（见表3）。

表3 时空属性获取操作

实体级别的时空变化的表达对于表达时空过程非常有用，本文也给出了实体级别的时空变化的基本操作（见表4）。

表4 实体级动态变化基本操作

4 结语

对已知集合中任意2个元素来做二元运算时，如果所得结果仍是此集合的元素，则称此集合关于运算具有封闭性[17]。本文在XQuery-FS基础上扩展出来的时空查询代数的操作在序列上具有封闭性。这是因为XQuery是以表达式为基础的函数式语言，其表达式的运算结果是一个序列，而这个序列又可以作为另外一个表达式的操作数，这也是XQuery的表达式可以嵌套的原因，所以时空查询代数操作在序列上是封闭的，可以统一地用于时空或者时态或者空间数据的管理。

结合基于特征的时空数据模型的时空语义，通过扩展XQuery-FS查询代数的数据类型和操作，给出了时空查询代数的形式化定义，为后续在NXD基础上开展时空查询引擎以及时空查询优化研究打下了理论基础。

[1] 王珊,萨师煊.数据库系统概论(第四版)[M].北京：高等教育出版社,2006

[2] World Wide Web Consortium,XQuery 1.0 and XPath 2.0 Formal Semantics. W 3C Recommendation 23 January 2007,http:// www.w3.org/TR/2007/REC-xpath-datamodel-20070123/

[3] Jose R.Rios Viqueira.Relational Algebra forSpatio-temporal Data Management[J].In:Proceedings of the EDBT 2000,PhD Workshop,2000,43-46

[4] Tony Griffiths,A lvaro A,Fern and es A,et al.A Query Calculus for Spatio-temporal Object Databases[J].Eighth International Symposium on Temporal Representation and Reasoning (TIME-01)Claudio Bettini and Angelo Montanari(eds.),IEEE Computer Society Press,Civdale del Friuli,Italy,2001:101-110

[5] Martin Erw ig,Markus Schneider.Spatio-temporal predicates[J]. IEEETransactions on Know ledge and DataEngineering(TKDE), 2002,14(4):881-901

[6] 周英华,金培权,岳丽华.一种基于对象关系模型的时空查询代数stro-algebra[J].中国科学技术大学学报,2006,36(11): 1190-1195

[7] 万常选,刘喜平.XML数据库技术[M],清华大学出版社,2008

[8] 孟小峰,王宇 .XML查询优化研究[J].Journal of Software, 2006,17(10):2069-2086

[9] Mary Fern_ and ez,et al.A Data Model and A lgebra for XML Query [J/OL], http://www.cs.bell-labs.com/wadler/topics/ xm l.htm l#algebra:1～16

[10]World Wide Web Consortium.XQuery 1.0 and XPath 2.0 Data Model(XDM).W 3C Recommendation 23 January 2007.http:// www.w3.org/TR/2007/REC-xpath-datamodel-20070123/

[11]孟小峰,罗道峰.OreintXA:一种有效的XQuery查询代数[J].软件学报,2004,15(11):1648-1660

[12]Jagadish H.V,Laks V.S,Lakshmanan,et al.TAX:A Tree Algebra for XML[J].Lecture Notes in Computer Science,2002,Volume 2397/2002:149-164

[13]罗道峰,孟小峰.OrientStore:Native XML存储方法[J].计算机科学,2003,30(10):105-110

[14]Open Geospatial Consortium Inc.OpenGIS?Geography Markup Language(GML)Encoding St and ard.OpenGIS?St and ard.http:/ /www.opengeospatial.org/st and ards//gm l.

[15]LIU Xiaohua,WAN Youchuan.Logical Expression of Feature-Based Spatio-temporal Data Model Research[DB/OL],2nd International Conference on Information Engineering and Computer Science-Proceedings,ICIECS 2010.

[16]LIU Xiaohua,WAN Youchuan.Storing Spatio-Temporal Data in XML Native Database[DB/OL],2010 2nd International Workshop on Database Technology and Applications,DBTA2010-Proceedings.

[17]沈以淡.简明数学词典[Z].北京：北京理工大学出版社,2003

Spatio-temporal Query Algebra Based on XML Data Model

by LIU Xiaohua

The spatio-temporal query algebra is one kind of abstract spatio-temporal querylanguage;it uses the subset of basic predicates, operations,the functions of spatio-temporal abstract data type to express the spatio-temporal query.While the data model of the spatiotemporal microscopic operates employed the XML data model which the Native XML Database(NXD)adopt to store semi-structured spatial-temporal data,therefore this article held the space and time expansion to the XML query algebra-XQuery FS data type and the query, and introduced in GML to describe the geography feature and it's relationships,has defined one kind newly based on the XML data model space and time inquiry algebra.

spatio-temporal queryalgebra，XML datamodel，XMLquery algebra

2011-03-04

项目来源：国家自然科学基金资助项目（41071104）；武汉市青年科技晨光计划资助项目（200950431203）。

P208

B

1672-4623(2011)03-0081-05

柳晓华，博士，研究方向为时空数据库、时空建模。