Namespaces and Prefixes

The metamodel for the abstract syntax of RDF streams is defined in the namespace http://www.w3.org/ns/rsp# and we use the prefix rsp for this namespace. Additional prefixes used in this document are the following:

Temporal Entities and Timestamp Predicates

Timestamped Graphs

A timestamped graph is defined as an RDF Dataset under the RDF Dataset semantics that "each named graph defines its own context" (see ) and where a particular triple in the default graph has been designated as the timestamp triple, with the following constraints:

1. There is exactly one named graph pair <n, G> in the RDF Dataset (where G is an RDF graph, and n is an IRI or blank node).
2. The timestamp triple has the form <n, p, t>, where n is defined in the previous item, and p is a timestamp predicate that captures the relationship between the temporal entity t, called the timestamp, and the graph G.

There may be multiple triples in the default graph, including multiple triples using timestamp predicates, but exactly one triple must be designated as the timestamp triple. The objects of any triples that use a timestamp predicate but are not the timestamp triple of the timestamped graph are not called timestamps.

Due to the assertion of the timestamp triple, the context referred to in "each named graph defines its own context" has a temporal aspect to it. Other aspects of this context may be asserted by additional triples in the default graph of the timestamped graph. Such triples are not required to have timestamp predicates, and thus may be about non-temporal aspects of the context, e.g., the authority or the sensor device. That is, we require the context to have a temporal aspect to it, but the context is not limited to temporal aspects. Thus, it would be misleading to call it a "temporal context".

The part of the definition above that points to RDF Dataset semantics really belongs in the semantics section, not in this definition, which should be purely syntax. We need additional informative text that gives the motivation for these definitions.

This definition does not permit the timestamp to be omitted, which is one of the data structures that is considered to be in-scope by the requirements document.

A sequence of RDF graphs (or named graphs, or RDF datasets) MAY be physically received by an RSP engine, which MAY then create an RDF stream from it by adding timestamps, e.g. indicating the time of arrival. The original sequence is not itself an RDF stream.

This definition allows the timestamp to be an IRI or blanknode. Additional information about the timestamp may be provided in the default graph (e.g., through properties in the OWL Time Ontology), but this is not required by the definition of timestamped graph.

A literal-timestamped graph is a timestamped graph whose timestamp t is an rdfs:Literal.

Merge and union of RDF streams with non-literal-timestamped graphs may not be defined. See .

The timestamp predicate p may be drawn from a community agreed vocabulary (Issue 10). The timestamp predicate may also be user-defined.

The format in the examples of this document follows TriG, although does not imply any specific serialization or formatting; it simply shows the data structured according to the RDF stream model. When the default graph of a timestamped graph contains only one triple, this must be the timestamp triple, so there is no need of an additional format to designate it. In examples of timestamped graphs having more than one triple in the default graph, the first triple of the default graph to occur in the serialization is assumed to be the timestamp triple. Prefixes (e.g. prov:, dul:) are used for readability; their expansions are defined in Table 1.

A non-normative subsection should be created to hold all the information about the formatting of examples, and there the expansion of all prefixes that are used in examples can be defined.

According to the semantics defined in , the assertion of the named graph pair means that the graph denoted by :g entails the two triples :axel :isIn :RedRoom and :darko :isIn :RedRoom, under whatever entailment regime is being considered. It does not assert those triples directly, nor does it assert that these triples are actually in that graph. Further, it does not rule out additional entailments of :g. These details are best explained in the semantics section itself, although it would probably be helpful to have some informative explanation near the beginning to avoid confusion.

Given any two timestamped graphs, TSG1 and TSG2, we say that TSG2 covers TSG1 (denoted TSG1 ≲ TSG2) if and only if TSG1 and TSG2 have the same timestamp predicate P and the timestamps, t1 and t2 resp., satisfy t1 ≤P t2, where ≤P is the temporal partial order associated with the time plenum of the timestamp predicate P.

The relation ≲ between timestamped graphs is a preorder (a reflexive, transitive binary relation). It is not a partial order because it doesn't have the antisymmetry property (a≲ b and b≲ a implies a = b.)

RDF Stream

An RDF stream S consists of a sequence of timestamped graphs, called its elements, such that elements sharing the same timestamp predicate are ordered by the partial order associated with this timestamp predicate. I.e., if a stream S contains elements S(i) and S(j) with i < j and S(i) covers S(j), then the timestamps of S(i) and S(j) are equal.

If a timestamp predicate occurs in the timestamp triple of an element of an RDF stream, we say it is a timestamp predicate of the stream.

