Temporal GraphQL: A Tree Grammar Approach

To record the changing history of the schema, each terminal and nonterminal in the body of a production is annotated with a transaction time lifetime (transaction time since edits to the schema are transactions). The lifetimes are updated as follows when edits are made to the productions (to the schema).

• $\mathrm{■}$

  Deletion of terminal or nonterminal in the body - When part of a production is deleted the lifetime of the deleted parts is ended at the time at which it was deleted.

• $\mathrm{■}$

  Insertion of a terminal or nonterminal - An insertion creates a new lifetime starting at the time at which the part of the production was inserted and terminating at time uc (until changed).

• $\mathrm{■}$

  Insertion or deletion of a production - Each terminal or nonterminal in the body is updated as either inserted (lifetime starts) or deleted (lifetime ends).

• $\mathrm{■}$

  Terminal or nonterminal marked as deprecated - GraphQL supports a @deprecated annotation in the schema. Rather than deleting properties or types, they can be annotated as deprecated. Since deprecated properties/types are not deleted, their lifetime will continue (since they contine to be present in the schema). Since deprecated properties and types are part of the GraphQL standard, Temporal GraphQL will continue to support such types, so a slice at the current time will include deprecated fields present as of the time of the slice. However, in Temporal GraphQL fields and properties (including deprecated fields) can be (logically) deleted since rollback to previous versions of the schema is supported. So in some sense, Temporal GraphQL “fixes” the need for having a @deprecated annotation, but for compatibility, it continues to support the annotation.

• $\mathrm{■}$

  Change to a production - We model the change to a production as the deletion of the changed part, followed by an insertion of the new part.

For example, suppose that at time 1 the temporal type given in Figure 6 is inserted in the schema. Then at time 2 the name field is deleted and at time 3 a moniker field is added. By time 4 the production for the type in the query grammar would be as shown below, the temporal annotations are shown as subscripts for each terminal and nonterminal in the body of the production.

The temporal annotations specify the time(s) at which the body of the production is valid. For instance the rule would be used as follows in validating a query, such as that given in Figure 4. Initially, the lifetime of the query is 1-uc. But the query contains the Character name property. So as the query name construct is parsed, the lifetime becomes 1-uc $\bigcap$ 1-2 = 1-2, which is the time interval in which the name property existed. If the lifetime becomes empty, then the parsing fails (at no transaction time is the query valid).

The lifetime computed by the query grammar can be propagated to the task of generating the result using the result grammar, in particular it constrains the result to only data that was alive during the computed lifetime as described next

A result tree grammar can be converted to a temporal result tree grammar that includes timestamps in the data and supports multiple versions of a property as follows. First, for each nonterminal, $X$, in the grammar corresponding to an @temporal object type we add add two nonterminals: a version nonterminal, represented as $X_V$, which represents a single version of the data, and a history nonterminal, represented as $X_T$, which is a list of versions. Next, we add a production, $X_T\to \mathrm{𝚟𝚎𝚛𝚜𝚒𝚘𝚗𝚜}X[X_V\ast ]$, to indicate that a history nonterminal is a list of versions of type $X$. We also add a production, $X_V\to \mathrm{𝚝𝚒𝚖𝚎𝚜𝚝𝚊𝚖𝚙}[T]\mathrm{𝚍𝚊𝚝𝚊}[X]$, to state that a version is the paring of a timestamp (represented by Timestamp type, $T$) and the data for that version, which is an instance of $X$. Finally, in the body of each production we replace $X$ with $X_T$ to indicate that $X$ is temporal.

As an example, the productions in the temporal result tree grammar is given below.

• $\mathrm{■}$

  $\mathrm{\Sigma }=\{\mathrm{𝚒𝚍},\mathrm{𝚗𝚊𝚖𝚎},\mathrm{𝚏𝚛𝚒𝚎𝚗𝚍𝚜},$…$\mathrm{𝚕𝚒𝚏𝚎𝚜𝚙𝚊𝚗},\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗},\mathrm{𝚂𝚝𝚛𝚒𝚗𝚐},\mathrm{𝚍𝚊𝚝𝚊},\mathrm{𝙸𝙳},\mathrm{𝑛𝑢𝑙𝑙}\}$

• $\mathrm{■}$

  $R=Q$

• $\mathrm{■}$

  $N=\{Q,C,C_T,C_V,P,P_T,P_V,S,S_T,S_V\}$

• $\mathrm{■}$

  $\mathrm{\Delta }$ contains the following productions.

  $D$ $\to$ data[$Q$]

  $Q$ $\to$ [ $C_T$ | $S_T\ast$ | $P_T\ast$ ]

  $C_T$ $\to$ versionsCharacter[$C_V\ast$]

  $C_V$ $\to$ timestamp[$T$] data[$C$]

  $C$ $\to$ id[ID] name[ String | null ] friends[$C$]$\ast$ homeworld[$P$] species[$S$]

  $P_T$ $\to$ versionsPlanet[$P_V\ast$]

  $P_V$ $\to$ timestamp[$T$] data[$P$]

  $P$ $\to$ id[ID] name[ String | null ] climate[ String | null ]

  $S_T$ $\to$ versionsSpecies[$S_V\ast$]

  $S_V$ $\to$ timestamp[$T$] data[$S$]

  $S$ $\to$ id[ID] name[ String | null ] lifespan[ String | null ] origin[$P$]

  $T$ $\to$ start[ Int | null ] stop[ Int | null ]

