Recent studies on change detection for RDF data have focused on minimizing the delta size and, as a way to exploit the semantics of RDF models in reducing the delta size, the forward-chaining inferences have been widely employed. However, since the forward-chaining inferences should pre-compute the entire closure of the RDF model, the existing approaches are not scalable to large RDF data sets. In this paper, we propose a scalable change detection scheme for RDF data, which is based on backward-chaining inference and pruning. Our scheme, instead of pre-computing the full closure, computes only the necessary closure on the fly, thus achieving fast and scalable change detection. In addition, for any two RDF data input files to be compared, the delta obtained from our scheme is always equivalent to the one from the existing forward-chaining inferences. In addition, in order to handle RDF data sets too large to fit in the available RAM, we present an SQL-based implementation of our scheme. Our experimental results show that our scheme, in comparison to the existing schemes, can reduce the number of inference triples for RDF change detection by 10–60%.
FlourisGManakanatasDKondylakisHPlexousakisDAntoniouG. Ontology change: classification and survey. The Knowledge Engineering Review2008; 23(2): 117–152.
3.
NoyNFKleinM. Ontology evolution: Not the same as schema evolution. Knowledge and Information Systems2004; 6(4): 428–440.
4.
PlessersPTroyerOCastelyanS. Understanding ontology evolution: A change detection approach. Journal of Web Semantics2007; 5(1): 39–49.
5.
TummarelloGMorbidoniCBachmann-GmurRErlingO. RDFSync: Efficient remote synchronization of RDF models. In: Proceedings of international semantic web conference, 2007, pp. 537–551.
6.
ImDLeeSKimH. A version management framework for RDF triple stores. International Journal of Software Engineering and Knowledge Engineering2012; 22(1): 85–106.
7.
KleinMKiryakovAOgnyanovDFenselD. Ontology versioning and change detection on the Web. In: Proceedings of international conference on knowledge engineering and knowledge management, 2002, pp. 197–212.
8.
NoyNFMusenMA. Ontology versioning in an ontology management framework. IEEE Intelligent Systems2004; 19(4): 6–13.
9.
VolkelMGrozaT. SemVersion: An RDF-based ontology versioning system. In: Proceedings of IADIS international conference on WWW/internet, 2006, pp. 195–202.
10.
LeonardiEHoaiTTBhowmickSSMadriaS. DTD-DIFF: A change detection algorithm for DTDs. Data & Knowledge Engineering2006; 61(2): 384–402.
11.
WangYDeWittDJCaiJ. X-Diff: An effective change detection algorithm for XML documents. In: Proceedings of international conference on data engineering, 2003, pp. 519–530.
12.
Berners-LeeTConnollyD. Delta: An ontology for the distribution of differences between RDF graphs, http://www.w3.org/DesignIssues/Diff (2004).
13.
PapavassiliouVFlourisGFundulakiIKotzinosDChristophidesV. On detecting high-level changes in RDF/S KBs. In: Proceedings of international semantic Web conference, 2009, pp. 473–488.
14.
TzitzikasYTheoharisYAndreouD. On storage policies for semantic Web repositories that support versioning. In: Proceedings of European Semantic Web conference, 2008, pp. 705–719.
15.
ZeginisDTzitzikasYChristophidesV. On the foundations of computing deltas between RDF models. In: Proceedings of international Semantic Web conference, 2007, pp. 637–651.
16.
ZeginisDTzitzikasYChristophidesV. On computing deltas of RDF/S knowledge bases. ACM Transactions on the Web2011; 5(3): 14.
ChristophidesVPlexousakisDSchollMTourtounisS. On labeling schemes for the Semantic Web. In: Proceedings of international World Wide Web conference, 2003, pp. 544–555.
19.
BroekstraJKampmanA. Inferencing and Truth maintenance in RDF Schema. In: Proceedings of workshop on practical and scalable semantic system, 2003.
20.
ShenWQuY. An RDF storage and query framework with flexible inference strategy. In: Proceedings of Asia–Pacific Web conference, 2006, pp. 166–175.
21.
StuckenschmidtHBroekstraJ. Time–space trade-offs in scaling up RDF schema reasoning. . In: Proceedings of workshop on scalable Semantic Web knowledge base system, 2005, pp. 172–181.
22.
BroekstraJKampmanAHarmelenFV. Sesame: A generic architecture for storing and querying RDF and RDF schema. In: Proceedings of international Semantic Web conference, 2002, pp. 54–68.
23.
OgnyanovDKiryakovA. Tracking changes in RDF(S) repositories. In: Proceedings of international conference on knowledge engineering and knowledge management, 2002, pp. 373–378.
24.
CarrollJJ. Signing RDF graphs. In: Proceedings of international Semantic Web conference, 2003, pp. 369–384.
25.
CarrollJJDickinsonIDollinCReynoldsDSeaborneAWilkinsonK. Jena: Implementing the Semantic Web recommendation. In: Proceedings of international World Wide Web conference, 2004, pp. 74–83.
26.
EderJWiggisserK. Change detection in ontologies using DAG comparison. In: Proceedings of international conference on advanced information systems engineering, 2007, pp. 21–35.
27.
LeonardiEBhowmickSSMadriaS. XANDY: Detecting changes on large unordered XML documents using relational databases. In: Proceedings of international conference on database systems for advanced applications, 2005, pp. 711–723.
28.
AbadiDJMarcusAMaddenSRHollenbachK. Scalable semantic web data management using vertical partitioning. In: Proceedings of international conference on very large data bases, 2007, pp. 411–422.
29.
WilkinsonKSayersCKunoHReynoldsD. Efficient RDF storage and retrieval in Jena2. In: Proceedings of workshop on Semantic Web and databases, 2003, pp. 131–150.
30.
ChongEIDasSEadonGSrinivasanJ. An efficient SQL-based RDF querying scheme. In: Proceedings of international conference on very large data bases, 2005, pp. 1216–1227.
31.
EisenbergAMeltonJ. SQL: 1999, formerly known as SQL 3. sigmod record1999; 28(1): 131–138.