Time-boundedness properties on RDF streams behave better if it is required that the set of temporal entities for each timestamp predicate is pairwise bounded. I.e., for each pair of temporal entities in the set, there is a temporal entity in the set that is an upper bound of both, as well as a temporal entity in the set that is a lower bound of both. This property is not satisfied by branching temporal structures, but could be a requirement of some profile.

The comparability between any pair of elements of an RDF stream must (or should?) be completely determined from the default graphs of those elements, or elements that precede at least one of them. Otherwise the ordering could be revealed by a subsequent element, inducing retroactively an ordering requirement on a previous pair of stream elements.

On the following we may refer to RDF stream simply as stream.

There can be multiple graphs with the same timestamp in the stream.

It has been pointed out that this statement might be problematic, as graphs could no longer be used for punctuation purposes. Comparatively, we have not found a constraint on this in similar models e.g., CQL: there could be zero, one, or multiple elements with the same timestamp in a stream.

Isomorphism

Two RDF timestamped graphs TSG1 and TSG2 are isomorphic if and only if there is a bijection M between the nodes, triples, graphs and named graphs in TSG1 and those in TSG2 such that:

1. M maps blank nodes to blank nodes;
2. M is the identity map on literals and IRIs;
3. For every triple <s p o>, M(<s, p, o>)= <M(s), M(p), M(o)>;
4. For every graph G={t1, ..., tn}, M(G)={M(t1), ..., M(tn)};
5. For every named graph NG=<n, G>, M(NG)=<M(n), M(G)>;
6. M(NG1)=NG2, M(DG1)=DG2, and M(TST1)=TST2, where NG1 is the named graph of TSG1, DG1 is the default graph of TSG1, TST1 is the timestamp triple of TSG1, and similarly for TSG2.

The definition of timestamped graphs allows blank nodes to be used as graph names, as well as within triples.

:_1 {...} {:_1, prov:generatedAtTime, t1}


:_2 {...} {:_2, prov:generatedAtTime, t1}

      
      

Two RDF streams are S-isomorphic if and only if they have the same set of elements.

:g1 {...} {:g1, prov:generatedAtTime, t1}
:g2 {...} {:g2, prov:generatedAtTime, t2}
:g3 {...} {:g3, prov:generatedAtTime, t2}
:g4 {...} {:g4, prov:generatedAtTime, t3}



:g1 {...} {:g1, prov:generatedAtTime, t1}
:g3 {...} {:g3, prov:generatedAtTime, t2}
:g2 {...} {:g2, prov:generatedAtTime, t2}
:g4 {...} {:g4, prov:generatedAtTime, t3}

    

Two RDF streams S1 and S2 are B-isomorphic if and only if there is a bijection M between the nodes, triples, graphs, named graphs, and timestamped graphs that occur in S1 and those that occur in S2 such that:

1. M maps blank nodes to blank nodes;
2. M is the identity map on literals and IRIs;
3. For every triple <s p o>, M(<s, p, o>)= <M(s), M(p), M(o)>;
4. For every graph G={t1, ..., tn}, M(G)={M(t1), ..., M(tn)};
5. For every named graph NG=<n, G>, M(NG)=<M(n), M(G)>;
6. For every timestamped graph TSG where NG is the named graph and DG is the default graph containing the timestamp triple TST, M(TSG) is a timestamped graph TSG2, with named graph M(NG), default graph M(DG) and timestamp triple M(TST).;
7. For every i ≥ 1, M(S1(i))=S2(i), where S1(i) is the i-th element of S1 and S2(i) is the i-the element of S2.

An RDF stream is viewed as being on a single "RDF surface"(see [[BLOGIC]]), so that blank nodes may be shared between any graphs in the stream. For this reason, B-isomorphism is defined in terms of a single mapping M for the entire RDF stream rather than, say, separate mappings for each timestamped graph.

Two RDF streams are isomorphic if there exists an RDF stream that is both B-isomorphic to one stream and S-isomorphic to the other stream.

RDF streams that are S-isomorphic are isomorphic.

RDF streams that are B-isomorphic are isomorphic.

Isomorphic RDF streams MUST have the same semantics. The semantics of RDF streams is affected by the result of applying window functions () as well as by entailment. Therefore, isomorphic RDF streams SHALL be indistinguishable, up to isomorphism, with respect to entailment (in any entailment regime), as well as with respect to the application of window functions.

Substreams and Windows

A substream S' of an RDF stream S is an RDF stream that is isomorphic to a subsequence of S.

There are several specializations of the substream relation which are useful in practice. These include the filter relation, where stream elements are selected based on satisfaction of some criterion, and the window relation, where a temporally contiguous portion of the stream is selected.

