论文标题
通过动态链接数据图评估连续的基本图模式
Evaluating Continuous Basic Graph Patterns over Dynamic Link Data Graphs
论文作者
论文摘要
在本文中，我们研究了评估基本图形模式（简称BGP，SPARQL查询的子类）的问题；即，连续更新的链接数据图。我们考虑通过一系列消息流连续接收更新的设置，并支持插入和删除三元组（更新是直接处理的，以删除和插入的结合）。在这种情况下，我们建议一组将缓存数据最小化的内存算法，以有效且不断地回答BGP查询。查询通常会提交到系统中，并在处理更新消息时不断产生三角洲答案。 为了有效，不断地评估流式数据数据的提交查询，以及最大程度地减少缓存数据的量，我们提出了一种方法，将提交的查询分解为更简单的子查询，并通过结合乘头的中间答案来实现查询评估。使用这种方法，提出的算法计算多项式时间和空间中BGP查询的增量答案。请注意，对于BGP查询的某些子类，我们表明可以在恒定或线性的时间和空间中实现评估。整合所有历史的三角洲答案，算法确保在任何给定时间构建每个查询的答案。
In this paper, we investigate the problem of evaluating Basic Graph Patterns (BGP, for short, a subclass of SPARQL queries) over dynamic Linked Data graphs; i.e., Linked Data graphs that are continuously updated. We consider a setting where the updates are continuously received through a stream of messages and support both insertions and deletions of triples (updates are straightforwardly handled as a combination of deletions and insertions). In this context, we propose a set of in-memory algorithms minimizing the cached data to efficiently and continuously answer BGP queries. The queries are typically submitted into a system and continuously result in the delta answers while the update messages are processed. To efficiently and continuously evaluate the submitted query over the streaming data, as well as to minimize the amount of cached data, we propose an approach where the submitted query is decomposed into simpler subqueries and the query evaluation is achieved by combining the intermediate answers of the subqueries. Using this approach, the proposed algorithms compute the delta answers of a BGP query in polynomial time and space. Note that for certain subclasses of BGP queries, we show that the evaluation can be achieved in constant or linear time and space. Consolidating all the historical delta answers, the algorithms ensure that the answer to each query is constructed at any given time.
