Algebraic Operations on Spatiotemporal Data Based on RDF

Abstract

In the context of the Semantic Web, the Resource Description Framework (RDF), a language proposed by W3C, has been used for conceptual description, data modeling, and data querying. The algebraic approach has been proven to be an effective way to process queries, and algebraic operations in RDF have been investigated extensively. However, the study of spatiotemporal RDF algebra has just started and still needs further attention. This paper aims to explore an algebraic operational framework to represent the content of spatiotemporal data and support RDF graphs. To accomplish our study, we defined a spatiotemporal data model based on RDF. On this basis, the spatiotemporal semantics and the spatiotemporal algebraic operations were investigated. We defined five types of graph algebras, and, in particular, the filter operation can filter the spatiotemporal graphs using a graph pattern. Besides this, we put forward a spatiotemporal RDF syntax specification to help users browse, query, and reason with spatiotemporal RDF graphs. The syntax specification illustrates the filter rules, which contribute to capturing the spatiotemporal RDF semantics and provide a number of advanced functions for building data queries.

1. Introduction

The Resource Description Framework (RDF) [1] was originally designed as a metadata model to publish or exchange data on the Semantic Web, and has since become the W3C standard. Recently, it has been used as a general method for conceptual description, and some researchers have started to focus on spatiotemporal data modeling and algebraic operations.

Towards spatiotemporal data modeling, there have been some achievements in representing spatiotemporal entities, such as a temporal data model [2,3], a spatial data model [4], and a spatiotemporal data model [5]. In previous studies on temporal data modeling, Tappolet et al. [6] present a syntax and storage format based on named graphs to express a temporal RDF. Due to the fact that all entities can be linked with relations through labels, Hernández et al. [7] put forward an approach that adds temporal qualifiers and values to the RDF model representation in the form of labels. In this approach, the RDF triples are expanded into a five-tuple (s, p, o, q, v), where (s, p, o) refers to the primary relation, q is the temporal qualifier property, and v is the temporal qualifier value. Besides this, there are some models that add temporal labels to RDF triples to form quads [8,9]. In addition to temporal models, there are some studies about spatial RDF modeling. For example, GeoRDF [10] is an RDF-compatible profile for describing geometric information (points, lines, and polygons). In GeoRDF, GeoMetadataOverSvg is the geographic information notation, which plays a significant role in the spatial data connection of the Semantic Web. Benefiting from that, GeoRDF can be used to represent any point on the Earth. Regarding spatiotemporal data, the structured spatiotemporal RDF was first proposed by Koubarakis et al. [11]. It develops the stRDF data model based on RDF and puts forward the stSPARQL query language. The contribution of stRDF is regulating the representation principle of spatiotemporal data in RDF and standardizing the spatiotemporal data querying. It can also be applied to several spatiotemporal-related applications [12,13,14]. However, the spatial information fails to associate with temporal information in the stRDF model, which means that it has a weak ability to record dynamically changing data. When the knowledge graph is updating, the changes in spatiotemporal attribute values cannot be captured in time and lead to inconsistencies in the data. Moreover, it will probably return multiple results or errors when we query it for the spatial information at a given time.

With the prompt development of RDF graph querying [6,15], graph algebra has received widespread attention. It is the key to applying standard database-style optimization to queries. In previous studies, several different RDF algebras have been proposed by research groups coming from academia. Due to the lack of an RDF algebra, such query languages use APIs to describe their semantics, and optimization issues have been mostly neglected. To solve this problem, Frasincar et al. [16] propose RAL (an RDF algebra) as a reference mathematical study for RDF query languages. Robertson [17] proposes an algebraic operation of triadic relations for the RDF. An important aspect of this algebra is an encoding of triples, which implements a kind of reification. Chen et al. [18] incorporate semantics that inference into query answering and propose an RDF algebra based on a layered RDF graph model. The matrix algebra method MAGiQ was put forward by Jamour et al. [19]. MAGiQ represents an RDF graph as a sparse matrix, and translates SPARQL queries to matrix algebra programs, which takes advantage of the existing software infrastructure to process sparse matrices and is optimized for many architectures (e.g., central processing units (CPUs), graphical processing units (GPUs), and distributed architectures) effortlessly. On the basis of previous work, Thakkar et al. [20] consolidate existing graph algebra operators from the literature and propose two new traversal operators in an integrated graph algebra. Although researchers have proposed a lot of algebraic methods to assist with RDF queries, these methods or models cannot support spatiotemporal RDF queries. Therefore, it is necessary to develop a relatively complete spatiotemporal RDF graph algebra.

Motivated by such an observation, in this paper, we study algebraic operations and a spatiotemporal syntax specification based on the RDF. We: (i) present a general algebraic operational framework for manipulating spatiotemporal data, which can represent the content of data more clearly and support spatiotemporal RDF graphs specifically; and (ii) propose a spatiotemporal RDF syntax specification. It will be of great benefit to query explicit spatiotemporal RDF data and capture spatiotemporal RDF semantics.

The remainder of this paper is organized as follows. Section 2 presents related work. In Section 3, spatiotemporal algebraic operations based on the RDF are proposed. Section 4 explores the spatiotemporal RDF syntax specification, and Section 5 presents our conclusions and future work.

2. Related Work

As it contributes a lot to optimizing queries, algebra has been identified as a core operation in querying. The research results that are presented in this section mainly include works about spatiotemporal algebra and the algebra of RDF graphs.

