Abstract
The language most frequently used to represent the semantic graphs is the RDF (W3C standard for meta-modeling). The construction of semantic graphs is a source of numerous errors of interpretation. Processing of large semantic graphs can be a limit to use semantics in modern information systems. The work presented in this paper is part of a new research at the border between two areas: the semantic web and the model checking. For this, we developed a tool, RDF2NμSMV, which converts RDF graphs into NμSMV language. This conversion aims checking the semantic graphs with the model checker NμSMV in order to verify the consistency of the data. The data integration and sharing activities carried on the framework of the Semantic Web lead to large knowledge databases that must be queried, analyzed, and exploited efficiently. Many representation languages of the knowledge of the Semantic Web, starting with RDF, are based on directed, labeled graphs, which can be also manipulated using graph algorithms and tools coming from other domains. In this paper, we propose an analysis approach of RDF graphs by reusing the verification technology developed for concurrent systems. To this purpose, we define a translation from the SPARQL query language into temporal logic query, a general-purpose graph manipulation language implemented in the ScaleSem verification toolbox. This translation makes it possible to extend the expressive power of SPARQL naturally by adding temporal logic formulas characterizing sequences, trees, or general sub-graphs of the RDF graph. Our approach exhibits a performance comparable to dedicated SPARQL query evaluation engines, as illustrated by experiments on large RDF graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gruber, T.R.: Toward principles for the design of ontologies used for knowledge sharing. Presented at the Padua workshop on Formal Ontology, later published in International Journal of Human-Computer Studies 43(4-5), 907–928 (1995)
Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., Yergeau, F., Cowan, J.: Extensible Markup Language (XML) 1.1, 2nd edn W3C recommendation (2006), http://www.w3.org/TR/2006/REC-xml11-20060816/.
Bechhofer, S., van Harmelen, F., Hendler, J., Horrocks, I., McGuinness, D., Patel-Schneijder, P., Andrea Stein, L.: OWL Web Ontology Language Reference, World Wide Web Consortium, W3C (2004), http://www.w3.org/TR/owl-ref/
Becket, D., McBride, B.: RDF/ XML Syntax Specification (Revised). W3C recommendation (2004), http://www.w3.org/TR/2004/REC-rdf-syntax-grammar-20040210/
Berners-Lee, T., Hendler, J., Lassila, O.: The Semantic Web. Scientific American. pp. 34–43 (2001)
Clarke, E.M.: The birth of model checking. In: Grumberg, O., Veith, H. (eds.) 25 Years of Model Checking. LNCS, vol. 5000, pp. 1–26. Springer, Heidelberg (2008)
Cimatti, A., Clarke, E.M., Giunchiglia, F., Roveri, M.: NuSMV: a new symbolic model checker, pp. 410–425 (2000)
Chan, W.: Temporal-logicqueries. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, Springer, Heidelberg (2000)
Chebotko, C., Lu, S., Fotouhi, F.: Semantics preserving SPARQL-to-SQL translation. Data & Knowledge Engineering (2009)
Klyne, J.J.C.G.: Resource Description Framework (rdf): Concepts and abstract syntax. Tech. rep., W3C (2004)
Bönström, V., Hinze, A., Schweppe, H.: Storing RDF as a graph. In: Latin American WWW conference, Santiago, Chile (2003)
Berners-Lee, T.: W3C recommendation. HTTP-URI (2007), http://www.w3.org/DesignIssues/
Berners-Lee, T., Connolly, D.: Notation3 (N3): A readable RDF syntax. W3C recommendation (2008), http://www.w3.org/TeamSubmission/n3/
Becket, D., McBride, B.: RDF test cases. W3C Working draft (2004), http://www.w3.org/TR/rdf-testcases/
Katoen, J.P.: The principal of Model Checking. University of Twente (2002)
Cyganiak, R.: A relational algebra for SPARQL.Digital Media Systems Laboratory, HP Laboratories Bristol (September 2005)
Pnueli, A.: The temporal logic of programs. In: Proc. 18th IEEE Symp. Foundations of Computer Science (FOCS 1977), Providence, RI, USA, pp. 46–57 (1977)
Mukund, M.: Model Checking, Automated Verification of Computational Systems, pp. 667-681 (2009)
Gueffaz, M., Rampacek, S., Nicolle, C.: ScaleSem: Evaluation of semantic graph based on Model Checking. In: Webist 2011- The 7th International Conference on Web Information Systems and Technologies, Noordwijkerhout, Hollande (May 2011)
Mateescu, R., Meriot, S., Rampacek, S.: Extending SPARQL with Temporal logic. Technical report (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gueffaz, M., Rampacek, S., Nicolle, C. (2011). A New Approach Based on NμSMV Model to Query Semantic Graph. In: Snasel, V., Platos, J., El-Qawasmeh, E. (eds) Digital Information Processing and Communications. ICDIPC 2011. Communications in Computer and Information Science, vol 188. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22389-1_45
Download citation
DOI: https://doi.org/10.1007/978-3-642-22389-1_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22388-4
Online ISBN: 978-3-642-22389-1
eBook Packages: Computer ScienceComputer Science (R0)