摘要
传统的图数据模型未考虑时间维度，可能会导致时态查询极其复杂，甚至破坏时间信息的完整性，为此，提出了一种时态属性图数据模型和相应的时态图查询语言S-Cypher。该时态图数据模型使用对象节点表示实体，引入属性节点和值节点表示实体的属性，在节点以及对象节点之间的边上记录有效时间以表达时态信息，其记录的有效时间均遵循一组时态约束。S-Cypher是Cypher的时态拓展，在保证兼容的同时不仅提供了一套简洁完善的时态图查询语法，包括时态数据类型、时态图模式匹配、时间窗口限定和时态路径；还提供了一套在Neo4j上进行S-Cypher时态图查询的实现方案。实验结果显示，S-Cypher的查询时间平均是Cypher的1.29倍，表明S-Cypher能够有效地管理Neo4j中的时态图数据，并具有良好的性能。
Abstract
Traditional graph data models lack explicit temporal dimension representation, which may lead to complex temporal queries and potential loss of temporal information integrity. To address this limitation, a temporal property graph data model and a corresponding temporal graph query language called S-Cypher were proposed. The temporal graph data model represents utilized object nodes to represent entities, and introduced property nodes and value nodes to represent entity properties. Valid time was recorded on nodes and edges between object nodes to express temporal information, and the recorded valid time adhered a set of temporal constraints. S-Cypher served as a temporal extension to Cypher, ensured compatibility while providing a concise and comprehensive temporal graph query syntax, including temporal data types, temporal graph pattern matching, time window constraints, and temporal paths. An implementation scheme for executing S-Cypher temporal graph queries on Neo4j was also provided. Experimental results demonstrate that the query time of S-Cypher is on average 1.29 times that of Cypher, indicating that S-Cypher can effectively manage temporal graph data in Neo4j with satisfactory performance.
Keywords
在数字化时代，各行各业都在持续地产生和积累大量数据，时态数据作为其中一类重要资源而日益受到关注。时态数据是指随着时间变化而产生的数据。无论是金融行业的股票交易[1]，物联网的传感器监测[2]，还是社交媒体的用户行为分析[3-4]，时态数据都扮演着不可或缺的角色。这些数据中的时态信息反映着数据之间的时间关系和数据的演化趋势，具有深入分析挖掘的价值。
由于关系数据库的广泛应用，传统的时态图数据模型主要基于关系数据模型。但对于关系复杂的数据场景，关系数据模型的性能较差。越来越多的研究表明，在以关系为导向的应用程序中，图数据模型可以提供更好的可解释性、可拓展性和性能。然而，传统的图数据模型并没有专为时间信息设计的结构。虽然可以直接在传统的图数据模型上存储简单的时间信息（例如，往节点中添加一系列的时间点属性，以代表该节点及其各个属性的有效时间），但这种方式无法存储节点的同一属性在不同时间下的属性值，也很容易破坏时间信息的完整性。另一种方式是使用时态图数据模型。时态图数据模型提供专门的数据结构存储时间信息，有效解决了以上问题。但以时态图数据模型存储时间信息后，图查询将会变得极其复杂，且很容易破坏时态约束，此时一个相应的时态图查询语言是必不可少的。
本文提出了一种基于属性图的时态数据模型及其查询语言S-Cypher。该模型通过对象节点、属性节点与值节点构建时态图结构，在节点与边上记录遵循时态约束规则的有效时间，确保时态逻辑的完整性与一致性。S-Cypher作为Cypher的时态扩展语言，新增时态数据类型、时态图模式匹配、时间窗口限定、时态路径查询及严格遵循约束的更新语法，兼顾兼容性与表达能力。为实现实际应用，设计了时态数据在Neo4j等图数据库中的存储建模规则，并提供基于时间函数插件的S-Cypher查询实现方案，支持在原生Neo4j环境中执行时态操作。
1 相关工作
1.1 时态数据模型及查询语言
20 世纪八九十年代，时态数据库得到了蓬勃发展，产生了大量研究成果，并已进入标准化和产品化阶段。虽然时态数据模型主要基于关系数据模型，但其中的许多基础理论成果也在时态图数据库中得到借鉴和应用，包括以下几个重要概念：
时间域（time domain）：在自然界中，时间每时每刻都存在，可以被看作一个连续的实数域。考虑到计算机的特性，一般以离散形式来表示时间，可以形式化地记为一个Ω的线性域。Ω是线性的，并通过有序的自然数进行离散化。
时间点（point）和时间区间（interval）：时间点指Ω上的一个点，时间区间指一段时间，由开始时间和结束时间组成。其中，开始时间和结束时间都是一个时间点。
时间粒度（time granularity）：指描述时间数据的最小单位，反映了时间域的离散程度。
有效时间（valid time）：指一个对象（事件）在现实世界中发生并保持的那段时间，可以是单一的时间点、单一的时间区间、时间点的集合或时间区间的集合，甚至也可以是整个时间域。一个相近的概念是事务时间（transaction time），指一个数据库对象在数据库中进行操作的时间。本文旨在研究有效时间的管理，事务时间相关的版本化机制并不在讨论范围内。
NOW：NOW是时态数据库中一个特殊的时间元素，指当前时间点，是一个时间变元，随着当前时间的变化而变化。
TempSQL[5]、TQuel[6]和TSQL2[7]是三个具有代表性的时态查询语言，均是对关系数据库查询语言SQL或Quel的时态拓展。作为查询语言，它们大致等于元组演算，借助有效时间代数进行时态查询。S-Cypher与这些时态查询语言有着共通之处，都支持了Allen时态区间关系[8]等时间代数。但由于S-Cypher本质上是一种图查询语言，因此还包括了对Match等图查询子句的时态拓展。
1.2 图数据模型及查询语言
目前有两种主流的图数据模型：属性图[9]和资源描述框架[10]（resource description framework，RDF），通常选择在其一的基础上进行时态拓展。属性图由Neo4j推广并流行开来，可能是当下最流行的图数据模型。在属性图中，节点和关系都可以拥有属性。属性图用节点表示实体，用关系表示实体之间的连接，用属性描述节点和关系的特征，能够以灵活而直观的方式存储和表达图形数据。RDF由三元组构成，每个三元组构成一个“主谓宾”的陈述，在图中表示为两个相连的节点和连接边。RDF图适合构造复杂的知识图谱、语义网和推理系统，但其查询和遍历的效率相对较低，尤其是在面对大规模数据时。
经过长期发展，在属性图和RDF的基础上产生了多种成熟的图查询语言，如Cypher[11]、SPARQL[12]、Gremlin[13]等。其中Cypher是当下最流行的图查询语言，也是事实上的标准，是S-Cypher进行时态拓展的基础。
1.3 时态图数据模型及查询语言
根据标记时间信息的方式，时态属性图数据模型主要分为两种：标记有效时间（valid-time-labeled）的时态属性图数据模型[19-21]和基于快照（snapshot-based）的时态属性图数据模型[22-24]。前者在节点、边性等图元素上标记有效时间以管理图数据的时态信息，后者使用一系列快照和增量更新序列存储时态图数据。快照数据库的优势在于能够快速获得某个时间点的大量数据，但具有一些局限性，比如以全局方式捕获快照不允许直接跟踪单个对象的变化；在分析信息随时间扩散的问题上，快照方法会导致错误的时态路径[25]。考虑到快照数据库的局限性，本文使用标记有效时间的时态属性图数据模型。
目前的时态属性图查询语言主要基于SQL或现有图查询语言进行时态拓展。Campos等[20]提出了TEG-QL，其语法类似于SQL，可以方便地转化为Cypher，但仅能使用Snapshot和In来限制查询有效时间在某个时间点或某个时间区间的节点和边。Debrouvier等[21]介绍了T-GQL，T-GQL使用了一种SQL和Cypher的混合语法，并将重点放在了时态路径查询。Rost等[26]报告了基于属性图查询语言（property graph query language，PGQL）的时序图查询语言T-PGQL，这是一种将图模式匹配与类似SQL的语法和功能结合的图查询语言。
现有时态图查询语言的语法大多不完善且较为粗糙，有较大改善空间，且尚没有时态图数据语言对Cypher进行了良好的时态拓展。为此，本文设计了一种兼容Cypher且语法完善的时态图查询语言。
2 时态图数据模型
2.1 时态属性图
近年来，Debrouvier等[21]提出了一个有影响力的基于属性图的时态图数据模型。该时态图数据模型将节点分为了对象节点、属性节点和值节点，分别代表实体、实体的属性键和实体的属性值。每个节点以及对象节点之间的边都携带一个有效时间。其中，属性节点可以在不连接到任何值节点的情况下存在，其有效时间由用户设置，需要包含其相连的所有值节点有效时间，但不做其他约束。这带来了一定程度的灵活性：可以单独设置对象节点的属性，而不用设置属性值，属性节点有效时间的设置也更加自由。但这却带来了更多的问题：
1）节点属性相关操作的复杂度增加。用户需要经常性地考虑属性节点的有效时间问题。例如，在删除值节点时，必须决定是否要更改属性节点的有效时间，甚至删除属性节点；同样，在添加值节点和更新值节点的有效时间时，也需要考虑是否要修改属性节点的有效时间。
2）属性节点和值节点之间依然存在着约束关系，这与属性节点的独立性矛盾。例如，用户先将某个属性节点的有效时间设置为[2000年，2010年），又在2015年为该属性赋值，即添加一个有效时间为[2015年，NOW）的值节点，此时系统将难以决定应该报错，还是应该修改属性节点的有效时间。系统难以判断属性节点的有效时间是否有意义，但报错又会限制用户操作。
3）属性节点的有效时间存在语义问题。属性节点的有效时间表示该属性在现实中存在的时间域，然而，若属性在某个时间域内没有属性值，该属性也就失去了其存在的实际意义。现实中不存在具有属性但没有属性值的情况。即使要记录属性值不明的情况，也可以直接将属性值设置为Unknow。
为了解决这些局限性，本文改进了模型，使属性节点不能独立存在，且将属性节点的有效时间确定为其所有值节点有效时间的并集。定义1给出了改进的模型。
定义1 时态属性图G可以表示为（No，Na，Nv，Eo，Ep，Ev），其中，No、Na和Nv分别为对象节点、属性节点和值节点的集合，Eo、Ep和Ev分别为对象节点之间的边、从对象节点到属性节点之间的边，以及从属性节点到值节点之间的边的集合。每个节点和每条边都包含一个内容（content）和一个有效时间（VT）。
图1为一个时态属性图示例。时态属性图用对象节点表示实体，用属性节点和值节点分别表示实体的属性键和属性值。对象节点之间的边表示实体间的关系，从对象节点到属性节点之间的边表示属性和实体之间的从属关系，从属性节点到值节点的边表示属性值和属性键之间的从属关系。每个对象节点可以拥有多个属性，因此每个对象节点可以连接多个属性节点。同样地，每个属性键可以拥有多个不同时间下的属性值，因此每个属性节点也可以连接多个值节点。但反过来，每个属性节点和值节点分别只能连接一个对象节点和属性节点。
图1时态属性图示例
Fig.1An example of temporal property graph
对象节点、属性节点、值节点和对象节点之间的边的内容分别表示实体标签、实体属性名、实体属性值和实体关系类型，它们的有效时间则表示所代表的实体、实体的属性键、实体的属性值和实体的关系在现实世界中存在或发生并保持的那段时间。有效时间由一个不相交的非空时间区间集组成，其中，每个时间区间由两个时间点——开始时间和结束时间构成。
2.2 约束
为保证时态数据的完整性，时态图数据库在数据更新操作期间，还必须要满足时态图数据模型的约束如下所示。其中，id（n）表示n的标识号，e{n1，n2}表示从n1到n2的边，E=Eo∪Ep∪Ev。n1，n2∈No∪Np∪Nvn1=n2∨id（n1）≠id（n2）；n1∈No，e{n2，n1}∈En2∈No；n1∈Np，e{n2，n1}∈E，n2∈No；n1∈Np，e{n2，n1}∈En2∈No；n1∈Nv，e{n2，n1}∈E，n2∈Np； n1∈Nv，e{n2，n1}∈En2∈Np；n1∈Np，e{n1，n2}，n2∈Nv； n1，n2∈No，e{n2，n1}e·VT∈n1·VT∩n2·VT； n1∈No，n2∈Np，e{n2，n1}n2·VT∈n1·VT；n∈Npn·VT=·VT； n1，n2∈No，e1{n1，n2}，e2{n1，n2}∈E，e1·content=e2·contente1=e2∨e1·VT∩e2·VT=Ø； n1，n2∈Nv，n3∈Np，e1{n3，n1}，e2{n3，n2}∈En1=n2∨n1·VT∩n2·VT=Ø； n1，n2∈Np，n3∈No，e1{n3，n1}，e2{n3，n2}∈En1=n2∨n1·content≠n2·conent。
2.3 建模规则
本节提出了一组将以时态属性图形式组织起来的数据存储至Neo4j等属性图数据库的建模规则，具体如下：
1）对象节点、属性节点和值节点均使用节点进行建模，并分别赋予标签Object、Property和Value。对象节点的内容由0到多个节点标签表示，属性节点和值节点的内容则由属性content表示。节点的有效时间由属性startTimes和endTimes共同表示。
2）对象节点和属性节点之间的边由边类型为Object_Property的边进行建模，属性节点和值节点之间的边则由边类型为Property_Value的边进行建模，这两类边均不拥有属性。虽然这两类边存储在数据库中，但其作用仅仅是确认属性节点和值节点的归属关系，对用户来说不可见，用户无法直接对其进行操作。
3）对象节点和对象节点之间的边使用边进行建模，其内容由边类型表示，有效时间由属性startTimes和endTimes共同表示。用户可以为其另外设置0到多个静态属性。
将时态图数据以时态属性图形式存储至Neo4j图数据库后，就可以借助Neo4j图数据库所提供的成熟图管理方法来管理，具体的实现方案见第4节。
3 S-Cypher
时态图查询语言S-Cypher可以看作Cypher的时态扩展语言。Cypher的基础语法详见Cypher说明手册[11]，本节旨在对S-Cypher与Cypher的区别，即时态扩展部分进行说明。S-Cypher的时态拓展主要包括：
1）添加时态数据类型——时间区间、一系列时间代数，以及对特殊时间元素NOW的支持。
2）在Cypher的Match子句上添加@T的相关语法，以便于进行时态图模式匹配。
3）支持3种时态路径的查询语法和4种时间窗口的限定语法。
4）添加Stale过时子句用法，并拓展Cypher的Set、Delete、Create子句对时态属性图的更新操作支持。
3.1 时态数据类型
S-Cypher所使用的时态数据类型包括时间点、时间区间（interval）和时间段（duration）。其中时间点和时间段使用了Cypher所定义的5种时间点类型和时间段类型。每个时态数据库在建立时，都必须使用其中一种时间点类型来指定数据库的时间粒度，之后所设置的有效时间中的时间点均为该类型。
时间区间为Map类型，由两个相同类型的时间点——开始时间和结束时间构成，采用前端封闭、尾端开放的形式。
Cypher提供时间点与时间段之间的算术运算和比较运算，以及一系列时间点函数和时间段函数。S-Cypher除了支持Cypher内置的时间算法，还支持Allen的13种时态区间关系[8]，以及几个常见的时间运算，包括Coalesce、Intersect和Except，分别用于处理缺失时间值、计算多个时间区间的交集和计算两个时间区间的差集。
在S-Cypher中，NOW有两种使用场景：一种是在时态查询语句中，匹配在当前时间有效的元素，此时转换器会将NOW用当前时间点代替。另一种是在时态更新语句中用NOW记录元素的结束时间，表示该元素在开始时间之后一直有效，此时转换器会将NOW用相应时间点类型的最大值替代，并存储在数据库中。
3.2 时态查询语法
时态图查询与传统图查询的区别在于时态图查询可将时态信息作为查询的限制条件。本节展示了时态查询语法中限制时态信息的多种方式。
3.2.1 时态图模式匹配
时态图模式匹配在传统图模式匹配的基础上，加入了时态条件的限制。和Cypher中的图模式一样，时态图模式也可以在Match子句中使用。
携带有效时间的时态图元素包括对象节点、属性节点、值节点以及对象节点之间的边。在时态图模式匹配中，可以使用@T（＜start＞，＜end＞）和@T（＜timing＞）对这些时态图元素的有效时间进行限制，其中，＜start＞、＜to＞和＜timing＞的时间点类型与数据库的时间点类型一致。假设某元素的有效时间为T，并在时态图模式中使用@T（t1，t2）（或@T（t1））对其有效时间进行限制，那么仅当[t1，t2）T（或t1T）时，该元素满足匹配条件。
对于已匹配到的时态图元素，可以通过特殊操作符@T查询它们的有效时间，还可以进一步在Where子句中对时态图元素的有效时间进行更加复杂的限制。实体在不同时刻可能拥有不同的属性值，在访问实体的属性值时，可以使用#T（t1，t2）或#T（t1）限制值节点的有效时间。时态信息查询的相关语法如表1所示。
表1时态信息的查询语法
Tab.1 Query syntax of temporal information
注：[]表示可选。
3.2.2 时态路径语义
在非时态图中，如果两个节点之间存在路径，则认为这两个节点是连通的，然而，这种说法并不适用于时态图。在时态图中，常见的有三种时态路径：连续有效路径[27]、成对连续路径[21]和顺序有效路径[21]，在时态上的连续性有着不同的定义。时态路径可由元组（ni（1），ej（1）（T1），ni（1），ej（2）（T2），···，ej（k-1）（Tk-1），ni（k））表示，其中，ni表示id为i的对象节点，ej表示id为j的边，Tk表示ej（k-1）的有效时间，（ni（1），···，ni（k））表示时态路径所遍历的对象节点，（ej（1），···，ej（k-1））表示时态路径所遍历的边。
连续有效路径中的边满足，i=1，···，k-2，即路径中的所有边都同时在某个非空时间区间集T内有效。
成对连续路径中的边满足Ti∩Ti+1≠Ø，即路径中的任意两条相邻边都在某个非空时间区间内同时有效。
顺序有效路径中的边满足Ti·end≤Ti+1·start（i=1，···，k-2），即路径中边的有效时间呈单调递增分布。顺序有效路径适合应用在航班、通信等调度问题上，可以与最早到达路径、最迟出发路径、最快路径和最短路径四种语义结合。
在S-Cypher中查询这些时态路径时，可以限制出发节点、目的节点、关系类型、路径长度，以及路径元素的有效时间。
3.2.3 时间窗口限定
除了在时态图模式中限制元素的有效时间，也可以使用At Time和Between、Snapshot和Scope限定子句的有效时间，从而简便时态查询。对于时态图查询语法，限制有效时间的优先级为：时态图模式匹配＞At Time=Between＞Scope＞Snapshot。
At Time子句和Between子句仅作用于某一条子句，分别包含一个时间点和时间区间，不能对同一条子句使用。At Time子句必须和Match子句或更新子句搭配使用，用于限制元素的有效时间或声明更新的操作时间。Between子句必须和Match子句或Delete子句搭配使用，用于限制元素的有效时间。
Snapshot子句和Scope子句是单独调用的，作用于当前会话下的所有语句，分别包含一个时间点和时间区间。Snapshot子句可对所有语句生效，用于限制元素的有效时间或声明更新的操作时间。Scope子句仅对Match子句和Delete子句生效，用于限制元素的有效时间。当会话同时使用了Snapshot和Scope时，时态查询语句和Delete子句优先根据Scope子句指定时间区间进行匹配，而时态更新语法（除Delete操作）忽略Scope子句，仅根据Snapshot子句指定的时间点进行匹配。
在不使用时间窗口子句时，时态图查询语句仅使用时态图匹配对查询图进行时态限制，时态图更新语句则默认使用当前时刻作为操作时间。
3.3 时态更新语法
S-Cypher的时态更新语法包括对实体、实体关系和实体属性的创建、删除、过时和修改。相对于传统图更新操作，在对时态属性图做更新操作时，还需要处理节点和对象节点之间边的有效时间，并保证它们在更新前后均满足时态属性图的约束。
3.3.1 时态创建语法
时态创建语法包括对实体、实体关系和实体属性的创建，其中，实体和实体关系的创建使用Create子句实现，而实体属性则使用Set子句实现。
创建实体和实体关系时，分别创建一个对应的对象节点和边，其中边的有效时间必须落在其出点和入点的有效时间内，且与同出点、入点和内容的其他关系的有效时间没有重合区间。
创建实体属性时，在该实体对应的对象节点下创建属性节点、值节点和相连边。若已创建过相同属性名的属性，则不再新创建属性节点，而是在之前所创建的属性节点下新创建一个值节点。其中，值节点的有效时间不能与同属性节点下的其他值节点的有效时间重合；属性节点的有效时间必须落在所属对象节点的有效时间内。
假设操作时间为t，那么新创建的对象节点、边和值节点的有效时间默认为[t，NOW），属性节点的有效时间为相连值节点的有效时间的并集。也可以通过指定操作时间或直接指定所创建的对象节点、边和值节点的有效时间，前提是指定的有效时间满足时态约束。
3.3.2 删除语法
时态删除语法包括对实体、实体关系和实体属性的删除，使用Delete子句实现。
物理删除实体时，物理删除对应对象节点及其相连的属性节点、值节点和边；物理删除实体关系时，物理删除对应边；物理删除实体属性时，物理删除对应的属性节点、值节点和相连边，若属性节点不再有相连的值节点，属性节点也会一并删除。
3.3.3 过时语法
过时语法包括对实体、实体属性和实体关系的过时，使用Stale子句实现。过时操作将元素的结束时间由NOW改为操作时间，表示该元素不再实时有效。显然，过时结束时间只能为NOW的元素。
过时实体时，过时对应对象节点及其相连的边、属性节点和值节点；过时实体关系时，过时对应边；过时实体属性时，过时对应的属性节点和值节点。
假设操作时间为t，那么所过时的节点或边的结束时间将由NOW修改为t。t可以由用户指定，但必须迟于开始时间。
3.3.4 时态修改语法
时态修改语法包括对对象节点、对象节点之间的边、值节点的内容、有效时间的修改，以及对实体属性的修改，均使用Set子句实现。
修改对象节点、边和值节点的内容时，分别修改对象节点的标签，边类型和值节点的content属性。其中，在修改边的内容时，需确认修改之后的边与同出点、入点和内容的其他边没有重合的有效时间。
修改对象节点、边和值节点的有效时间时，分别修改对应节点和边的startTimes和endTimes属性，必须确保修改后：
1）边的有效时间同时落在入点和出点的有效时间内，且与同出点、入点和内容的其他边的有效时间没有重合区间。
2）值节点的有效时间与同属性节点下的其他值节点的有效时间没有重合区间。
3）随值节点改变的属性节点的有效时间落在所属对象节点的有效时间内。
实体属性的修改操作可以看作过时操作和创建操作的结合，即先过时在操作时间下有效的值节点，再创建一个内容为指定属性值的值节点。
4 实现
为了利用Neo4j的已有技术来管理时态图数据，本节设计了一套将S-Cypher查询语句转换为Cypher查询语句，并运行在Neo4j图数据库上的实现方案，如图2所示。
图2在Neo4j上运行S-Cypher语句的实现方案
Fig.2Implementation scheme for running S-Cypher statements on Neo4j
4.1 转换器
转换器的作用是将S-Cypher查询语句转换为Cypher查询语句，从而在Neo4j图数据库上查询时态图数据。具体流程如下：
1）使用ANTLR4 解析时态图查询语句，为其生成语法解析树。ANTLR4[28]是一个开源的语法分析工具，已有30余年的历史，能够稳定高效地进行词法分析和语法分析。
2）生成S-CypherWalker对象。S-CypherWalker继承了ANTLR4生成的解析树监听器，在遍历语法解析树的过程中，监听解析过程，并记录时态图查询语句的关键信息。
3）根据S-CypherWalker对象携带的关键信息，使用翻译器将其转换为中间表示S-CypherQuery对象。S-CypherQuery对象是时态图查询语句的对象表示，包含了各类子句对象。
4）根据S-CypherQuery对象的组成，使用生成器将其转换为扩展的Cypher查询语句。
4.2 时态拓展插件
对于无法直接转换为基础Cypher查询语句的时态图查询语句，如时态路径查询、复杂的时态数据操作等。可以借助Neo4j提供的用户自定义过程和函数机制[11]构建自定义时态算法转换。
通过使用Java编写用户自定义过程和函数来构建S-Cypher所需的自定义时态算法，并将其编译为jar文件，放入Neo4j的安装目录后，就可以直接在Cypher中调用自定义时态算法，从而在Neo4j中运行扩展的Cypher查询语句。
此外，在进行时态更新时，有可能会破坏时态约束，而翻译器无法检查所有非法时态更新语句。对于翻译器无法检测到的非法更新语句，本文借助自定义时态算法来进行检查，若更新语句违反了时态约束，则给出错误提示，确保前文提到的时态属性图的时间完整性约束。
在一个简单的社交网络时态图上进行了一系列非法的时间更新操作，并测试了每种违反约束的情况。对于每个违反时间约束的操作，S-Cypher都会抛出错误，这表明S-Cypher可以通过调用时态函数来检查有效时间的有效性，并给出错误提示。由于篇幅限制，更多的非法更新语句参见文献[29]，以下为其中一个非法S-Cypher查询示例。
例1：创建一个于1990年出生名为“Mary Smith”的人和一个于1937年出生名为“Daniel Yang”的人，并创建一条Mary Smith与Daniel Yang之间的从1937年到1990年的朋友关系。
查询结果：
结果显示，该语句不满足约束条件，查询失败。原因是新创建的朋友关系的有效时间并不在Mary Smith的有效时间内，违反了约束8。这与人们的常识相一致，1990年出生的Mary Smith不可能在1990年前就与Daniel Yang成为朋友。
5 实验
本节中的实验始终在8内核，16 GB的单机上运行。实验使用了第3节的实现方案，在社区版Neo4j 5.15.0上进行时态查询。这些实验旨在回答以下问题：
1）与Cypher相比，S-Cypher的时态语法是否更简便？
2）与Cypher相比，S-Cypher时态查询的运行性能如何？
5.1 数据集
实验使用美国航班的真实数据[30]，选取了其中2023年的数据。图中对象节点的标签均为机场（Airport），机场节点之间的边的类型为航班和飞机尾部编号。节点的有效时间均设为[1987年，NOW），航班边的有效时间则设为[＜起飞时间＞，＜到达时间＞）。
5.2 测试
5.2.1 性能对比
首先，使用所提出的时态属性图模型和S-Cypher查询语言在Neo4j上进行时态查询。然后，与直接使用属性图模型和Cypher查询语言进行时态查询的方法进行性能对比。前者使用了第4节提出的实现方案，后者直接在节点上存储该节点及其所有属性的有效时间。
该测试选择K跳顺序有效路径查询作为工作负载。对于每个查询，随机选择一个机场节点，查询该机场只要最多经过K条航班就能到达的所有机场，并返回这些机场的编码。图3展示了两个方案分别进行K跳顺序有效路径查询的查询时间。
结果显示，在进行1~6跳顺序有效路径查询时，S-Cypher顺序有效路径查询的查询时间随着跳数增加而增加，与Cypher相比，S-Cypher查询的运行时间未显著增加，能够以良好的性能执行现实任务。
结果表明，当跳数较少或图规模较小时（具体为图3（a）的前4跳，图3（b）的前3跳），S-Cypher的顺序有效路径查询的查询速度比Cypher慢，平均查询时间是Cypher的2.47倍。
图3不同规模时态图下S-Cypher与Cypher在 K跳顺序有效路径查询中的性能对比
Fig.3Performance comparison between S-Cypher and Cypher for K-hop sequential path queries across temporal graphs of varying scales
然而，当跳数较多或图规模较大时，S-Cypher的顺序有效路径查询有着更快的查询速度，平均查询时间为Cypher的53%。这是由于Neo4j使用内联机制进行了属性存储优化[31]。Neo4j数据库使用固定大小的属性记录存储属性，属性名称直接存储在属性记录中，而属性值则通过一个指向动态存储区的指针或内联值存储在属性记录中。当属性数据少到可以编码到一个属性记录中时，属性值可以直接内联到属性存储文件，而不是存储在一个动态存储区中。显然，通过直接访问内联值获取属性值比从动态存储区查找属性值高效得多。
直接在节点上存储节点和节点属性的有效时间时，由于属性数量较多，节点只能通过访问动态存储区获取属性值。而在使用所提出的时态属性图模型存储数据时，每个节点和边只有3个属性，即content、startTimes和endTimes，在有效时间的时间区间集较小时，可以直接通过访问内联值获取属性值，从而花费了更小的开销。当对有效时间进行索引时，时态查询时间将进一步缩短。
5.2.2 语法简便性
本节通过对比S-Cypher查询语句及转换后的Cypher查询语句的字符数，验证S-Cypher时态语法的简便性。其中，S-Cypher查询语句和Cypher语句在结构和内容均相同的时序图数据上进行查询，其查询结果保持一致。
对简单的社交网络时态图和高速铁路交通时态图进行时态图查询。目标涵盖所有基本时态图查询函数，并对转换前后的查询语句进行比较。测试语句设计S-Cypher的所有语法，包括Match、Create、Delete、Stale、Set和Return。
经过统计，S-Cypher查询语句的平均字符数为Cypher的20.4%，表明S-Cypher可以以更简洁的语法查询时态图数据。此外，由于需要确保时间约束，大多数Cypher查询语句需要依赖于我们定义的时态函数来实现时态图查询。简单地使用Cypher进行时态图数据操作并不能保证正确的时态约束，这也展示了S-Cypher的时态图查询能力。由于篇幅限制，详细的查询语句和字符数统计参见文献[29]。
5.3 局限性讨论
从实验结果看，在跳数较少或图规模较小时，S-Cypher顺序有效路径查询的平均查询时间为Cypher的2.47倍，显示其查询性能还有进一步的完善空间。在未来的工作中，可以通过在图数据库中对有效时间、时态路径等时态对象建立索引来加快时态查询性能，也可以设计时态图数据的底层存储和索引结构来优化时态信息的搜索速度。
此外，由于S-Cypher的实现依赖现有图数据库，其时态查询的本质是在图模式匹配的过程中过滤有效时间符合要求的节点和边。但如果设计了专门的时态图数据引擎，就能够使用其他方式进行时态查询，比如优先对有效时间进行筛选，能够更高效地进行有效时间的范围匹配和多点匹配，再比如支持时态视图，能够对频繁访问的时间点内的数据进行查询。合适的时态图数据库引擎不仅能够提升查询性能，也方便扩展更复杂的时态查询算法，这也是未来的工作方向之一。
6 结论
为更高效地管理时态数据，本文提出了一种基于属性图的时态数据模型和相应的时态图查询语言S-Cypher。该时态图模型使用对象节点表示实体，引入属性节点和值节点表示实体的属性，在节点以及实体与实体间的边上记录有效时间以表达时态信息，其记录的有效时间均遵循一组时态约束。
S-Cypher是Cypher的时态拓展，保证兼容的同时提供了一套简洁完善的时态查询语法，包括时态数据类型、时态图模式匹配、时间窗口限定、时态路径和时态更新语法等，其中更新语法能够始终遵循时态属性图的约束。
本文还提出了一套将时态数据以时态属性图形式组织起来并存储到Neo4j等属性图数据库的建模规则，以及一套将S-Cypher查询语句运行在Neo4j图数据库上的实现方案，从而可以在安装了时间函数插件的Neo4j图数据库上查询S-Cypher查询语句，对时态数据进行管理。
最后，对S-Cypher的查询效果进行了实验验证。实验显示S-Cypher能够以简便的语法以及良好的性能进行时态图查询，且时态更新始终遵循约束。
研究表明，由于Neo4j的内联机制，在利用所提时态属性图模型来存储时态图，并处理海量数据和多跳查询时，可以提高时态查询的性能。这提供了一个新的研究思路，表明利用Neo4j的内联机制可以提高图数据的查询性能。