2.1. Algebra for Spatiotemporal Data

With the emergence of a large amount of spatiotemporal data, researchers began to devote themselves to the study of spatiotemporal algebra. To support spatial features, Córcoles et al. [21] present the Geography Markup Language (GML) based on XML. It inherits the interoperability of the XML and allows for the exchange of geographic information on the Web, and an extension to algebraic operations is provided on the basis of GML and a query language. Towards temporal data, Pan et al. [22] represent temporal aggregates in OWL-Time, and propose a systematic way of mapping iCalendar recurrence sets to OWL-Time temporal sequences. Baratis et al. [23] propose a four-dimensional (4D)-Fluent representation that represents temporal information in OWL, where concepts varying in time are represented as 4D objects, and put forward the TOQL query language. Batsakis et al. [2] enhance this approach with qualitative temporal expressions allowing for the representation of temporal intervals with unknown starting and ending points by means of their relation (e.g., “before” and “after”) to other time intervals. To handle qualitative temporal relationships and the extended 4D-Fluent representation, they also extend the TOQL query language. In [24], Moffitt et al. combine advances in graph databases and temporal relational databases. Then, they propose an algebra called TGA that adheres to point-based semantics. TGA includes principled temporal generalizations of conventional graph operators as well as novel operators that support exploratory analysis of evolving graphs at different levels of temporal and structural granularity. Aiming to perform operations over spatiotemporal data, Perry et al. [25] study geospatial and temporal semantic analytics and Hakimpour et al. [26] present practical approaches to data processing in the space, time, and theme dimensions using existing Semantic Web technologies. Perry et al. [27] devise SPARQL-ST to support spatiotemporal queries based on SPARQL. Bai et al. [28] develop an algebra based on Native XML to manipulate spatiotemporal XML data. In this work, the logical structure of a spatiotemporal database, data type systems, and querying operations were investigated. Bai et al. [29] deal with fuzzy information and propose an algebra for fuzzy spatiotemporal data in XML.

2.2. Algebra of RDF Graphs

There is a rich set of studies on RDF graph algebra. For instance, an algebraic operation of triadic relations for RDF is introduced in [17]. Jamour et al. [19] propose a matrix algebra method to answer RDF graph queries. Frasincar et al. [16] propose a prototype of an RDF algebra, including three types of operations: the first is the extraction operation, the second is the loop operation, and the third is the model construction operation. However, RAL does not support RDF graph structure queries. Chen et al. [18] introduce a set of operations for manipulating RDF graphs and an RDF query algebra (LAGAR) is proposed. LAGAR includes four operations: pattern-matching operations, construction operations, graphics set operations, and related functional operations, and this algebra optimizes RDF graph model matching operations. The use of a relational algebra for SPARQL query processing is investigated in [30], in which the transformation from SPARQL into an abstract relational algebra is presented and the differences between the semantics of SPARQL and that of the relational model are discussed. GeoSPARQL [31] attempts to unify data access for the geospatial Semantic Web. Battle et al. [32,33] describe the motivation for GeoSPARQL and the implementation of GeoSPARQL. In order to better manage fuzzy data, Zuo et al. [34] introduce a picture fuzzy graph based on a picture fuzzy relation, and describe the utility of the picture fuzzy graph. Ma et al. [35] put forward a fuzzy RDF model. In addition, a fuzzy RDF algebra is formally proposed and a set of algebraic operations is developed. To rewrite algebra expressions in a form that satisfies certain needs, they also present some algebraic equivalences based on a data graph isomorphism. Because the interval type 2 fuzzy set (IT2FS) increases the number of degrees of freedom to express uncertainty in the edge weight and has a greater capacity to describe fuzzy information in a logically correct manner, Dey et al. [36] propose the minimum spanning tree problem with an undirected connected weighted interval type 2 fuzzy graph (FMST-IT2FS), which can be used to optimize the query of fuzzy RDF graphs. Besides this, several RDF graph algebras are proposed to deal with specific domains, such as querying a large-scale distributed triple-store system [37] and optimizing RDF graph pattern matching in MapReduce [38].

In recent years, some query methods based on the spatiotemporal RDF have been developed, including stSPARQL [11], SPARQL-ST [27], g^st-store [39], and ST-SPARQL [40]. Koubarakis et al. [11] propose the query language stSPARQL, which is an extension of SPARQL. Compared with SPARQL, it has the ability to query spatiotemporal attributes. The main statements are the SELECT statement, the Filter statement, and the Having statement. Since stRDF cannot dynamically connect spatiotemporal data, it is difficult to use stSPARQL to query large-scale dynamic spatiotemporal data. Perry et al. [27,41] describe a framework built over the RDF metadata model for analysis of thematic, spatial, and temporal relationships between named entities, and then present a formal syntax and semantics for SPARQL-ST based on the formalization of the SPARQL syntax given by [42]. In addition, Perry et al. [43] also give an overview of GeoSPARQL’s implementation in Oracle Spatial and Graph and show how to load, index, and query spatial RDF data. Wang et al. [39,44] present a spatiotemporal-information-integrated RDF data management system called g^st-Store and introduce a spatiotemporal query language that extends the SPARQL language with spatiotemporal assertions to query spatiotemporal-information-integrated RDF data. In [40], the authors put forward a spatiotemporal data type that adds spatial data on Geo-ontology to temporal data. They suggest that it should be applied in ST-OW because using the ST-ontology, which has been added to the temporal data in the semantic Web service, will make available new information for various inferences and queries.

