Evaluating Continuous Basic Graph Patterns over Dynamic Link Data Graphs

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.