Incremental View Maintenance for SPARQL Queries: Adapting the Counting Algorithm

The counting algorithm is a classic approach to incremental view maintenance for queries on relational data. We adapt this algorithm to SPARQL queries on RDF (Resource Description Framework) datasets. In the decentralized Web, data are customarily stored in RDF, which is linked data that can be queried using SPARQL. The efficiency of retrieval of query results can be improved through maintaining views on the data incrementally as the underlying data change. SPARQL operators give rise to heterogeneous sets of solution mappings and involve multi-set semantics. We develop a theory of SPARQL algebra on annotated sets of solution mappings and show how to handle operators traditionally perceived as difficult, including LeftJoin, Diff, and Minus. We discuss the implementation of our methods—based on the counting algorithm—and assess the feasibility using data and queries from the Berlin SPARQL Benchmark. Performant incremental view maintenance will be instrumental when querying the decentralized web at scale.