However, the algebraic operations of the abovementioned RDF graph are mainly used for the traditional RDF dataset, which cannot handle a complex spatiotemporal RDF dataset. Therefore, this paper aims to extend the traditional RDF graph operation and establish an RDF graph algebra for spatiotemporal data.

3. Spatiotemporal RDF Semantics and Graph Algebra

In this section, we explore the spatiotemporal RDF semantics and graph algebra of spatiotemporal knowledge graphs.

3.1. Spatiotemporal RDF Semantics

In the following, we further study the semantics of the spatiotemporal RDF. Before that, we propose a spatiotemporal RDF model called stRDFS. stRDFS is defined as follows:

Definition 1.

Given a URI set R, an empty vertex set B, a text description set K, a temporal data set I, and a spatial data set S, an stRDFS expression is g (s, p: <t, l>, o), where:

●

s is a resource name and s ∈ R ∪ B.

●

p is a property name and p ∈ R.

●

o is a value and o ∈ R ∪ B ∪ K ∪ I ∪ S.

●

t ∈ I is temporal data.

●

l ∈ S is spatial data.

In Definition 1, to solve the problem of data inconsistencies in stRDF, we add spatial labels and temporal labels to the predicate to associate spatial data with temporal data to form a spatiotemporal predicate p. When spatiotemporal data change, spatiotemporal attributes associated with them will change as well.

Definition 2.

Given an stRDFS expression g (s, p: <t, l>, o), U = {f_s-o, f_s-t, f_s-l, f_p-t, f_p-l} is a mapping set of g, the value range of mapping f_x-y is denoted as Range (f_x-y), where Range (f_x-y) = y, and an stRDFS graph for g is a labeled graph G (V, E, F, λ, T, L), where:

●

V = s ∪ Range (U) is the set of vertexes.

●

E = {(r, r’)} is the set of edges from r to r’, where ∀r, r’ ∈ V.

●

F (r, r’) = {f | (r, f: <t, l>, r’) ∈ G} is the set of mappings of E, where ∀r, r’ ∈ V*.

●

λ is the set of labels given by vertexes or edges.

●

T ∈ Range (f_s-t ∪ f_p-t).

●

L ∈ Range (f_s-l ∪ f_p-l).

In Definition 2, f is a mapping relationship. f_s-o represents the mapping, whose function is expressed as an attribute name, from s to o. The mapping f_s-t indicates that s is linked with temporal data, and the formed triple is (s, p, t). In (s, p, t), the property represents “temporal information” and the attribute value t represents temporal data. The mapping f_s-l indicates that s is linked with spatial data and the expression is (s, p, l). In the triple, the attribute represents “spatial information” and the attribute value l represents spatial data. The mapping f_p-t indicates that p is linked with temporal data and combines with the other mappings to form an stRDFS tuple. When f_p-t is combined with f_s-o, the formed tuple is (s, p: t, o), indicating that the temporal data describe the valid time of (s, p, o). When f_p-t is combined with f_s-t, the formed tuple is (s, p: t₂, t₁), indicating that the valid time of s is t₁, and the valid time of the tuple (s, p, t₁) is t₂. When f_p-t is combined with f_s-l, a tuple (s, p: t, l) is formed, indicating that s is linked with spatial data l, and the valid time of tuple (s, p: t, l) is t. The mapping f_p-l represents that p is linked with spatial data and combines with other mappings to form an stRDFS tuple. When f_p-l is combined with f_s-o, the formed tuple is (s, p: l, o), indicating that the spatial data l describes (s, p, o). When f_p-l is combined with f_s-t, the formed tuple is (s, p: l, t), indicating that the valid time of s is t, and the spatial data of (s, p, t) is l. When f_p-l is combined with f_s-l, a tuple (s, p: l₂, l₁) is formed, indicating that s is linked with the spatial data of l₁, and the spatial data of (s, p, l₁) is l₂. The mapping f_p-o is illegal. The f_o-t and f_o-l logically represent the temporal data and spatial data of o, respectively. In the stRDFS structure, f_o-t and f_o-l are converted into f_s-t and f_s-l, and they can appear as separate tuple mappings. For instance, (s₁, p, o: t) can be converted into two tuples (s₁, p₁, o) and (s₂, p₂, t), where s₂ = o and p₂ represents “temporal information”. Similarly, (s₁, p, o: l) can be converted into two tuples (s₁, p₁, o) and (s₂, p₂, l), where s₂ = o and p₂ represents “spatial information”.

According to Definition 2, there are two cases. The first one is that stRDFS graph vertexes contain spatiotemporal information, in this case T ∈ Range (f_s-t) and L ∈ Range (f_s-l), as shown in Figure 1a. The second case is that the stRDFS graph edges contain spatiotemporal information, in this case T ∈ Range (f_p-t) and L ∈ Range (f_p-l), as shown in Figure 1b.

Definition 3.

Given two stRDFS graphs G₁ and G₂, the implication relation of G₁ and G₂ is as follows:

●

When G₁, G₂ are stRDFS basis graphs, G₁ |= G₂ only if G₁ (Ti) |= G₂ (Ti) and G₁ (Si) |= G₂ (Si).

●

