查询流动信息：RDF流的动态处理和自适应增量维护

8430查询流动信息：RDF流的动态处理和自适应增量维护0Xuanxing Yang *0天津大学计算机科学与技术学院 中国天津 tdyxx@tju.edu.cn0摘要0最近，随着动态信息在网络上的普及，已经有人努力扩展RDF和SPARQL以表示流动信息和连续查询功能。虽然现有的工作侧重于RDF流的连续查询过程的形式化和实现，但对于查询RDF流元组之间的复杂时间相关性以及RDF流处理系统的有效、可扩展实现问题却鲜有关注。为了填补这一空白，本文提出了CT-SPARQL和AIMRS，这是一种用于组合流模式的语言和一个用于自适应增量维护CT-SPARQL中定义的RDF流元组的架构。我们相信这项工作将有益于各种实时分析和未来预测应用。0CCS概念0•  信息系统  →  资源描述框架（RDF）；0关键词0RDF流；连续查询；流处理；自适应增量维护0ACM参考格式：Xuanxing Yang. 2018.查询流动信息：RDF流的动态处理和自适应增量维护. 《WWW '18Companion: The 2018 Web Conference Companion》,2018年4月23日至27日, 法国里昂. ACM, 美国纽约, 5页.https://doi.org/10.1145/3184558.318657301 问题0最近，随着大量实时应用的发展，一种新型的流动信息，如GPS信号、实时传感器读数和社交媒体评论，已经出现在网络上。与网络上其他资源之间的持久关系不同，这种信息是实时条件的时间性陈述。0* 由Xiaowang Zhang指导。0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。《WWW '18Companion: The 2018 Web ConferenceCompanion》，2018年4月23日至27日，法国里昂。IW3C2（国际万维网会议委员会）出版，根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31865730各种方面的数据，如交通、传感器网络、共识等以数据流的形式不断传递给处理系统。一旦及时处理和适当解释，这些异构数据流所携带的时间信息将激发各种实时分析和未来预测应用。然而，流动信息的动态性为其应用带来了几个挑战。在语义层面上，为了从数据流中利用相对较高级别的信息，我们需要将来自不同方面的数据流以及静态背景知识结合起来，并使用查询或推理过程来获取感兴趣的答案。然而，由于流动信息的异构性，用统一、明确的语义模型表示数据流和静态知识是必要的。另一方面，流动信息是时间性的。与静态知识相比，每个时间性陈述只在短时间间隔内有效，不同的有效时间导致它们之间的时间相关性非常复杂，如果不仔细建模，将导致完全不同的含义。简而言之，为了捕捉和利用流动信息所携带的语义，我们需要：0∙  用明确的数据模型表示和整合数据流和背景知识。 ∙查询不仅包括流式信息的内容，还包括它们之间的时间相关性。0在数据处理模型上，一次性查询和批处理模型无法捕捉流式信息的动态语义。实际上，我们需要一个连续的查询执行计划，以及一个动态的数据流管理策略。此外，大量和高更新频率的流式信息决定了一般的数据存储和索引策略将不再有用。因此，总结一下，在数据处理层面上处理流式信息，我们需要：0∙  用于连续查询的动态查询执行计划。 ∙用于大量和频繁更新的数据流的有效和可扩展的管理计划。0因此，在本文中，我们提出了CT-SPARQL和AIMRS，这是一种为时间RDF流模式指定的查询语言，以及用于自适应增量维护RDF流的系统。0PhD Track WWW 2018，2018年4月23日至27日，法国里昂84402 最先进的0大量流式信息的处理模型已在[1]中进行了彻底研究。最近，随着语义Web的发展，有一种趋势将流式信息提升到语义级别，并将其与背景知识结合起来，以便不同方面的流式信息可以相互交互[2]。因此，已经努力扩展了RDF[7,8]和SPARQL[9,10]，它们是W3C推荐的用于表示Web上的语义信息和标准RDF查询语言的元数据模型，用于流元组和连续查询功能。在元数据模型层面上，RDF被设计用于表示Web上资源之间的持久关系。为了利用RDF的数据模型来表示流式、时间信息，一个问题是如何将RDF语句的时间注释编码到RDF的数据模型中。现有的工作[5,6]已经研究了这个问题，并表明基于时间点和基于时间间隔的表示对于表示时间注释的RDF语句是等效的。另一方面，正如[21]中所研究的那样，时间语句的有效时间间隔之间的时间相关性非常重要，需要被准确地捕捉和建模。不幸的是，现有的RDF流处理语言，如C-SPARQL[11,12]、CQELS[13]和EP-SPARQL[14]，这些语言都不能查询[21]中列出的所有时间关系。C-SPARQL和CQLES由于依赖于CQL的语义，无法检测窗口内的细粒度时间关系。EP-SPARQL虽然为每个时间RDF语句都添加了时间间隔，但是EP-SPARQL中的时间关系仅限于时间点之间的关系，因此无法对时间间隔之间的时间关系进行建模。在处理模型层面上，连续查询语言(CQL)[3,4]作为首次提出的用于注册可更新关系的连续查询的语言，已经对流处理中的操作进行了彻底的研究和分类，分为三种类型，即流到关系(S2R)操作，关系到关系(R2R)操作和关系到流(R2S)操作。现有的RDF流处理系统都是基于CQL的处理模型，只是以不同的方式扩展了SPARQL查询的R2R操作。C-SPARQL集成了Esper和Jena[24]，这是两个用于CQL和SPARQL的引擎，以实现C-SPARQL引擎，然而，这种方法也限制了其性能和优化的潜力。CQELS通过效率来交换查询复杂性，并实现了一种特殊的RDF编码，一种用于这些特殊编码的RDF数据的SPARQL操作的本地实现，以及一种根据实时处理条件进行自适应映射策略，以实现高系统性能。EP-SPARQL在ETALIS[15]之上实现了其系统，ETALIS是一个用Prolog实现的系统。虽然EP-SPARQL能够捕捉RDF流之间相对复杂的时间相关性，但是它无法模拟时间间隔之间的时间关系。0与C-SPARQL和CQELS相比，PRSP[16-18]在处理RDF流元组方面具有更高的表达能力，但其实现仍然基于批处理模型，在流处理场景中缺乏可扩展性。PRSP[16-18]提供了一个基于插件的RDF流处理框架，可以将不同类型的RDF存储引擎集成在一起，以执行大量的RDF流的查询和推理过程。Strider[19]提供了一个混合自适应分布式RDF流处理引擎，可以使用Spark[20]处理大量的RDF数据。03 提出的方法0我们认为RDF流，即时间注释的RDF语句，是表示Web上流信息的合适数据模型。然而，我们的方法在查询语言和处理模型方面与现有工作有两个主要区别。03.1 查询语言0现有的RDF流处理语言，如C-SPARQL和CQELS，是CQL和SPARQL的扩展。然而，窗口的采用限制了它们的表达能力。在这些语言中定义的模式必须在一个窗口内，即一组预定义的时间间隔内，否则将无法检测到。然而，这种限制在模式本身中并没有明确定义。事实上，大多数数据流是不可预测的，我们无法预定义一个覆盖满足时间模式的所有流元组的窗口。我们认为，在定义时间模式时，用户应该关注流元组之间的时间相关性，而不是窗口引起的隐式时间限制。因此，我们连续查询语言的第一个区别是消除窗口，并且具有独立于窗口的连续查询的清晰语义。其次，在处理RDF流元组之间的复杂时间相关性时，现有查询语言的缺点主要在于：0∙ 无法描述在时间间隔内的流元组的否定。 ∙当一系列流元组以多种方式满足模式时，无法决定选择哪个。0因此，我们引入了一种新的二元运算符，用于定义两个流模式之间的唯一时间顺序关系，并展示如何使用该运算符定义组合流模式。我们相信通过这种方式，我们能够定义任何类型的复杂时间相关性，并准确选择感兴趣的流元组，无论它们的时间顺序如何。03.2 处理模型0现有的RDF流处理系统，如C-SPARQL、CQELS和EP-SPARQL，都基于CQL的处理模型。也就是说，使用流到关系操作符（窗口）提取流元组的部分，并使用关系到关系操作符（SPARQL操作符）0PhD Track WWW 2018, 2018年4月23日-27日，法国里昂8450为了在这些部分上执行查询，并最终使用关系到流操作符将答案流出。然而，这些方法有两个致命的缺点。首先，使用窗口提取的RDF流元组的部分直接转换为一个单一的RDF图，而不考虑它们不同的时间标注，这使得无法从这个RDF图中利用时间信息。其次，现有的RDF流处理系统仍然使用gStore [22]、RDF-3X [23]和Jena[24]等引擎来执行RDF流元组上的查询。这些引擎是为了在一批持久数据上多次执行查询而设计的。在查询执行之前，这些引擎将在数据上建立复杂的索引，以实现高查询执行性能，这也是一个耗时的过程。然而，在CQL处理模型中，仅需要对窗口注册的连续查询进行每次更新执行，并且窗口的内容以高频率更新。因此，对窗口内容建立复杂索引是不必要的，也是对系统资源的浪费，并且依赖于为持久数据设计的查询执行计划必然导致低系统性能和可扩展性差。我们认为将RDF流分割成几个快照比在预定义窗口中维护RDF流元组的总版本更好。首先，我们可以将具有不同时间标注的RDF流元组收集到一组快照中，每个快照用一个唯一的RDF图表示，因此时间信息可以作为这些命名图（快照）之间的一组时间关系来保留。其次，对一组较小的RDF图建立索引的时间消耗较少，更重要的是，它可以并行处理。最后但并非最不重要的是，在这种存储策略中，对多个快照的查询将被分解为对单个快照的一组子查询。通过逐步连接子查询的答案，我们可以得到原始查询的等效答案。因此，这种方法更适合流信息的实时处理特性。我们可以根据中间结果动态修改子查询执行计划，并且及时删除过期的中间结果以减少系统开销。04 方法论0在本节中，我们详细介绍了我们方法的特点，并展示了我们正在进行的工作的一部分。04.1 组合时间关系0我们介绍了一种定义流元组之间组合时间关系的方法。首先，假设两个不相交的集合 �, �，分别表示瞬时事件类型和时间点域，数据流 �是来自 � × � 的元组集合： � = { ( �, � ) | � ∈ �, � ∈ � }。瞬时事件表是从时间点域到布尔值的函数： � : � → { ����, ����� }。而这个函数0当且仅当在时间点 � 处发生类型为 � 的瞬时事件时，� ( � ) ≡ ( �, � ) ∈ �为真。然后我们演示了基本时间关系 SEQ 的语法和语义：SEQ声明了从一个事件类型到另一个事件类型的最近时间顺序关系。以一系列瞬时事件为例：{ ( � 1 , � 1 ) , ( � 2 , � 2 ) , ( � 1 , � 3 ) , ( � 2 , � 4 )}，关系 � SEQ � 是一个元组集合：{ (( � 1 , � 1 ) , ( � 1 , � 3 )) , (( � 2 , � 2 ) , (� 1 , � 3 )) }。形式上，我们有：� 1 SEQ � 2 = { (( � 1 , � 1 ) , ( � 2 , � 2 )) |� ( �2 , � ′ ) ∈ �.� ′ > � 1 → � ′ − � 1 ≥ � 2 − � 1}。事实上，流元组之间的时间关系是组合的，我们相信任何复杂的时间关系都可以分解为一组基本的 SEQ关系。此外，我们给出了组合事件类型的形式语法。(1) 从 �中选择一个瞬时事件类型 � 是一个组合事件类型。(2) 如果 � 1 ，� 2是瞬时事件类型，则表达式 ( � 1 SEQ � 2 ) 是一个组合事件类型。(3)如果 � 1 ，� 2 是组合事件类型，则表达式 ( ¬ � 1 ) ，( � 1 ∧ � 2 ) ，( � 1∨ � 2 ) 是组合事件类型。关于 SEQ关系的表达能力的讨论将是我们未来的工作，然而，我们在这里通过两个例子演示了由 SEQ关系定义的组合事件的表达能力。给定示例数据流：� = { ( � 1 , � 1 ) , (�, � 2 ) , ( � 1 , � 3 ) , ( � 2 , � 4 ) , ( � 2 , � 5 ) } (1)事件的否定。假设我们想找出以类型为 � 的事件开始，以类型为 �的事件结束，并且在时间区间 ( �, � ) 内没有类型为 �的事件的组合事件。这个组合事件可以表示为表达式：( � SEQ � ) ∧ ( �SEQ ( � ∨ � ))。事件 ( � SEQ � ) 和事件 ( � SEQ ( � ∨ � ))的连接保证了在区间 ( �, � ) 内没有类型为 �的事件，并且该事件表达式在 � 上的映射集合为 { (( � 2 , � 4 ) , ( � 2 , � 5)) }。(2) 事件的包含。假设我们想找出以类型为 �的事件开始，以类型为 � 的事件结束，并且在时间区间 ( �, � )内至少有一个类型为 �的事件的组合事件。这个组合事件可以表示为表达式：(( � SEQ ( � ∨ � ))∧ ( ¬ ( � SEQ � ))。该事件表达式在 � 上的映射集合为 { (( � 1 , � 1 ) , ( � 1 ,� 3 )) }。通过这种方式，可以明确区分两种类型的时间间隔，而现有的RDF 流处理语言如 C-SPARQL、CQELS 和 EP-SPARQL 无法做到。04.2 CT-SPARQL0在本节中，我们介绍了连续时间SPARQL（CT-SPARQL），它是一种扩展标准SPARQL语法的查询语言，具有SEQ关系。我们展示了如何将标准SPARQL图模式与SEQ关系结合起来形成RDF流模式。02018年4月23日至27日，法国里昂举办的博士生培训会议8460假设三个互不相交的集合 �, �,�，分别表示URI集合、空白节点集合和文字集合。RDF三元组是来自 (� ∪ � ) × � × ( � ∪ � ∪ � ) 的三元组。另外假设一个与 � ∪ � ∪ �互不相交的集合 �，表示变量集合。RDF流模式递归地定义如下：(1)如果 � 是一个RDF图模式，则 � 是一个RDF流模式。(2) 如果 � 1 ，� 2是RDF流模式，则表达式 ( � 1 SEQ � 2 ) 是一个RDF流模式。(3) 如果 �1 ，� 2 是RDF流模式，则表达式 ( ¬ � 1 ) ，( � 1 ∧ � 2 ) 和 ( � 1 ∨ � 2 )是RDF流模式。SPARQL图模式递归地定义如下：(1) 来自 ( � ∪ � ∪ � )× ( � ∪ � ) × ( � ∪ � ∪ � ) 的三元组是一个RDF图模式。(2) 如果 � 1 ，� 2是RDF图模式，则表达式 ( � 1 AND � 2 ) ，( � 1 UNION � 2 ) ，( � 1OPT � 2 ) 是RDF图模式。(3) 如果 � 是一个RDF图模式且 �是一个SPARQL内置条件，则表达式 ( � FILTER � )是一个图模式。在CT-SPARQL中，瞬时事件用SPARQL图模式表示，组合事件用流模式表示，流模式是一组通过SEQ关系连接的图模式。这种方法将SPARQL和SEQ关系结合在一起，使得CT-SPARQL能够利用SPARQL的表达能力来描述流信息和背景知识之间的异构关系，以及在SEQ关系之上定义的组合时间关系，从而能够明确地查询RDF流。04.3 AIMRS0在本节中，我们介绍了自适应增量维护RDF流（AIMRS）的架构。AIMRS的架构如图1所示，它是一个用于执行大量RDF流上的CT-SPARQL连续查询的系统。接下来，我们简要介绍AIMRS的重要组件以及它们如何相互协作。04.3.1查询解析器。查询解析器将一个跨多个快照的查询分解为一组在单个快照上的子查询。例如，一个CT-SPARQL查询 � : { ?vehichle:registeredAt :roadA } SEQ { ?vehicle :registeredAt :roadB } SEQ{ ?vehicle :registeredAt :roadC } 被分解为一组子查询： � ′ = { � 1 : {?vehicle :registeredAt :roadA } , � 2 : { ?vehicle :registeredAt:roadB } , � 3 : { ?vehicle :registeredAt :roadC }} 并且这组子查询 � ′将用于根据先前的查询执行结果生成动态查询计划。0RDFS推理器0RDF流快照t10RDF流快照t20RDF流0更新0连续查询查询执行反馈0流式结果0有效的流数据0查询结果解析器0更新0待过期的数据0查询计划0RDF流快照t30更新0图1：AIMRS的架构04.3.2动态查询计划。动态查询计划的基本策略是尽早从内存中删除过期的流元组，因为子查询之间通过SEQ关系连接，这可以实现。另一个要点是，只有在其前任子查询在上一个快照中有结果时，才执行子查询。例如，� 1 在快照1中检测到流元组(:vehicle :registeredAt:roadA)，然后在快照2中同时执行 � 1 和 � 2。一旦 � 2在任何快照中检测到流元组(:vehicle :registeredAt:roadB)，快照1中的流元组(:vehicle :registeredAt:roadA)将被删除。04.3.3动态推理过程。为了确保来自异构数据源的流信息能够在语义层面上相互交互，有必要用背景知识丰富它们。例如，从GPS传感器接收到的流信息是一组经度和纬度值，如(:vehicle :hasLongitude:literal1)和(:vehicle :hasLatitude:literal2)。而背景知识将这些地理值与道路相关联，如(:roadA:hasLongitude :literal1)和(:roadA :hasLatitude:literal2)。在这种情况下，我们将使用推理过程为进一步的查询过程添加另一个三元组(:vehicle :registeredAt:roadA)。然而，推理过程是耗时的，并且我们不需要在每个快照中为所有规则进行推理。因此，推理过程也应该是动态的。用于丰富RDF流的规则取决于动态查询执行计划。例如，如果 � 1 和 � 2将在下一个快照中执行，则只需要使用与:roadA和:roadB相关的规则进行推理过程。0PhD Track WWW 2018，2018年4月23日至27日，法国里昂84705 结果0AIMRS的评估主要包括两个标准：CT-SPARQL查询的正确性和系统性能。05.1 正确性0CT-SPARQL验证面临的障碍有两个方面。首先，我们正在进行的工作尚未达到CT-SPARQL的语义层面。虽然我们能够定义复杂的流模式，但我们尚未找到它与现有的RDF流处理语言（如C-SPARQL、CQELS和EP-SPARQL）之间的联系。其次，目前缺乏一种定制生成感兴趣的RDF流数据的方法。虽然现有的工作已经提供了来自C-SPARQL、CQELS和EP-SPARQL的RDF流数据和测试查询。然而，这些工作侧重于CQL的语义，即连续查询功能，并且不关注RDF流元组之间的时间相关性。因此，我们的评估工作主要包括两个部分：（1）CT-SPARQL语言的语义分析。（2）生成具有复杂时间相关性的RDF流元组的定制方式。05.2 系统性能0这部分评估主要包括两个方面：吞吐量和查询响应延迟。吞吐量决定了AIMRS可以应用于多大规模的RDF流处理场景，而查询响应延迟决定了AIMRS可以应用于多少种场景。06 结论和未来工作0在本文中，我们分析了现有RDF流处理工作的现状，并指出了一个新的方向：利用RDF流元组之间的复杂时间相关性的语义和处理模型。我们相信在实时应用中，如交通监测、传感器网络和社交媒体中，一旦适当地探索了这些细粒度的关系，将极大地丰富流信息，并激发各种时间敏感的应用。由于我们已经提出了CT-SPARQL的语法和AIMRS的架构，我们未来的工作将集中在CT-SPARQL的形式化和AIMRS的实现上。0致谢0本工作得到了中国国家自然科学基金（61672377）和中国国家重点研发计划（2016YFB1000603）的支持。0参考文献0[1] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom.数据流系统的模型和问题。ACMSigmod-Sigact-Sigart数据库系统原理研讨会，1-16，2002年。[2] A. Margara，J.Urbani，F. V. Harmelen和H.Bal。流式Web：对动态数据进行推理。Web语义科学服务代理在万维网上，25（1）：24-44，2014年。[3] A. Arasu，S. Babu和J.Widom。CQL：流和关系上的连续查询语言。计算机科学讲义，2003年9月。[4] A.Arasu，S. Babu和J. Widom。CQL连续查询语言：语义基础和查询执行。VLDBJournal，15（2）：121-142，2006年。[5] C. Gutierrez，C. Hurtado和A.Vaisman。时间RDF。欧洲语义Web会议，93-107，2005年。[6] C. Gutierrez，C.Hurtado和A.Vaisman。将时间引入RDF。IEEE知识与数据工程交易，19（2）：207-218，2007年。[7]Hayes，Patrick，McBride和Brian。RDF语义1.1。W3C建议推荐，2014年。[8] R.Cyganiak，D. Wood和M. Lanthaler。RDF1.1概念和抽象语法。W3C建议推荐，2014年。[9] C. Gutierrez，C. Hurtado和A.Mendelzon。查询RDF数据库的形式化方面。SWDB会议论文集，293-307，2003年。[10]S. Harris和A. Seaborne。SPARQL 1.1查询语言。W3C建议推荐，2013年。[11] D. F.Barbieri，D. Braga，S. Ceri，E. D. Valle和M.Grossniklaus。C-SPARQL：用于连续查询的SPARQL。国际万维网会议，1061-1062，2009年。[12] D. F. Barbieri，D. Braga，S. Ceri，E. D. Valle和M.Grossniklaus。用C-SPARQL查询RDF流。ACMSIGMOD记录，39（1），20-26，2010年。[13] D. Le-Phuoc，M. Dao-Tran，J. X.Parreira和M.Hauswirth。统一处理链接流和链接数据的本地和自适应方法。国际语义Web会议，370-388，2011年。[14] D. Anicic，P. Fodor，S. Rudolph和N.Stojanovic。EP-SPARQL：事件处理和流推理的统一语言。国际万维网会议，635-644，2011年。[15] D. Anicic，P. Fodor，S. Rudolph和N.Stojanovic。Etalis：基于规则的事件处理推理。基于事件的分布式系统的推理，计算智能系列。LNCS，Springer Verlag，2011年。[16] Q. Li，X. Zhang和Z.Feng。PRSP：用于RDF流处理的基于插件的框架。国际万维网会议，815-816，2017年。[17] Q. Li，X. Zhang和Z.Feng。RDF流处理的自适应框架。亚太Web，427-443，2017年。[18] Q. Li，X.Zhang，Z. Feng和G.Xiao。RDF流推理的自适应框架。国际语义Web会议，海报和演示，2017年。[19] X.Ren和O.Cure。Strider：一种混合自适应分布式RDF流处理引擎。国际语义Web会议，559-576，2017年。[20] M. Zaharia，M. Chowdhury，M. J. Franklin，S. Shenker和I.Stoica。Spark：带有工作集的集群计算。Usenix云计算热门话题会议，15（1）：10-10，2010年。[21] J. F.Allen。维护关于时间间隔的知识。关于物理系统的定性推理读物，26（11）：361-372，1983年。[22] L. Zou，M. T. Ozsu，L. Chen，X. Shen，R. Huang和D.Zhao。gStore：基于图的SPARQL查询引擎。VLDBJournal，23（4）：565-590，2014年。[23] T. Neumann和G.Weikum。RDF-3X引擎用于可扩展的RDF数据管理。VLDBJournal，19（1）：91-113，2010年。[24] J. J. Carroll，I. Dickinson，C. Dollin，D.Reynolds，A. Seaborne和K.Wilkinson。Jena：实施语义Web建议。国际万维网会议，16：74-83，2004年。02018年4月23日至27日，法国里昂举办的博士生研讨会WWW 2018