1.1 Namespaces

The following namespaces and prefixes are used throughout this document.

All other namespace prefixes are used in examples only. In particular, IRIs starting with http://example.org/ represent some application-dependent IRI [RFC3987].

1.2 Conventions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

Unless otherwise stated, examples throughout this document use the PROV-N Provenance Notation [prov-n].

In this specification, we use the term Qualified Name in accordance to [prov-dm], and use its syntax as specified in [prov-n] (see production prod-QUALIFIED_NAME). In compliance with [prov-dm], we note that a qualified name can be mapped to an IRI by concatenating the IRI associated with the prefix and the local part.

3.1 Variable Grouping

We define a group of variables ^◊, or group ^◊ for short, as a set of group variables that are expected to change values in lockstep with each other. Groups are identified by a natural number. A pattern's grouping of group variables ^◊ is a partitioning of the set of variables occurring in a pattern; each partition forms a group and is allocated a natural number.

A binding ^◊ is an association between a variable and some values. If there is a binding for a variable, the variable is said to be bound ^◊. If there is no binding for a variable, the variable is said to be unbound ^◊.

All group variables belonging to a given group MUST be bound to the same number of values, since their values have to change in lockstep manner. If this condition is not satisfied, it is an error situation (see error IncorrectNumberOfBindingsForGroupVariable).

A group variable SHALL NOT belong to more than one group.

The algorithm to deterministically create a grouping of variables for a pattern P is as follows.

Grouping function (Pattern: P) {
  List<Variable> variable_list=sort(extract_group_variables(P));

  Hashtable <Variable,Set<Variable>> linked = extract_linked_variables(P); // includes transitive closure
  
  Grouping g = new Grouping();
  int count = 0;
  for (Variable v: variable_list) {
    if (!(belong v g)) {
       add v and linked.get(v) to g as group identified by count;
    }
    count++;
  }	
  return g;
}

First, all group variables are extracted from the pattern and sorted by alphabetical order of their URIs. Then, all linked variables are computed, in the form of a map, associating a variable to the variables it is linked with. It is assumed that the transitive closure of this relation is computed here. Then, each variable (if not already inserted in the grouping) is added to the grouping with the variables it is linked with. Groups are deterministically identified, starting with value 0. This procedure is deterministic since it relies on the alphabetical sorting of group variables.

In the absence of tmpl:linked attribute, we have as many groups as variables.

3.2 Group Usage

A PROV statement MAY contain a set of group variables. A statement's group usage ^◊ is the list of group identifiers corresponding to these variables; the list of group identifiers is ordered in ascending order. The group usage for a statement without group variable is the empty list []. A list is noted by integers separated by commas occurring in square brackets.

3.3 Binding Structure

The examples above have shown that group variables belonging to a same group evolve in a lockstep manner, whereas the statement-level variables should be bound to as many group of values as the number of possible instantiations of the statement they occur in.

A group variable or a statement-level variable occurring in optional identifier position is bound to a list of values. A bundle variable is bound to a single value (i.e. a list of length 1). A statement-level variable (not occurring optional identifier position) is bound to a list of list of values: this allows a given attributes to be have 0, 1, or more occurrences in a given statement.

Since all group variables of a group g in a set of bindings B MUST be associated with lists of values having the same length; this length is given by number_of_variable_values(B,g). Otherwise, it is an error, see IncorrectNumberOfBindingsForGroupVariable.

Section 4. specifies how a set of bindings can be expressed as a PROV document.

3.4 Variable Value Indexing

Let us consider a set of bindings B and a statement's group usage [g₁, ..., g_n], where g₁, ..., g_n are group identifiers, with n ≥1 (meaning that the statement contains at least one group variable). A variable value index ^◊ is a list [i₁, ..., i_n] of naturals of length n, such that each 0 ≤ i_j < number_of_variable_values(B, g_j).

A variable value index for a group usage and a set of bindings B denotes a particular combination of variable values.

The expansion algorithm (see Section 3.5) enumerates and sorts all possible variable values indices for a given group usage. For that, we rely on the following index order ^◊: in [i₁, ..., i_n], i₁ is the least significant integer, and i_n is the most significant integer. So, [0,0] precedes [1,0], which precedes [0,1], which precedes [1,1].

  agent(ex:ag1,[tmpl:order = "[0]"])

  entity(ex:en3,[tmpl:order = "[2]"])

  wasAttributedTo(ex:en2, ex:ag2,[prov:type = 'ex:t4', tmpl:order = "[1, 1]"])

3.5 Expansion

Expansion proceeds by processing each statement in turn, instantiating variables according to the following algorithm.

Bundle expansion(Set of bindings: B, Bundle b) {
  bid = substitution(bundle_variable(b),B);
  l = empty list of statements;
  for each statement s in bundle b {
    u = the group usage for s;
    count = 0;
    for all possible variable value index i (sorted by increasing index order) for u  {
      env = the effective bindings for B and i;
      s2 = substitution_group_variable(s,env);
      s3 = substitution_statement_level_variable(s2,B,count);
      s4 = set_tmpl_order_attribute(s3,i);
      count++;
      add s4 to l
    }
  }
  return new bundle with bid and l;
}

Table 2 summarizes the syntax and meaning of variables and attributes accepted in a PROV template.