A window S' of an RDF stream S is a substream of S such that if S'(i) and S'(j) are two elements of S' and S'(i) ≲ S'(j) (i.e., S'(j) covers S'(i)), and further if S'(i) ≲ S(k) ≲ S'(j) for some element S(k) of S, then S(k) is an element of S'.

Informally, a window is a temporally-contiguous selection from the original stream, without gaps.

Time-based Window Functions

Because the time plenum for each timestamp predicate is partially ordered, we may define a temporal interval of a timestamp predicate to be an interval, in the usual sense for partial orders, within its time plenum.

Recall that intervals need not be bounded and need not be closed, and are specified in terms of two, one or zero inequality conditions based on the partial order or its induced strict order.

A general time-based window function w is a general window function specified by a finite set wP of timestamp predicates together with temporal intervals wJ(P) of each timestamp predicate P in wP, such that for every stream S, an element S(i) of S is an element of w(S) if and only if the timestamp predicate P of S(i) is in P and the timestamp t of S(i) is contained in wJ(P).

A time-based window function is the restriction of a general time-based window function to a subset of RDF streams.

The substream resulting from the application of a time-based window function is time-bounded.

Temporal-count-based Window Functions

A general temporal-count-based window function w is a general window function specified by a finite set wP of timestamp predicates together with semi-infinite temporal intervals wJ(P) of each timestamp predicate P in wP with endpoints wT(P), and positive integers wN(P), for each timestamp predicate P in wP such that for every stream S, an element S(i) of S is an element of w(S) if and only if the timestamp predicate P of S(i) is in P and

• t is the timestamp of S(i),
• T(S, P, w) is the set of temporal entities that are timestamps for elements of S with timestamp predicate P, belong to wJ(P), and belong to the closed interval between t and wT(P), and
• the cardinality of T(S, P, w) is less than or equal to wN(P)

A temporal-count-based window function is the restriction of a general temporal-count-based window function to a subset of RDF streams.

The substream resulting from the application of a temporal-count-based window function is temporal-count-bounded.

Due to the potential for stream elements with incomparable or duplicate timestamps, the number of elements in the substream having a particular timestamp predicate is not guaranteed to be equal to the depth specified for the predicate by the temporal-count-based window.

Temporal-count-based window functions with future-facing orientation on timestamp predicates whose time plenum is not totally-ordered are not computable, because in general it is not possible to know, at any point in the reception of the stream, whether there are further elements of the stream that would be selected by the temporal-count-based window function.

Applications that require a substream with an exact number N of elements for a specified timestamp predicate might apply a temporal-count-based window function with N for the count of temporal entities, and then randomly discard extra elements, according to some criterion, e.g., extreme elements (maximal or minimal, depending on the orientation of the counting). However, this extra step causes the process to be nondeterministic, and hence does not correspond to a function. If elements are discarded in a nonrandom fashion, e.g., based on their order in the stream sequence, then this would be a function, but would not preserve isomorphism, and so would not be a window function. The issue of obtaining a window function that returns an exact number of elements (for a particular predicate) is handled in the next section, where we define the concept of window relation, and use it to define an element-count-based window relation. When restricted to certain kinds of RDF streams, element-count-based window relations are functional so element-count-based window functions can be defined on such subsets. This and similar considerations, of importance to implementations, motivate the RDF Stream profiles as subsets of RDF streams.

Window Relations

A window relation is a binary relation on RDF streams (a relation having an extension which is a set of pairs of RDF streams) such that the second element in the pair is a window of the first element and preserves isomorphism. That is, if <S1, S2> is a member of the extension of a window relation W, and S3 and S4 are isomorphic to S1 and S2, resp., then <S3, S4> is also a member of the extension of W.

A length-based window relation W is a window relation specified by a set of streams WS, a finite set WP of timestamp predicates together with the following parameters for each timestamp predicate p in WP:

• a semi-infinite temporal interval WJ(P) of timestamp predicate P (the interval of P);
• a temporal entity WT(P) which is the finite endpoint of WJ(P) (the temporal reference of P);
• a positive integer WN(P) (the length for P)

• the timestamp predicate P of S'(i) is in WP, and
• the timestamp t of S'(i) is in WJ(P).

A length-based window function W on domain WS is a length-based window relation where any member <S, S'> of its extension are such that S is in WS and W defines a total function on WS.

The names "element-count-bounded window relation" and "element-count-bounded window function" have been proposed, as a replacement of "length-bounded ...". This nomenclature depends on the adoption of "element" as the term for the individual timestamped graphs in a stream.

RDF Time-Series Profiles

This section describes four profiles which are defined through restrictions on the default graphs of the stream's timestamped graph elements or on the relation between timestamp values:

• RDF time series
• RDF distinct time series
• RDF regular time series
• RDF distinct regular time series

RDF Linked-List Profiles