An Online Validator for Provenance: Algorithmic Design, Testing, and API

Abstract. Provenance is a record that describes the people, institu-tions, entities, and activities involved in producing, influencing, or deliv-ering a piece of data or a thing. The W3C Provenance Working group has just published the prov family of specifications, which include a data model for provenance on the Web. The working group introduces a notion of valid prov document whose intent is to ensure that a prov document represents a consistent history of objects and their interac-tions that is safe to use for the purpose of reasoning and other kinds of analysis. Valid prov documents satisfy certain definitions, inferences, and constraints, specified in prov-constraints. This paper discusses the design of ProvValidator, an online service for validating provenance documents according to prov-constraints. It discusses the algorith-mic design of the validator, the complexity of the algorithm, how we demonstrated compliance with the standard, and its rest api