ABSTRACT
A graph rewriting system should be capable of specifying under what conditions a graph manipulation operation is valid. The embedding instructions normally contain a fair amount of information and are usually very flexible; however, allowing the policy designer to specify the embeddings may become error-prone. The OPM nomenclature places a restriction on the set of admissible RDF graphs, which we call valid OPM graphs. These restrictions serve to control a graph transformation process (also a graph rewriting process) by ruling out transformations
that lead to nonadmissible graphs. Our graph matching is based on regular expressions. We identify the patterns in the provenance graph by composing regular path queries in SPARQL. Therefore, this chapter is devoted to processing queries with regular expressions.