A key feature of the result tree grammar is that it can be expressed with a non-temporal GraphQL schema, enabling GraphQL itself to support Temporal GrapQL. The representational schema for the temporal result grammar is given n Figure 9. The representational schema is a GraphQL schema that represents the data and temporal metadata. In the representational schema the Character type is converted to a CharacterTemporal type. The CharacterTemporal type replaces Character everywhere else in the schema. A temporal type is a list of versions. Each version is a Timestamp paired with a snapshot of a non-temporal Character object. The Timestamp object is simply a transaction time interval, but in practice could be bitemporal, a temporal element, or indeterminate; the object is defined to represent the kinds and nature of times that annotate the data.

The temporal result grammar describes the types produced by the API. A fragment of the representational data is shown in Figure 10. The data represents one change to the “R2-D2” Character, the homeworld was updated from “Tatooine” to “Naboo”. The change creates a new version of the Character object.

We note that this representational grammar takes a temporal-centric approach to querying (described in the next section). In a temporal centric approach filtering is done primarily by temporal constraints rather than value-specific constraints. There are alternative, potential representations that we leave to future work that could better support a value-centric approach. For instance, a Timestamp property could be added to each type in the schema to record its lifetime. We envision a system in which a designer could choose the representational schema that best suits their needs or alternatively choose support for more than one kind of representational schema simultaneously. Note that the schema is not used for storage of the data, rather it provides a view for query access, so supporting alternative representations should be possible.

The temporal result grammar is also used to construct the result of temporal queries. Just as in the non-temporal case, the grammar is used to generate a result by repeated application of the productions starting from the start nonterminal. But in the temporal case two additional features are needed, the timestamps have to be processed and the result can be temporal or non-temporal (depending on the operation). Let’s consider the @slice operator first.

We introduce the notion of sequenced generation (or parsing) to process @slice. It is sequenced because for each use of a production in the generation (parse) there is an associated lifetime that represents when the data is alive. The lifetime is important to track since in the generated tree a child cannot exist without its parent, so each child’s lifetime is constrained by the lifetime of its parent. A slice grabs the part of a history within a time interval specified by the user. So initially, the lifetime of the root is given in the slice. Moreover, when the @slice is validated using an evolving grammar, the validation produces a timestamp that represents the times at which the query is valid (matches the temporal schema grammar). So the lifetime is the intersection of the time specified in the slice and the time produced by the validation. If this time is empty, then the @slice generates an error (the schema does not match the query). As the generation proceeds from the root to each leaf in the result, the lifetime is maintained along each branch in the tree by taking the intersection of the branch’s lifetime with the data’s lifetime in any version object.

As an example, consider the @slice query given in Figure 7 using the grammar of Section 4.2 including the change made to the grammar in Section 4.2.1 on the data of Figure 10. The query specifies a slice from 3-4 but validation produces a time of 1-2 since name only exists at time 1-2. The intersection is empty, hence an error would be generated. But suppose the slice was from 1-1. The result depicted in Figure 11 would be generated. Initially 1-1 would be passed from the root (the hero node) along each branch (each Character version) in the constructed tree. For each version in the data the intersection of the version’s time and the branch’s time is computed, which becomes the branch’s time for descendants along the branch, and the timestamp is updated. If the time is empty then the branch generation is terminated. As an example, for the first (leftmost) versionsCharacter node in Figure 11 the stop property in the timestamp is changed from 2 to 1 as indicated in a red font. For the second versionsCharacter branch the intersection of 1-1 and 3-4 (the time of the version) is empty, so the framed branch in the tree is not generated in the result.

The evaluation of @delta starts the same as the evaluation of @slice with the initial computation of the lifetime of the root. But the intersection of times along a branch is not performed, instead branches are pruned if the version lifetime does not start or end during the branch’s lifetime. So if we replace @slice with @delta in the query in Figure 7 and use a start time of 1, then the validation would produce a root timestamp of times 1-2. When applied to Figure 11 the leftmost branch (without changing the timestamp) would be selected, but the right child has a time of 3-4, so is outside the interval 1-2 and would not be included in the result.

Finally, the evaluation of @snapshot (and @current) is similar to that of @slice insofar as branches are pruned that fall outside of the slice time. But all non-data nodes are removed from the result. As example using Figure 11 the @snapshot at time 1 would prune the framed subtree rooted at the rightmost versionsCharacter node (since its lifetime is 3-4), and also prune from the result the non-data nodes by placing the name node as the only child of the hero node (removing the nodes in blue font in the leftmost versionsCharacter subtree).