When G₁, G₂ are stRDFS graphs, G₁ |= G₂ only if μ₁ (G₁) for every base graph instance of G₁, there exists a base graph instance μ₂ (G₂) of G₂ and μ ₁ (G₁) |= μ₂ (G₂).

Here, |= denotes the implication relation and μ represents the mapping of entities to attribute values. The closure of figure G can be expressed as G’. ∪ _{(Si ∪ Ti)} G (Si ∪ Ti) is the underlying stRDFS graph of the stRDFS graph G, the union of the graphs G (Si ∪ Ti), and the subgraphs of G.

Definition 4.

Given an stRDFS graph G, the largest set and block closure are defined as follows.

●

G’ is the largest set on universe (G) that adds all RDF vocabularies, which can be expressed as tcl (G), where G ⊆ G’ or G |= G’.

●

The block closure of G is expressed as scl (G). It is a spatiotemporal RDF graph defined by ∪_{Si, Ti} (cl(G (Si ∪ Ti)) ^{Si, Ti}, where cl(G (Si ∪ Ti) is an arbitrary closure of the RDF graph G_{(Si ∪ Ti)}.

Theorem 1.

For two stRDFS graphs G₁ and G₂, a necessary and sufficient condition of G₁ |= _{(Si ∪ Ti)} G₂ is that there is a mapping from G₂ to scl (G₁).

Proof of Theorem 1.

 

Sufficiency. Define μ as a mapping from G₂ to scl(G₁). μ₁(G₁) is an example of a base graph, such that μ₂ = μ ○ μ₁. We can obtain the conclusion that for any temporal function Ti and any spatial function Si, there is μ₂G₂ (Si ∪ Ti) ⊆ μ₁(cl(G₁)) (Si ∪ Ti) and ∀Si, ∀Ti, μ₁(G₁) (Si ∪ Ti) |= _{(Si ∪ Ti)} μ₂(G₂) (Si ∪ Ti). Therefore, μ₁(G₁) |= _{(Si ∪ Ti)} μ₂(G₂).

Necessity. Define μ₁ as the mapping from any variable X in G₁ to a different constant C_x. Make μ₂(G₂) an example of a basic graph, ∀Si, ∀Ti, μ₁(G₁) (Si ∪ Ti) |=_{(Si ∪ Ti)} μ₂(G₂) (Si ∪ Ti). It is easy to see that ∀ Ti, ∀ Si, μ₂G₂ (Si ∪ Ti) ⊆ μ₁(cl (G₁)) (Si ∪ Ti). μ₂G₂ ⊆ ∪ _{(Si ∪ Ti)} (cl (μ₁ (G₁) (Si ∪ Ti)))^{(Si ∪ Ti)}. Therefore, μ₂ is a mapping from G₂ to scl(G₁). □

Theorem 2.

Given three stRDFS graphs A (V_A, E_A, F_A, T_A, L_A), B (V_B, E_B, F_B, T_B, L_B), and C (V_C, E_C, F_C, T_C, L_C), an isomorphism from A to B is a bijective function h: V_A → V_B and it is an equivalence relation.

Proof of Theorem 2.

 

Reflexivity. Consider the identity map h: V → V such that ∀s ∈ V, h(s) = s. h is a bijective mapping satisfying ∀s ∈ V, T(s) = T(h(s)), and L(s) = L(h(s)). Hence, h is an isomorphism of the spatiotemporal graph to itself. Therefore, it possesses reflexivity.

Symmetry. Consider the identity mapping h: V_A → V_B such that h (s_A) = s_B, s_A ∈ V_A satisfying T_A (s_A) = T_B (h(s_A)) and L_A (s_A) = L_B (h(s_A)). As h is bijective by h(s_A) = s_B, s_A ∈ V_A, then h⁻¹(s_B), ∀s_B ∈ V_B. Therefore, s_A ∈ V_A, T_A (s_A) = T_B (h(s_A)), then T_A (h⁻¹(s_B)) = T_B (s_B) (∀s_B ∈ V_B). Additionally, s_A ∈ V_A, L_A(s_A) = L_B(h(s_A)), then L_A (h⁻¹(s_B)) = L_B(s_B) (∀s_B ∈ V_B). Therefore, we obtain h⁻¹: V_B → V_A, which is isomorphic from B to A.

Transitivity. Suppose that h₁: V_A → V_B and h₂: V_B → V_C are isomorphisms of A onto B and B onto C, respectively. As h₁ is a bijective map h₁ (s_A) = s_B, s_A ∈ V_A satisfies T_A (s_A) = T_B (h(s _A)), ∀ s_A ∈ V_A, and L_A (s_A) = L_B (h(s_A)). In the same way, h₂ (s_B) = s_C, s_B ∈ V_B satisfies T_B (s_B) = T_C (h(s_B)), ∀s_B ∈ V_B, and L_B (s_B) = L_C (h(s_B)). From what has been discussed above, we draw the conclusion that T_A (s_A) = T_B (s_B) = T_C (s_C) and L_A (s_A) = L_B (s_B) = L_C (s_C).

Hence, h₂ ○ h₁ is an isomorphism between A and C. It satisfies transitivity.

In conclusion, the isomorphism between spatiotemporal RDF graphs is an equivalence relation. □

3.2. Spatiotemporal Classes and Descriptions in the Spatiotemporal Domain

In order to introduce the stRDFS description more clearly, we introduce several main classes: strdfs: SpatialObject, strdfs: SpatialGeometry, strdfs: SpatialFeature, strdfs: TemporalObject, strdfs: TimeSlice, strdfs: TemporalFeature, strdfs: SpatiotemporalObject, strdfs: SpatiotemporalGeo, and strdfs: SemiLinearPointSet. Their relations are shown in Figure 2.

The class strdfs: SpatialObject represents a set of all entities with only spatial information. Its subclass strdfs: SpatialGeometry describes parameter Si in the stRDFS model (s, p: <Ti, Si>, o), including the data on latitude, longitude, and altitude, and the other subclass strdfs: SpatialFeature describes landform, terrain, and so on. The class strdfs: TemporalObject is a set of all entities that contain temporal data. Its subclass strdfs: TimeSlice describes parameter Ti in the stRDFS model (s, p: <Ti, Si>, o), and the other subclass strdfs: TemporalFeature includes other temporal data on temporal entities, such as a time zone, a tense, a time dimension, or the time of existence. The class strdfs: SpatiotemporalObject is a set of all spatiotemporal entities, which is a superset of strdfs: TemporalObject and strdfs: SpatialObject. The class strdfs: SpatiotemporalGeo describes geometric data of spatiotemporal entities and it is a superset of strdfs: SpatialGeometry and strdfs: TimeSlice. The class strdfs: SemiLinearPointSet is the set of rational numbers that represent time values, longitude values, latitude values, altitude values, etc.

For example, there is a large sonic receiver that calls corresponding programs to analyze sound waves after receiving them. The software class has the instances Program1 and Program2, whose types are JavaProgram and PythonProgram, respectively. The receiver class has the instances Receiver1 and Receiver2, and Receiver2’s type is SoundWaveReceiver. We compare the stRDF model and the stRDFS model by describing the spatiotemporal information. The stRDF model is as follows:

ex: program1	rdf: type	ex: JavaProgram
ex: program2	rdf: type	ex: PythonProgram
ex: program1	om: procedure	ex: CountProgram
ex: program2	om: procedure	ex: OutputProgram
ex: program1	om: hasPro1Call	ex: receiver2
ex: program2	om: hasPro2Call	ex: receiver2
ex: receiver2	rdf: type	ex: SoundWaveReceiver
ex: receiver2	ssn: measures	ex: sound
ex: receiver2	ssn: hasLocation	ex: location1
ex: location1	strdf: hasTrajectory	“(t = 8t and t = 18t or 9t ≤ t ≤ 14t) and k = 0t and ((20.9°N < L < 21°N and 45.8°E < D <= 46°E) or (L = 21°N and D = 46°E))” ^^ strdf: SemiLinearPointSet.

In the stRDF model, strdf: hasTrajectory describes the spatiotemporal data, which is considered to be the attribute value of strdf: hasTrajectory for Location1. In the stRDF model, only spatiotemporal data on whole entities can be recorded in the spatiotemporal dimension, while the spatiotemporal data on a certain part of the object cannot. For example, the stRDF model cannot represent the spatial data at t = 8t and record the temporal data when the object is in position (L = 21°N and D = 46°E). At the same time, if an attribute value changes at a certain time or in a certain spatial position, stRDF will record inaccurate data. The stRDFS model solves this problem as follows:

ex: program1	rdf: type	ex: JavaProgram
ex: program2	rdf: type	ex: PythonProgram
ex: program1	om: procedure	ex: AnalysisProgram
ex: program2	om: procedure	ex: AnalysisProgram
ex: program1	om:hasPro1Call	ex: receiver2
ex: program2	om: hasPro2Call	ex: receiver2
ex: receiver2	rdf: type	ex: SoundWaveReceiver
ex: receiver2	ssn: measures	ex: sound
ex: receiver2	ssn: hasLocation1	ex: location1
ex: receiver2	ssn: hasLocation2	ex: location2
om: hasPro1Call	strdfs: SpatiotemporalGeo	“t = 8 t and t = 18t and k = 0t and (20.9°N < L < 21°N and 45.8°E < D <= 46°E)” ^^ strdfs: SemiLinearPointSet
om: hasPro2Call	strdfs: SpatiotemporalGeo	“9t ≤ t ≤ 14t and L = 21°N and D = 46°E and k = 0t” ^^ strdfs: SemiLinearPointSet
ssn: hasLocation1	strdfs: SpatialGeometry	“(20.9°N < L < 21°N and 45.8°E < D <= 46°E)” ^^ strdfs: SemiLinearPointSet
ssn: hasLocation2	strdfs: SpatialGeometry	“(L = 21°N and D = 46°E)” ^^ strdfs: SemiLinearPointSet

At Location1, when t = 8t and t = 18t, the receiver calls Program1 to analyze the data. At Location2, when t ∈ [9t, 14t], the receiver calls Program2 to analyze the data. In the stRDFS model, spatiotemporal data are used to describe om: hasPro1Call and om: hasPro2Call, which facilitates the modification of common attribute values, such as program names. Based on this feature, the stRDFS model can represent spatiotemporal data and record changes in spatiotemporal attributes at any time or in any location.

We define 11 kinds of topological relations to describe the relations among spatiotemporal entities: Equal, Disjoint, Meet, Overlap, Cover, CoveredBy, Inside, Contain, Before, Now, and After. The corresponding domains are shown in

Table 1. Topological relations among spatiotemporal classes.

Relation Name	Relation URI	Domain/Range
Equals	strdfs: geoEquals	strdfs: SpatialObject
Disjoint	strdfs: geoDisjoint	strdfs: SpatialObject
Meet	strdfs: geoMeet	strdfs: SpatialObject
Overlap	strdfs: geoOverlap	strdfs: SpatialObject
Covers	strdfs: geoCovers	strdfs: SpatialObject
CoveredBy	strdfs: geoCoveredBy	strdfs: SpatialObject
Inside	strdfs: geoInside	strdfs: SpatialObject
Contains	strdfs: geoContains	strdfs: SpatialObject
Before	strdfs: timBefore	strdfs: TemporalObject
Now	strdfs: timNow	strdfs: TemporalObject
After	strdfs: timAfter	strdfs: TemporalObject

.

3.3. Spatiotemporal RDF Graph Algebra

This subsection introduces five types of stRDFS graph algebras: union, intersection, difference, Cartesian product, and filter. In order to make these operations suitable for the model proposed in this paper, we improve the union, intersection, difference, and Cartesian product operations to provide solutions when the relationship between two points does not necessarily exist and add a filter operation to meet the specified requirements. These stRDFS graph algebras are sufficient and can satisfy the known operations. We provide an example in Figure 3 to show the algebraic process for stRDFS graphs by the method proposed in this paper.

Definition 5.

Given two stRDFS graphs A (V_A, E_A, F_A, T_A, L_A) and B (V_B, E_B, F_B, T_B, L_B), the union of A and B is defined as A ∪ B = (V, E, F, T, L), where:

●

V = V_A ∪ V_B

●

E = E_A ∪ E_B

●

F = F_A ∪ F_B

●

Π_NT = Π_N T_A ∪ Π_N T_B

●

Π_kT = min(Π_N T_A, Π_N T_B)

●

L = L_A ∪ L_B.

In Definition 5, Π_N/k (x) represents the projection of x on N/k, where N = [t_s(f), t_e(f)] is the valid time and k = t_r(f) is the reference time recorded at present. In N = [t_s(f), t_e(f)], t_s(f) represents the start time of mapping f_vi-vj, and t_e(f) represents the terminal time of mapping f_vi-vj. min represents the minimum reference time. The stRDFS graph requires that the reference time in the temporal data for each edge and each node must be consistent. When the union operation is performed over two stRDFS graphs, the reference time of the two graphs must be consistent. For convenience of description, we uniformly selected the minimum reference time as the reference time of the resulting graph.

As shown in Figure 3, there are two stRDFS graphs (a) and (b), and we performed the union operation in Definition 5 to obtain the graph (c). The solid line indicates that the relationship between two points must exist, and the dotted line indicates that the relationship between the two points does not necessarily exist.

Definition 6.

Given two stRDFS graphs A (V_A, E_A, F_A, T_A, L_A) and B (V_B, E_B, F_B, T_B, L_B), the intersection of A and B is defined as A ∩ B = (V, E, F, T, L), where:

●

V = V_A ∩ V_B

●

E = E_A ∩ E_B

●

F = F_A ∩ F_B

●

Π_NT = Π_N T_A ∩ Π_N T_B

●

Π_kT = min (Π_N T_A, Π_N T_B)

●

L = L_A ∩ L_B.

As shown in Figure 3, there are two stRDFS graphs (c) and (d), and we performed the intersection operation in Definition 6 to obtain the graph (e).

Definition 7.

Given two stRDFS graphs A (V_A, E_A, F_A, T_A, L_A) and B (V_B, E_B, F_B, T_B, L_B), the difference of A and B is defined as A − B = (V, E, F, T, L), where:

●

E = E_A − E_B

●

V is the set of vertexes of E.

●

F is the set of mappings of E.

●

T is the temporal dataset of F.

●

L is the spatial dataset of F.

However, the algebraic operations of the abovementioned RDF graph are mainly used for the traditional RDF dataset, which cannot handle a complex spatiotemporal RDF dataset. Therefore, this paper aims to extend the traditional RDF graph operation and establish an RDF graph algebra for spatiotemporal data.

As shown in Figure 3, we can obtain graph (f) using Definition 7 with the difference of the two stRDFS graphs (d) and (a).

Definition 8.

Given two stRDFS graphs A (V_A, E_A, F_A, T_A, L_A) and B (V_B, E_B, F_B, T_B, L_B), the Cartesian product of A and B is defined as A × B = (V, E, F, T, L), where:

●

V = V_A × V_B

●

E = {(u, u₂)(u, v₂)| u ∈ V_A, u₂ v₂ ∈ E_B} ∪ {(u₁, ω)(v₁, ω)| ω ∈ V_B, u₁ v₁ ∈ E_A}

●

F is the set of mappings of E.

●

T is the temporal dataset of F.

●

L is the spatial dataset of F.

There are two stRDFS graphs (g) and (h) in Figure 3. We can obtain graph (i) with their Cartesian product using Definition 8.

Theorem 3.

Given two stRDFS graphs A (V_A, E_A, F_A, T_A, L_A) and B (V_B, E_B, F_B, T_B, L_B), we have the following.

●

A ∪ B is an stRDFS graph.

●

A ∩ B is an stRDFS graph.

●

A − B is an stRDFS graph.

●

A × B is an stRDFS graph.

Definition 9.

(stRDFS graph pattern). An stRDFS graph pattern is defined as P = (V_P, E_P, F_P, T_P, L_P, Re), where:

●

V_P is a finite set of vertexes.

●

E_P is a finite set of directed edges.

●

F_p is the set of mappings of E_p.

●

T_P is a temporal dataset.

●

L_P is a spatial dataset.

●

R_e = {R₁R₂, R₁|R₂, R+, ε} is a set of filter rules describing E_p, where R represents a filter rule.

In practice, the stRDFS graph needs to be filtered according to certain rules so that the resulting graph meets the specified requirements. The stRDFS graph pattern described in Definition 9 represents the filter rules. In the program, the input is often filter rules and the stRDFS graph that needs to be processed, and the output is the resulting graph that satisfies specified requirements. According to the stRDFS graph filter rules, we can obtain the following conclusions: V_p is a vertex pattern abstracted from the rules and each vertex pattern corresponds to a set of vertexes in the filtered stRDFS graph. E_p is an abstraction of the attributes in the filter rules and each edge represents a type of edge of the stRDFS graph being filtered. F_p is an abstract collection of attribute names in the rule. T_p is the temporal dataset in the filter rules. Similarly, L_p is the spatial dataset in the filter rules. Re is regular expression and can have four forms: R₁R₂, R₁|R₂, R⁺, and ε. R₁R₂ is a concatenation of expressions that represents that two rules are next to each other. R₁|R₂ is an alternative of expressions that represents that filtering can be done by meeting one of the two rules. R⁺ denotes one or more occurrences of R. ε represents that there are no filter rules to filter stRDF graphs.

For example, consider an stRDFS graph pattern P, which models information concerning a writer (? w) who is born in A city, the fee for a book (? book) that the writer had written from 2016 to 2018 in A city, which is more than $10 (? f > $ 10), and the book’s genre, which is comedy. P can be expressed in the form of Figure 4.

Using the stRDFS graph G shown in Figure 5, we performed the filter operation in Definition 9. The result of spatiotemporal filtering of P and G is shown in Figure 6.

4. Spatiotemporal RDF Syntax Specification

In the stRDFS model, we define several topological relations to describe the relations among spatiotemporal entities and introduce five types of stRDFS graph algebras. However, stSPASQL does not define corresponding functions to deal with spatiotemporal data queries. While the queries contain the operations we proposed, stSPASQL cannot meet the requirements of the queries and needs to be improved. To solve this problem, we specify a spatiotemporal RDF syntax on the basis of stSPASQL [11]. The syntax proposed in this subsection is similar to the SQL syntax, and it is designed so that stRDFS format datasets can be easily accessed. It also provides a number of advanced functions for building more expressive queries that illustrate other filter conditions and then format the final output. The overall structure of the syntax is similar to that of SQL, which has three main parts represented by the uppercase keywords SELECT, FROM, and WHERE.

●

The keyword SELECT determines the specification of the query result. It is followed by the rest of the query: the list of identifiers of the query result.

●

The keyword FROM specifies the query’s scope, which is normally a spatiotemporal dataset or several stRDFS graphs.

●

The keyword WHERE represents the actual query and is followed by the query criteria, which are given by a pattern that corresponds to some stRDFS graphs replaced by variables. More complicated patterns are also allowed to be formed with some algebraic operators. This mode can be used not only to query a single spatiotemporal dataset but also multiple spatiotemporal datasets.

The function indicates the relations between the variables expressed by the FILTER statement, which is a part of the WHERE statement. In order to browse the spatiotemporal syntax, we define the spatial functions and temporal functions shown in

Table 2. Spatiotemporal functions.

Function	Type	Syntax format	Meaning
strdfs: distance	Spatial Function	FILTER (strdfs: distance(A, B))	Returns the shortest distance between A and B
strdfs: intersection		FILTER (strdfs: intersection (A, B))	Returns a geometric object that represents all points in the intersection of A and B
strdfs: union		FILTER (strdfs: union (A, B))	Returns a geometric object that represents all points in the union of A and B
strdfs: difference		FILTER (strdfs: difference (A, B))	Returns a geometric object that represents all points in the difference set of A and B
strdfs: spCartesian		FILTER (strdfs: spCartesian (A, B))	Returns a geometric object that represents all points in the Cartesian product set of A and B
strdfs: spfilter		FILTER (strdfs: spfilter (A, B))	Returns a geometric object that represents all points in the subgraph of A after filtering according to the pattern B
strdfs: spEquals		FILTER (strdfs: spEquals (?A, ?B))	The query result satisfies A = B
strdfs: spDisjoint		FILTER (strdfs: spDisjoint (?A, ?B))	The query result satisfies that A is disjoint with B
strdfs: spMeet		FILTER (strdfs: spMeet (?A, ?B))	The query result satisfies that A meets B
strdfs: spOverlap		FILTER (strdfs: spOverlap (?A, ?B))	The query result satisfies that A overlaps B
strdfs: spCovers		FILTER (strdfs: spCovers (?A, ?B))	The query result satisfies that A covers B
strdfs: spCoveredBy		FILTER (strdfs: spCoveredBy (?A, ?B))	The query result satisfies that A is covered by B
strdfs: spInside		FILTER (strdfs: spInside (?A, ?B))	The query result satisfies that A is inside B
strdfs: spContains		FILTER (strdfs: spContains (?A, ?B))	The query result satisfies that A contains B
strdfs:spEnvelope		FILTER (strdfs: spEnvelope (A))	Returns the minimum bounding box of A
strdfs: spBefore	Temporal Function	FILTER (strdfs: spBefore (?A, ?B))	The query result satisfies that A is earlier than B
strdfs: spNow		FILTER (strdfs: spNow (?A, ?B))	The query result satisfies that A and B are at the same time
strdfs: spAfter		FILTER (strdfs: spAfter (?A, ?B))	The query result satisfies that A is later than B

.

In order to demonstrate the application of the proposed functions, we provide some examples. Examples 1, 2, and 3 represent queries of spatial data, temporal data, and spatiotemporal data, respectively.

Example 1.

When we query the name and spatial data of a destroyed forest less than 0.1 km from a city, the syntax is as follows:

SELECT ?NAME ?FGEO

WHERE {

?R rdf: type noa: Region

?R strdfs: SpatialGeometry ?RGEO

?R noa: hasCorineLandCoverUse ?S

?S rdfs: subclassof clc: Forests

?C rdf: type dbpedia: City

?C strdfs: SpatialGeometry ?CGEO

?NAME rdf: type noa: DestroyedArea

?NAME strdfs: SpatialGeometry ?FGEO

FILTER(strdfs: spInside (?RGEO, ?FGEO) && strdfs: distance (?FGEO, ?CGEO) < 0.1))

}

The SELECT statement is followed by a list of the names of the results, namely: the region name and the spatial data on the region. The WHERE statement states the relations of the triples that need to be satisfied between the following variables: ?R indicates the area containing the forest ?F, ?C indicates the mentioned city, and ?NAME represents the mentioned destroyed forest. The FILTER statement represents the spatial function of spatial variables: strdfs: spInside (?RGEO, ?FGEO) represents that ?R is inside ?F and strdfs: distance (?FGEO, ?CGEO) < 0.1 represents that the shortest distance between ?F and ?C is less than 0.1 kilometers.

Example 2.

When we query the temporal data in a program that is called simultaneously with a certain other program, the syntax is as follows:

SELECT ?P ?PTS

WHERE {

?P rdf: type ex: Program

?P om: hasProCallP ex: TimeSlice1

om: hasProCallP strdfs: TimeSlice ?PTS

?Q rdf:type ex: Program

?Q om: hasProCallQ ex: TimeSlice2

om: hasProCallQ strdfs: TimeSlice ?QTS

FILTER (strdfs: spNow (?PTS, ?QTS))

}

Since the program’s name and the temporal data of the program are sought, the SELECT statement is followed by ?P and ?PTS, that is, the temporal information of ?P is ?PTS. FILTER (strdfs: spNow (?PTS, ?QTS)) represents that ?P and ?Q have the same temporal information.

Example 3.

On the basis of the example in Section 3.2, when we query the name of the programs that are called by the sound wave receiver in the adjacent area and its spatiotemporal data, the syntax is as follows:

SELECT ?P ?PGT

WHERE {

?P rdf: type ex: Program

?P om: hasCallPBy ex: SoundWaveReceiver

om: hasCallPBy strdfs: SpatiotemporalGeo

?PGT (?PGEO, ?PTS)

?Q rdf:type ex: Program

?Q om: hasCallQBy ex: SoundWaveReceiver

om: hasCallQBy strdfs: SpatiotemporalGeo

?QGT (?QGEO, ?QTS)

FILTER (strdfs: spMeet (?PGEO, ?QGEO) && strdfs:spNow (?PTS, ?QTS))

}

Since the program’s name and the spatiotemporal data of the program are sought, the SELECT statement is followed by ?P and ?PTS, that is, the spatiotemporal information of ?P is ?PGT. FILTER (strdfs: spMeet (?PGEO, ?QGEO) && strdfs: spNow (?PTS, ?QTS)} means that ?P meets ?Q and they have the same temporal information.

This paper has a proposed spatiotemporal data model and the corresponding algebraic operations. A lot of missing or insufficient operations that do not exist in conventional models have also been put forward. Little related work on spatiotemporal RDF algebras has involved experimental results, so we consider only the theoretical feasibility of the proposed method in this paper. However, there are several intermediate algebras for optimizing RDF graph pattern matching, and they were proposed from a matching or querying viewpoint, not the algebra viewpoint. As a result, we will continue to study the corresponding querying method in our future work.

5. Conclusions and Future Work

In this paper, we explored a spatiotemporal RDF semantics and defined a spatiotemporal data model based on the RDF. Based on this model, we proposed algebraic operations for manipulating spatiotemporal RDF data. In our method, in contrast to previous works, filtering rules are contained in the algebraic operations so that the resulting graph meets the specified requirements. This algebra consists of a series of operations that make it possible to express the content of data and the structure of a spatiotemporal RDF graph. Furthermore, we also introduced a syntax specification for the spatiotemporal RDF, which may contribute to the study of spatiotemporal RDF querying in the future.

There are three aspects left for future work. The first is that it is worth trying to consider the application of the query syntax and improve efficiency without affecting accuracy. The second is that, in the face of uncertainty in spatiotemporal data, a more flexible model should be built. The last is that the query language of the spatiotemporal RDF should be explored and compared with other state-of-the-art methods.