An object-relational spatio-temporal geoscience data model

An object-relational spatio-temporal geoscience data model

Author's Accepted Manuscript An object–relational geoscience data model spatio–temporal Hai Ha Le, Paul Gabriel, Jan Gietzel, Helmut Schaeben www...

2MB Sizes 1 Downloads 13 Views

Author's Accepted Manuscript

An object–relational geoscience data model

spatio–temporal

Hai Ha Le, Paul Gabriel, Jan Gietzel, Helmut Schaeben

www.elsevier.com/locate/cageo

PII: DOI: Reference:

S0098-3004(13)00114-3 http://dx.doi.org/10.1016/j.cageo.2013.04.014 CAGEO3168

To appear in:

Computers & Geosciences

Received date: 10 June 2012 Revised date: 29 March 2013 Accepted date: 16 April 2013 Cite this article as: Hai Ha Le, Paul Gabriel, Jan Gietzel, Helmut Schaeben, An object–relational spatio–temporal geoscience data model, Computers & Geosciences, http://dx.doi.org/10.1016/j.cageo.2013.04.014 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting galley proof before it is published in its final citable form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

1

An Object–Relational Spatio–Temporal Geoscience Data Model

2

Hai Ha Lea,∗, Paul Gabrielb , Jan Gietzelb , Helmut Schaebena a

3 4

5

Institut f¨ur Geophysik und Geoinformatik, TU Bergakademie Freiberg, Germany b GiGa infosystems UG (haltungsbeschr¨ankt), Freiberg, Germany

Abstract

6

A model for spatially and temporally indexed multi–dimensional geoscience data has been de-

7

veloped by first embedding a combinatorial topological model in terms of G–Maps in the domain

8

Rm × Time (m ∈ N), and then converting it to an object–relational model which can easily be

9

implemented in an object–relational database system.

10

Geoscience objects referring to space and time often have complex geometries which are usu-

11

ally partitioned into simpler cells and have geometrical, topological, geological, geophysical, geo-

12

chemical and other relevant properties assigned to their cells. These objects may exist in a Eu-

13

clidean space Rm of arbitrary dimension m depending on which properties are chosen as “coordi-

14

nates”, where usually m = 3 and refers to three spatial dimensions, and evolve in one dimensional

15

valid time (Time). The valid time is independent of geometry, topology and properties but not vice

16

versa, i.e., the geometry of an object, for example, and all its properties are modeled as functions

17

of the valid time. Then the objects are assumed to be sampled at arbitrary but fixed instances of

18

time, and their evolution between these instances is modeled by appropriate interpolation. The

19

structure of the data model is well adapted to the interpolation required to represent the objects in

20

between the instances of their observation.

21

The data model provides the basis prerequisite of our envisioned spatio–temporal geoscience 1

22

information system.

23

Keywords: data modeling, data model for spatio–temporal multidimensional geoscience data,

24

database design, spatio–temporal geoscience information system.

25

1. Motivation and Introduction

26

Almost all data in Earth sciences refer to space and time, i.e., they describe geo–objects subject

27

to dynamic processes causing the evolution of their geometry, topology and geoscience properties.

28

Therefore we strive to develop a spatio–temporal geoscience information system capable to pro-

29

cess and answer queries like “Given a location (geo–object at a specified location) and properties

30

like temperature and pressure, for what period(s) of time was the geo–object exposed to them?”

31

or “How are the geometry and properties of an geo–object at a given time?”. An appropriate data

32

model is the prerequisite to build such an information system.

33

A data model comprises a logical scheme, operations and constraints. A spatio–temporal

34

geoscience data model is a data model for geo–objects existing in space and evolving in time.

35

An object–relational spatio–temporal geoscience data model is a spatio–temporal geoscience data

36

model which is put in the form of an object–relational model. Object–relational data models can

37

be implemented in almost all open source and commercial database systems, such as PostgreSQL,

38

Oracle, Microsoft SQL Server, and their applications take largely advantageous use of the database

39

system such as multi–user, concurrency control, transaction. Corresponding author; Tel.: +49-1573-8686588; Postal address: Hai Ha Le, Gustav-Zeuner-Str. 12, D-09596 Freiberg, Germany. Email addresses: [email protected] (Hai Ha Le ), [email protected] (Paul Gabriel), [email protected] (Jan Gietzel), [email protected] (Helmut Schaeben) ∗

Preprint submitted to Computers & Geosciences

April 19, 2013

40

Recent communications (Raza, 2012; Pelekis et al., 2004; Raza et al., 1999) have proposed

41

spatio–temporal data models for temporal geographic information systems (TGIS). Almost all

42

higher 2–dimensional geographic data are in digital evaluation model (DEM) and are called 2.5D,

43

i.e., z value is recorded as an attribute for each data point (x,y). They are not “true” 3-dimensional

44

data. 2-dimensional geographic data encompass simple geometric objects like points, lines, poly-

45

gons, and non spatial properties assigned to them. In geology, e.g. structural geology, mining

46

geology, engineering geology, objects like ore bodies have complex geometries, in at least 3–

47

dimensional Euclidean space, possibly characterized by horizons, faults, or folds. These geometric

48

objects are usually partitioned into cells which can be ordered in a hierarchy according to their

49

spatial dimension, and geological, geophysical, geochemical, and other relevant properties are

50

assigned to them.

51

In recent years, computational geometric modeling has focused on methods based on topology.

52

Then, a geometric model is composed of a topological model and an embedding model. Topologi-

53

cal models can roughly be classified into two groups: models representing cells either explicitly or

54

implicitly. The former models are based on incidence graphs; they represent cells such as vertices,

55

edges, faces, volumes as nodes of graphs, and represent some incidence or adjacency relationships

56

between these cells as edges of the graph. These models include Winged–Edge (Baumgart, 1975),

57

Vertex–Edge/Face–Edge (Weiler, 1985), Doubly Connected Edge List (Berg et al., 2008). The

58

latter models are also called ordered topological models where the ordering information of cells

59

about any cell is available, e.g. the counter–clockwise order of 0– and 1–cells with respect to a

60

2–cell. They use a single type of basic element and functions which operate on the set of these

61

elements. Examples of such models include C–Map (Edmonds, 1960; Lienhardt, 1994; Damiand 3

62

et al., 2011), Cell–Tuple (Brisson, 1989, 1993), G–Map (Lienhardt et al., 2009; Lienhardt, 1994;

63

L´evy and Mallet, 1999; Mallet, 2002). The advantage of ordered topological models is their capa-

64

bility to represent objects of any dimension. Notice that the model in (Raza et al., 1999) applies

65

the Cell–Tuple model, but represents cells explicitly; therefore it is restricted to a predefined di-

66

mension.

67

Lienhardt (1991) has compared some topological models with the C–Map and G–Map models.

68

The original version of C–Map (Edmonds, 1960; Lienhardt, 1994) represents partitioned, oriented

69

quasi–manifolds without boundaries. The extended version of C–Map in (Damiand et al., 2011)

70

can be used to represent objects with boundaries. The G–Map model uses one type of element,

71

called darts, and involutions on the set of darts. It represents partitioned quasi–manifolds of any

72

dimension; an additional dimension can be considered by simply adding one more involution. The

73

objects represented by G–Map can be orientable or non–orientable, with or without boundaries.

74

G–Map is defined by succinct and simple mathematical formulations. The operations to construct,

75

manipulate, and query a G–Map are simple, therefore their implementation will be straightforward.

76

Moreover, G–Map is close to the data model of Paradigm GOCAD R . G–Map and Cell–Tuple are

77

similar. To meet the requirements of a wide variety of geoscience applications, G–Map is the

78

model of our choice to build the data model.

79

To integrate time into spatial and non–spatial data, models (Raza, 2012; Raza et al., 1999;

80

Chen, 2001; Steiner, 1998) divided the time axis into time intervals, defined by beginning and

81

ending time instances, and represent data as being constant over these intervals. Thus the model

82

allows for instantaneous changes only. To overcome this restriction, a more flexible data model

83

assigns time stamps to the data and then applies interpolation to model the temporal evolution, 4

84

where the actual interpolation methods can be chosen to match conceptual geological models.

85

Duplicating objects at a time instance provides objects sharing the same geometry but differing in

86

their topology. In this way duplication accounts for instantaneous changes of the topology which

87

cannot change continuously and remains unchanged at least until the next time instance, while the

88

evolution of the geometry and the properties is modeled continuously, e.g. by piecewise linear

89

interpolation. As a result, a fast snapshot operation can be defined which calculates the geometry

90

and the properties of an object at any time.

91

Our data model describes the geometry, topology and properties of geo–objects as functions

92

of time along the real valid time axis. These functions are defined by their values at a finite

93

sequence of instances of time and user defined interpolation methods. In summary, our approach

94

features (i) the combinatorial topological G–Map model, (ii) an embedding model adapted to linear

95

geometries, (iii) assigning properties to cells of various dimension, (iv) instantaneous evolution of

96

the topology, and (v) continuous evolution of geometry and properties. Note that we use linear

97

embeddings as almost everybody else to keep the model as simple as possible yet sufficiently

98

versatile to meet the requirements of reasonable applications.

99

Following, Section 2 introduces the geometric model of geo–objects in m–dimensional Eu-

100

clidean space Rm referring to the topological model provided by G–Map. Then Section 3 con-

101

siders geometric objects in spatio–temporal domain, and Section 4 presents an extension of the

102

geometric model in Rm to a model in the domain Rm × Time. In Section 5, the model is converted

103

to an object–relational model. Section 6 describes the assignment of geoscience properties to the

104

geo–objects. Section 7 exemplifies how the evolution of a geo–object, i.e., its geometry, topology,

105

properties and existence subject to uplift and erosion, is presented with our data model. Section 8 5

106

considers issues of implementing the model in an object–relational database management system,

107

and the final Section 9 provides discussion and conclusion.

108

2. Geometric modeling based on topology – Generalized Maps

109

2.1. Modeled geometric objects

110

Geomodeling software, such as Paradigm GOCAD R , Paradigm SKUA R , Midland Valley MOVE,

111

Schlumberger PETREL, apply a hierarchy of basic geo–objects like Point, LineString, TIN (Tri-

112

angulated Irregular Network), Polyhedra, 2D Grid, faulted 3D Grid, regular 3D Grid as shown in

113

Figure 1 to compose geological models.

(a)

(e)

(c)

(b)

(d)

(f)

(g)

Figure 1: (a) Point, (b) LineString, (c) TIN, (d) Polyhedra, T T (e)2D Grid, (f)faulted 3D Grid, ti+1 Grid. (g)regular 3D

ti+1

ti

ti

114

These objects are main basic geo–objects that we will model. They are “special cell complexes”

115

ti-1 in 3–dimensional Euclidean space R3 . We generalizeti-1them and state that the basic geometric

116

objects, which need to be modeled, are subsets of m–dimensional Euclidean space described by

Y

X

Y

6 X

(a)

(b)

117

n–dimensional quasi–manifolds (0 ≤ n ≤ m). Before giving a definition of quasi–manifold, some

118

terms need to be recalled.

119

Let i be an integer, i > 0, Ri be the i–dimensional Euclidean space, and ||.|| be the standard

120

norm in Ri , it is called Bi = {x ∈ Ri : ||x|| < 1} as open i–ball, Bi = {x ∈ Ri : ||x|| ≤ 1} as closed

121

i–ball, and S i = {x ∈ Ri+1 : ||x|| = 1} as standard i–sphere. For convenience, the open 0–ball B0

122

(closed 0–ball B0 ) is considered as a single point.

123

For i ≥ 0, an open (a closed) i–cell is a set homeomorphic to an open (a closed) i–ball; an

124

i–sphere is a set homeomorphic to a standard i–sphere. The dimension of an open (a closed) i–cell

125

(or an i–sphere) c is i, denoted as dim(c).

126

Definition 1. Let n be an integer, n ≥ 0, an n–dimensional finite CW(closure–finite, weak topology)–

127

Complex is a pair (X, P) where X is a Hausdorff space and P is a finite partition of X into open

128

cells of dimension not greater than n, and for every open i-cell c, 0 < i ≤ n, in P, exists a

129

continuous map H from the closed i-ball to X such that

130

131

132

(i) the restriction to the open i–ball is a homeomorphism onto c, and (ii) the image of the restriction to the standard (i − 1)-sphere is the union of open cells in P of dimension less than i.

133

We show in the next lemma that if i > 0, the image of the restriction of H to the standard (i−1)–

134

sphere is independent of H, and therefore, we can define the boundary of an i–cell c, denoted ∂c,

135

as this image, H(S i−1 ). For convenience, the boundary of 0–cell is empty.

136

Lemma 1. Let i be an integer, i ≥ 0, X be a Hausdorff space, c be a subset of X. If there exists

137

a continuous map H from the closed i–ball b in i–dimensional Euclidean space Ri to X such that 7

138

the restriction of H to the open i–ball b is a homeomorphism onto c, then H(b) = c, where c is the

139

closure of c in the sense of the topology of X.

140

Proof. We have H(b) ⊆ H(b) = c (cf. Dugundji, 1966, Theorem 8.3). On the other hand, since

141

b is compact in Ri and H is continuous, H(b) is compact in X. Because X is a Hausdorff space,

142

H(b) is closed, therefore, H(b) ⊇ c.

143

Using the term boundary, terms face, co–face, incidence, adjacency, link, connectivity can be

144

defined. Given a cell α, a cell β is called a face of α if and only if β ∈ ∂α; in this case, α is called

145

co–face of β. Two cells α, β are incident if and only if either α is a face of β or β is a face of α.

146

Cells α, β are adjacent if and only if dim(α) = dim(β) and there exists a cell γ, which is a face of

147

both α and β. Given a cell α, a link of α is a union of all boundaries of co–faces of α, which is not

148

incident to α. An n–dimensional finite CW–Complex is connected if for every two 0–cells α, β a

149

sequence γ0 , γ1 , ..., γk exists such that α = γ0 , β = γk and γi , γi+1 are incident for any 0 ≤ i < k.

150

Definition 2. Let n be an integer, n ≥ 0, an n–dimensional quasi–manifold is an n–dimensional

151

finite CW–Complex (X, P) which satisfies the following conditions:

152

153

154

155

(i) Finite, regular CW-Complex: Every cell is either an n-cell or a face of an n-cell. (ii) Pseudo–manifold: If n > 0, every (n − 1)–cell is a face of at most two n-cells. (iii) Quasi–manifold: Inductively, 0 and 1–pseudo–manifolds are quasi–manifolds, for i > 1, a link of each 0–cell is a connected (i − 1)–quasi–manifold.

156

In topological sense, 0–cells, 1–cells, 2–cells, 3–cells are called vertices, edges, facets, vol-

157

umes respectively. i–cells describing cells in Rm , 0 ≤ i ≤ m, are called real i–cells, for example,

158

0–cells (points), 1–cells (lines), 2–cells (planar polygons), 3–cells (polytopes). 8

159

Symbol Ki is used to define a set of i–cells contained in the partition P of X.

Ki = {c ∈ P : dim(c) = i}

160

We recall that a quasi–manifold is a decidable space of arbitrary dimension, and that the al-

161

gorithm in Floriani et al. (2002) enables us to decompose any non–manifold into an assembly of

162

quasi–manifolds.

163

2.2. Generalized Maps (n–G–Map)

164

Graph theory can be used to construct a graph, where vertices represent cells and edges rep-

165

resent incidence relationships between cells. Such a graph is called an incidence graph. Brisson

166

(1989, 1993) introduced “Cell–Tuple–Structure”, where the incidence relationships are described

167

in terms of cell–views v = {ci , ci+1 , ..., c j }, j > i, or the view of cell ci from cell c j . The cell–

168

view v = {c0 , c1 , ..., cn } is a view of vertex c0 from a cell with the largest dimension cn and called

169

“vertex–view”.

170

The pair (w, w0 ) of two vertex–views w and w0 ,

w = {c0 , ..., ci−1 , ci , ci+1 , ..., cn }, w0 = {c0 , ..., ci−1 , c0i , ci+1 , ..., cn },

171

which share the same j–cells for all j , i, is called i–adjacent. Then i–adjacency induces a set of

172

involutions {ai } in the set of vertex–views.

173

Generalized maps (G–Map) are similar to Brissons “Cell–Tuple–Structure”, but have been 9

174

independently introduced by Lienhardt (cf. Lienhardt, 1989, 1994; Lienhardt et al., 2009; L´evy

175

and Mallet, 1999; Mallet, 2002). G–Map uses two objects “dart” and “i–involution”, where a dart

176

denotes a path from an n–cell node to a 0–cell node of the incidence graph, and an i–involution is a (b)

177

mapping to generate an i–adjacency. Darts are analogous to vertex–views in Cell–Tuple structure.

178

An involution is a bijection which is its own inverse. G–Map is formally defined as follows (cf.

179

Mallet, 2002).

180

(c) Definition 3. An n–G–Map of dimension n, n ≥ 0, is an algebra M(D, α0 , α1 , . . . , αn ), where D

(a)

181

is a finite set of abstract elements called darts, αi , i = 0, ..., n, are i–involutions on D, satisfying

182

V3 following conditions:

V4

F1

E5 183

(i) αi (d) , d

∀d ∈ D; 0 ≤F2i < n; E2

E3 184

E4

(ii) αi ◦ αi+2+k {αiF◦ αi+2+k (d)} = d 1

185

(iii) αi ◦ αi+2+k (d)E, d 1 V1

186

F2

E1

E3

E4

E2

E5

∀d ∈ D; i ≥ 0; k ≥ 0; i + 2 + k ≤ n;

∀d ∈ D; i ≥ 0; k ≥ 0; Vi1+ 2 + k ≤ Vn.2 V2

(a) A graphical display of a 2–G–Map is shown in Figure 2.

V3

V4

(b)

Darts

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Figure 2: Graphical display of a 2–G–Map.

187

The three conditions of the definition of n–G–Map ensure the consistency of boundary rela-

188

tionships and completeness of “darts sewing” when embedding geometric objects from n–G–Map. 10

(a) (d) 2–orbit

<

(d)

abstract 2-cell

189

Figure 3 shows examples of violations of these conditions. d d d

(a)

(b)

(c)

Figure 3: Violations of the 1 st condition (a), the 2nd condition (b), the 3rd condition (c).

190

An important operation on n–G–Map is the “orbit”–operation defined as follows. Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

191

Definition 4. An orbit < αi1 , αi2 , . . . , αik > (d) of a dart d ∈ D on a subset of involutions S =

192

{αi1 , αi2 , . . . , αik }, defined on the n–G–Map M(D, α0 , α1 , . . . , αn ) is the set of all darts which are

193

the image of d applying any combination of the involutions in S . Especially, an i–orbit of d is the

194

orbit of d on all but the i–involution, < α0 , . . . , αi−1 , αi+1 , . . . , αn > (d) =< α / i > (d).

195

The i–orbit < α / i > (d) is also referred as an “abstract” i–cell. In the next subsection we will

196

show that a correspondence exists between an “abstract” i-cell and a “real” i-cell. Figure 4 shows

197

some orbits of the example 2–G–Map in Figure 2.

198

2.3. Geometric Model (GModel)

199

˜ i }, where n–G–Map and i–orbit operations determine a collection of sets of “abstract” i–cells {K

200

˜ i = {˜ci =< α K / i > (d)} ∀i ∈ [0, n]. The boundary operation of an abstract i–cell c˜ i is induced from

201

the definition of n–G–Map as

∂˜ci = ∂(< α / i > (d)), =

for any d ∈ c˜ i ,

 <α / k > (d0 ) 0 ≤ k < i, d0 ∈< α / i > (d) . 11

(b) 0–orbit

<

(d)

abstract 0-cell

(c) d

1–orbit

<

(d)

abstract 1-cell

(a) (d) 2–orbit

<

(d)

abstract 2-cell

Figure 4: Orbits on the example 2–G–Map. d 202

˜ i } enables us to define the incidence and adjacency relationships The boundary operation in {K d d

203

of two abstract cells analogously to the incidence and adjacency relationships of geometric cells. (a)

(b)

(c)

204

- c˜ i and c˜ j are incident if and only if either c˜ i ∈ ∂˜c j or c˜ j ∈ ∂˜ci .

205

- c˜ i and c˜ j are adjacent if and only if i = j and there exists c˜ k , k = i − 1, incident to both c˜ i and

206

c˜ j .

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

207

To realize the abstract model in terms of G–Map as a geometric object, each abstract i–cell is

208

mapped onto a real i–cell in Rm . This is done by a series of (n + 1) mappings φ = {φ0 , φ1 , . . . , φn }

209

˜ i } to {Ki } satisfying the following two conditions for any i ∈ [0, n] (cf. Mallet, 2002, 2.3.4): from {K

210

˜ i and Ki ; (i) φi is a bijection between K 12

211

(ii) if i > 0, then the bijection φi and φi−1 preserve the incidence relationships: a0 ∈ ∂a if and

212

˜ i and any of its incident (i − 1)–cells only if φi−1 (a0 ) ∈ ∂φi (a) for any “abstract” i-cell a ∈ K

213

˜ i−1 . a0 ∈ K

214

˜ i } in the embedding space Rm (m ≥ n). An Such bijections φ are called an embedding of {K example of an embedding is shown in Figure 5. Y

X

Figure 5: An general embedding model. Y 215

216

Topology, represented by n–G–Map, and embedding, represented by functions φ, define geo-

217

metric model (n–G–Model).

218

Definition 5. An n–G–Model (n ≥ 0) is an algebra G(D, A, φ), comprising the n–G–Map M(D, A) X

219

of a set of darts D and a set of involutions A = {α0 , α1 , . . . , αn }, and the embedding φ.

220

Following Mallet (2002), linear geometric models can be defined as n–G–Models comprising

221

an embedding φ constituted by φ0 only. This is acceptable because we always construct embedding 13 Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Y

222

φ from valid geometries. In this case, the condition to ensure the consistency of the map ϕ = φ0 is X

ϕ(d) = ϕ(d0 ) for all d0 ∈< α / 0 > (d).

223

224

Figure 6 shows the embedding of a 2–G–Map in 2–dimensional Euclidean space R2 using a linear embedding model. Y

X

Figure 6: A linear embedding model.

225

3. Objects in spatio–temporal domain Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

226

227

228

229

230

231

Objects in spatio–temporal domain can be represented as objects in m–dimensional Euclidean space Rm evolving along a time axis T. Two kinds of evolutions can be distinguished: • evolutions which preserve all topological relationships concerning the objects (such in Figure 7a), i.e. homeomorphisms; • evolutions which alter the topological relationships concerning the objects (such in Figure 7b). 14

(a)

(c)

(b)

(e)

(d)

(f)

(g)

T

T

ti+1

ti+1

ti

ti

Y

ti-1

X

Y

ti-1

X

(a)

(b)

Figure 7: Geometry changes over time; (a) preserving the topology, (b) changing the topology.

232

Following the suggestion of Polthier and Rumpf (1995), geo–objects are duplicated at each

233

temporal instance into preObject and postObject. They share a common geometry but differ in

234

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/) their topology. Any preObject at a given instance has the same topology as the corresponding

235

postObject of the previous instance, and any postObject at a given instance has the same topology

236

as the preObject of the next instance. For example, in Figure 8, ti –preObject is a triangle and

237

has the same topology as ti−1 –postObject; the ti –postObject comprises 2 triangles, where one is

238

an ordinary and the other one is a degenerated triangle, and has the same topology as the ti+1 –

239

preObject; the ti –preObject and the ti –postObject share a common geometry.

240

Figure 9 depicts the evolution of a geo–object in spatio–temporal domain. While the discon-

241

tinuous evolution of topological relationships of an object can be described by a step function as

242

shown in Figure 10a, the geometrical evolution of an object can be described by a continuous

243

piecewise linear function, where “sudden” changes are modeled by linear changes over a very

244

short period of time as shown in Figure 10b.

15

ti-1

ti

ti-1

ti+1

ti

ti-preObject

ti-1-postObject

ti+1

ti-postObject

same

ti+1-preObject same

same geometryt -postObject but i ti-1-postObject topology ti-preObject topologyti+1-preObject different topology

same same same geometry but T Z topology Figure 8: Topology synchronization. topology different ti+1 topology T

Z

ti+1 ti

ti ti-1 Y

ti-1 Y X

X

Figure Example of an geo–object evolving in spatio–temporal Print to PDF without this9: message by purchasing novaPDF (http://www.novapdf.com/)

Print to PDF without this message by purchasing novaPDF16 (http://www.novapdf.com/)

domain.

t0

t1

t2

t3

T

t0 t00

t1 t11 t12 t2 t21 t3 t31 t32 t01 t13 t22 1 2 t0 t0 t30

T

(b)

(a)

Figure 10: (a) Topological function; (b) Geometrical function.

245

Figure 11 provides a joint view of the topological and geometrical evolution of the objects in

246

Figure 10a and Figure 10b. The topology of an object is a discrete function of t and can be de-

247

scribed by a finite set of the topologies MT = {M(t0 ), M(t1 ), . . . , M(tk )} corresponding to the time

248

series T M = {t0 , t1 , . . . , tk }. The geometry of an object is a function of time and by means of em-

t0

t1 t11 t12 t2

t21 t3

t31 t32

T

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/) 249

bedding of the object’s topology. It can be described by a set of piecewise linear functions (in case

250

of using linear interpolation) on the set of intervals {(t0 , t1 ), (t1 , t2 ), . . . , (tk−1 , tk )} with the condition

251

G(M(ti−1 ), ti ) = G(M(ti ), ti ) for any 0 < i ≤ k. Each piecewise linear function G(M(ti ), t) on inter-

252

val (ti , ti+1 ), 0 ≤ i < k, is defined by the set of values {G(M(ti ), t0i ), G(M(ti ), t1i ), . . . , G(M(ti ), tgi i )}

253

at times {ti = t0i , t1i , . . . , tgi i = ti+1 } and an interpolation method. If t > tk , the geometry of

254

the object is defined by the set of values {G(M(tk ), t0k ), G(M(tk ), t1k ), . . . , G(M(tk ), tgkk )} at times

255

{tk = t0k , t1k , . . . , tgkk }. For convenience, if the object exists after time tgkk then its geometry and topol-

256

ogy are the same as at tgkk , otherwise they are empty sets.

257

The calculation of the preObject and the postObject from an object is the main task of a

258

construction operation of the model. This task is known as solving the “vertex corresponding”

17

t0

t1

t2

t3

T

t0 t00

t1 t11 t12 t2 t21 t3 t31 t32 t01 t13 t22 t10 t20 t30

T

(b)

(a)

t0

t1 t11 t12 t2

t21 t3

t31 t32

T

Figure 11: Topology and Geometry over time.

thout this message by purchasing novaPDF (http://www.novapdf.com/) 259

problem and can be characterized as following. Given two n–dimensional geometric models

260

n − G(D, A, φ) and n − G0 (D0 , A0 , φ0 ), the problem is to construct two n–dimensional geometric

261

models n − G1 (D1 , A1 , φ1 ) and n − G01 (D01 , A01 , φ01 ) and a bijection H between n − G1 and n − G01

262

such that n − G and n − G1 share a common geometry, and n − G0 and n − G01 also share a common

263

geometry. The map H is a bijection between n − G1 and n − G01 in the sense that H is a bijection

264

between two sets of darts D1 and D01 and preserves all involutions and embeddings.

265

4. Geometric model in spatio–temporal domain

266

Let T be a collection of k + 1, k ≥ 0, sequences, where the ith sequence contains gi + 1, gi ≥ 0,

267

instances, and the initial instance of any sequence except the first equals the last instance of the

268

previous sequence, i.e.,

T = {{t00 , t10 , . . . , tg00 }, {t01 , . . . , tg11 } . . . , {t0k , . . . , tgkk }},

18

t0i+1 = tgi i

for all 0 ≤ i < k.

269

An example is T = {{1, 2, 3, 4}, {4, 5}, {5, 6, 7, 8, 9}}. The set T M of initial instances of the se-

270

quences of T is T M = {t0 , t1 , . . . , tk } with ti = t0i

271

272

273

274

275

for all i ∈ [0, k].

In the example, T M = {1, 4, 5}. To generalize the geometric model in Section 2 from Rm into the domain Rm ×Time, we proceed as follows: (i) Expand the set of darts D to the set DT such that DT can be partitioned into k + 1 non-empty and disjoint subsets Di of darts, i.e.,

DT =

k [

Di , Di , ∅ and Di ∩ D j = ∅

for all i , j.

i=0

276

277

(ii) Expand the embedding function φ into the collection of sequences, ordered and indexed according to T above, i.e.,

ΦT = {{φ00 , φ01 , . . . , φ0g0 }, {φ10 , . . . , φ1g1 } . . . , {φk0 , . . . , φkgk }}.

278

279

280

The domain of φi0 , φi1 , . . . , φigi is Di . (iii) Add constraints on the set {αi } such that {αi } is a set of involutions closed in each partition D j of DT αi (d j ) ∈ D j ,

281

for all d j ∈ D j .

Consequently, a new geometric model in spatio–temporal domain, called n–GST–Model, is 19

282

accomplished and defined as follows.

283

Definition 6. Let n, k be integers, n ≥ 0, k ≥ 0, and let gi , i = 0, ..., k, also be integers greater than

284

or equal to 0. Let DT , ΦT be defined as above, let A be a set of i–involutions for all i ∈ [0, n]. An

285

n–GST–Model is an algebra GST (DT , A, ΦT ) satisfying following constraints:

286

287

(i) αi (d j ) ∈ D j (ii) αi (d) , d

∀0 ≤ i ≤ n; 0 ≤ j ≤ k; d j ∈ D j ; ∀d ∈ DT ; 0 ≤ i < n;

288

(iii) αi ◦ αi+2+k {αi ◦ αi+2+k (d)} = d

289

(iv) αi ◦ αi+2+k (d) , d

290

291

(v) φij is an embedding

∀d ∈ DT ; i ≥ 0; k ≥ 0; i + 2 + k ≤ n;

∀d ∈ DT ; i ≥ 0; k ≥ 0; i + 2 + k ≤ n; ∀0 ≤ i ≤ k; 0 ≤ j ≤ gi .

The n–GST–Model is equipped with an operation called “snapshot” to construct the geometry

292

of an object at any given time instance t.

293

Definition 7. Let GST (DT , A, ΦT ) be an n–GST–Model, its snapshot at a given instance t is a

294

295

296

297

298

299

300

n–G–Model G(D, A, φ), denoted by GST (t), such that (i) if t0 ≤ t ≤ tgkk , s be a variable whose value be defined by t, then     i i+1   →s=i   Di i f t ≤ t < t (1) D =        Dk i f tk ≤ t ≤ tgkk → s = k,    φ sj+1 −φ sj  s s s s   φ +  j t sj+1 −t sj × (t − t j ) i f t j ≤ t < t j+1  (2) φ =       i f tgkk = t,  φkgk (ii) if t < t0 , GST (t) = ∅, (iii) if object exists when t > tgkk , then GST (t) = GST (tgkk ) for t > tgkk . If not, GST (t) = ∅ for t > tgkk . 20

301

302

303

5. The model in object–relational mode In this section, n–GST–Model is converted into object–relational mode. To this end, the following tasks are done.

304

First, the collection of sequences T = {{t00 , t10 , ..., tg00 }, {t01 , ..., tg11 }, ..., {t0k , ..., tgkk }} is represented as

305

two relations TimeT and TimeM as follows. The relation TimeT represents the sequence of time in-

306

stances at which the geometry of the object has changed T T = {t00 , t10 , ..., tg00 −1 , t01 , ..., tg11 −1 , ..., t0k , ..., tgkk },

307

and TimeM represents the sequence of time instances at which the topology of the object has

308

changed T M = {t0 , t1 , ..., tk }. For example, if T = {{1, 2, 3, 4}, {4, 5}, {5, 6, 7, 8, 9}}, then TimeT

309

contains values {1, 2, 3, 4, 5, 6, 7, 8, 9} and TimeM contains values {1, 4, 5}. Second, the set DT =

310

{Dt0 , Dt1 , . . . , Dtk } is represented as the relation Dart with an attribute TimeMID in [0, k]. Next,

311

the set A = {α0 , α1 , . . . , αn } of involutions is represented as the relation Alpha with attributes level

312

in [0, n], DartID1, and DartID2 to represent the map from dart d1 to dart d2 . Finally, the set

313

Φ = {{φ00 , φ01 , . . . , φ0g0 }, {φ10 , . . . , φ1g1 }, {φk0 , . . . , φkgk }} is represented as the relation Phi with attributes

314

T imeID, DartID, CoordinateID to map sets of darts, e.g. 0-orbits, to geometrical cells in real

315

space Rm .

316

317

318

319

Figure 12 shows the n–GST–Model in object–relational mode, referred to as n − GS T − Model in OR. The attribute Alive (boolean attribute) in the relation Feature is to define the object existing after the point of time tgkk or not.

320

To increase the performance of geometric queries, a relation Node representing abstract 0–

321

cells is added, and the relations Coordinate, and Phi are merged into a relation named Vertex. The 21

Geometry

Feature

Coordinate

TimeT

FeaID

CoordinateID

FeaID

Alive

PointValue

TimeID

Phi PhiID FeaID TimeID

TimeM FeaID TimeMID

DartID Dart

CoordinateID

DartID FeaID TimeMID

Alpha AlphaID FeaID DartID1 DartID2

Topology

Level

Figure 12: Object–relational model of GST. Figure 13 depicts n–GST–Model in OR with redundant relation Node.

322Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

323

6. Assigning geoscience properties to geometry

324

Almost all geoscience applications need to assign geological, geophysical, geochemical prop-

325

erties to parts of geometric objects to solve problems. For example, exploration and produc-

326

tion applications in petroleum fields usually require properties such as porosity, permeability, etc.

327

Therefore, besides modeling geometric objects evolving in space and time, properties need to be

328

assigned to geometries and they also evolve in time. Properties are assigned to cells, usually either

329

vertices or volumes, of geo–objects. Figure 14 shows an example of two geometric objects with

330

properties assigned either to the vertices (Fig. 14a) or to the 3-cells (Fig. 14b).

331

Users of GST–Model decide where to archive geo–objects and which properties should be as22

Geometry

Feature TimeT

FeaID

FeaID TimeID

Vertex vrtxID FeaID

Node

TimeID

NodeID

TimeM

NodeID

FeaID

FeaID

TimeMID

TimeMID

Coordinate[ ]

Dart Alpha

DartID FeaID

AlphaID

TimeMID

FeaID

NodeID

DartID1 DartID2

Topology

Level

Figure 13: Object–relational model of GST with redundant relation Node. Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1.2 1.4 1.1 1.3

1.2

1.3

1.4

1.5

1.2

(b)

(a)

Figure 14: Porosity values are assigned either to vertices of a horizontal surface (a), or to 3–cells of a geo–object (b).

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

23

332

signed, i.e., user–defined relations in the database. These relations and their attributes are designed

333

by database administrators and stored in user schema. Relation Catalog and a stored procedure

334

called GST REGISTER are added to the model to register and keep information connecting be-

335

tween user schema and internal GST schema. Figure 15 shows a GST–Model with properties.

GST schema

User schema

Feature

Shape ……



TimeT FeaID FeaID TimeID

Properties FeaID FeaID … TimeID

Geometry Vertex

TimeM

vrtxID Node

FeaID

NodeID

TimeMID

FeaID TimeMID

AbstractCell

FeaID

ACellID … Property1

TimeID

ACellID

Property2

NodeID

FeaID



Coordinate[ ]

TimeMID CellLevel

Property

Dart DartID

Catalog

Alpha

FeaLayerName

FeaID

AlphaID

TimeMID

FeaID

NodeID

DartID1

SRS

ACellID

DartID2

ProTableName

Level

CellLevelAttach

Topology

ShapeName

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Figure 15: Object–relational model of GST with properties.

336

The ”User schema” (see Fig. 15) comprises user–defined relations including

337

and . For example, in structural geology, relation STRUCTURAL HORIZONTAL

338

is designed to store horizontal surfaces with attributes ID for identifier, SHAPE for geometry of

339

surface, and NAME for name of surface. Properties POROSITY and PERMEABILITY are stored

340

in relation STRUCTURAL HOR PROS, and assigned to the vertices of these surfaces. The stored 24

341

procedure GST REGISTER is used to write register information about user schema to Catalog

342

relation. The example is described in SQL language using PostgreSQL as

343

• Create table STRUCTURAL HORIZONTAL(ID bigint, SHAPE bigint, NAME varchar(50));

344

• Create table STRUCTURAL HOR PROS(POROSITY float, PERMEABILITY float);

345

• Select GST REGISTER(’STRUCTURAL HORIZONTAL’, ’SHAPE’, 0, ’STRUCTURAL HOR PROS’,

346

347

348

0); Three attributes FeaID, TimeID, AcellID will be added into relation STRUCTURAL HOR PROS by procedure GST REGISTER.

349

The GST schema comprises internal relations that cannot be changed directly by users. Rela-

350

tion AbstractCell is added to increase the performance of properties query. A node is an abstract

351

cell with dimension (CellLevel) 0, which always assigns to coordinates, therefore relation Node is

352

kept to get high performance of geometric query.

353

7. Applications of the model

354

Being designed to represent geo–objects evolving in space and time, our GST–Model can

355

record the geological history in an appropriate and consistent way. Moreover, GST–Model can be

356

used to enhance 4d geomodeling such as restoration features by e.g. GOCAD R or SKUA R . Other

357

typical applications are numerical simulations of geodynamical processes. Here, we illustrate

358

our GST–Model by a representation of a geo–object subject to sedimentation, erosion, and uplift.

359

Figure 16 and Figure 17 depict a fictitious limestone layer subject to erosion and uplift, which 25

360

cause the limestone layer evolving in terms of geometry and topology until it disappearance as a

361

geo–object. Table 1: Relations Feature, TimeT, TimeM. Feature FeaID Alive 1 FALSE 2 ... ...

TimeT FeaID TimeID 1 -70 000 000 1 -69 900 000 1 -68 850 000 1 -68 800 000 2 ...

TimeM FeaID TimeMID 1 -70 000 000 1 -68 850 000 1 -68 800 000 2 ...

Table 2: Relation Node. NodeID 1 1000 2000 5000 ...

FeaID TimeMID 1 -70 000 000 1 -68 850 000 1 -68 800 000 2 ...

362

The limestone is modeled by its top surface and foot wall. The limestone body is the volume in

363

between these two TIN objects. To simplify the representation of the GST–Model for this example,

364

we refer only to the top surface of the limestone layer and call it “the object” (FeaID = 1 in relation

365

Feature – Table 1) throughout this section.

366

Figure 16a depicts the object at time 70 Ma. At this time, nearly the entire object was located

367

below the sea level. The dart #1 and the node #1 are components of the topology of the object.

368

The vertex #1 is a component of the geometry of the object, and is used to represent the geometric

369

location of node #1. Corresponding data of node, dart, and vertex are described in Tables 2, 3, 4, 26

Table 3: Relation Dart. DartID 1 1000 2000 5000 ...

FeaID 1 1 1 2

TimeMID NodeID -70 000 000 1 -68 850 000 1000 -68 800 000 2000 ... ...

ACellID -

Table 4: Relation Vertex.

pre-object post-object pre-object post-object

370

VrtxID 1 500 700 1000 1500 2000 5000 ...

FeaID 1 1 1 1 1 1 2

TimeID NodeID -70 000 000 1 -69 900 000 1 -68 850 000 1 -68 850 000 1000 -68 800 000 1000 -68 800 000 2000 ... ...

Coordinates {0 0 3} {0 0 9} uplift 6m {0 0 5} erosion 4m {0 0 5} {0 0 -0.2} erosion 5.2m {0 0 -0.2} {...}

respectively.

371

Figure 16b depicts the object at time 69.9 Ma. More than half of the object was above the sea

372

level. In the period [70 – 69.9] Ma, the object was moved upward without deformation or erosion,

373

therefore the object changed its geometry, but the topology remained unchanged. The topology of

374

the object at the time 69.9 Ma is represented by dart #1 and node #1. The location of the object

375

was changed. That is why a new vertex with a new identifier and a new coordinate is recorded in

376

the database. The vertex associated to node #1 is changed from #1 to #500 (see rows 1 and 2 in

377

Table 4).

378

Figure 16c depicts the object at time 68.85 Ma. In period [69.9 – 68.85] Ma, the object was

27

DartID: 1 NodeID: 1 VrtxID: 1

(a) Limestone at time 70 Ma.

(b) Limestone at time 69.9 Ma.

(c) Limestone at time 68.85 Ma.

DartID: 1 NodeID: 1 VrtxID: 500

DartID: 1 NodeID: 1 VrtxID: 700

DartID: 1000 NodeID: 1000 VrtxID: 1000

Topology of the object was changed

DartID: 1000 NodeID: 1000 VrtxID: 1500

DartID: 2000 NodeID: 2000 VrtxID: 2000

Topology of the object was changed

(d) Limestone at time 68.8 Ma.

(e) No limestone at time 68.75 Ma.

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Figure 16: Limestone at time 70 Ma.

28

379

eroded, which caused a change of its topology and its location. The topologies of the object at

380

time 68.85 Ma and time 69.9 Ma differ, some vertices are disappeared. To represent this evolution,

381

GST–Model represents the object at time 68.85 Ma by two versions: The pre–object and the post–

382

object. These two versions share an identical geometry. The pre–object uses the same topology

383

as the object at time 69.9 Ma (see Figure 8). Thus, the pre–object is represented by dart #1, node

384

#1, and vertex #700. The post–object is represented by dart #1000, node #1000, and vertex #1000

385

(see rows 3 and 4 in Table 4).

386

Figure 16d depicts the object at time 68.8 Ma. At this time, the object had been completely

387

eroded. This process is presented by the time step, exactly before the last triangle vanished. In this

388

case, the geometry of the top and foot wall are identical, i.e., the limestone has zero thickness. This

389

allows to handle the object in the database and to keep the information about the erosion. In the

390

same way as at the time 68.85 Ma, the object is also represented by two versions. The pre-object

391

is represented by dart #1000, node #1000, vertex #1500, and the post–object is represented by

392

dart #2000, node #2000, vertex #2000. After saving this last process, no more information of the

393

object is added into the database. Figure 16e depicts that the limestone layer had vanished after

394

the instance of time 68.8 Ma.

395

The lifetime of the object is determined by relations T imeT , T imeM and the attribute Alive in

396

relation Feature. In Table 1, the attribute Alive of the relation Feature is FALSE; relation T imeT

397

represents a sequence T imeT = {70, 69.9, 68.85, 68.8}; relation T imeM represents a sequence

398

T imeM = {70, 68.5, 68.8}. From these data, the lifetime of the object can be defined by the

29

399

collection of sequences T (described in Section 4),

T = {{70, 69.9, 68.85}, {68.85, 68.8}, {68.8}},

400

401

402

and the object existed no more after the point of time 68.8 Ma. Cross sections of the limestone layer are depicted in Figure 17.

8. Notes on issues of implementation

403

We are implementing GST–Model in our GST software system (Gabriel et al., 2012; GST,

404

2012). The following notes and tips can be useful for users who wish to implement GST–Model

405

in an object–relational database management system, e.g. PostgreSQL (2012).

406

407

408

409

410

411

412

413

• Operations might be implemented as stored procedures of DBMS using SQL or C/C++ languages. • Implementations might use open source libraries as Boost C++ libraries (Boost, 2012), Computational Geometry Algorithms Library (CGAL, 2012), etc. • Input/output data might be in standard format like SFS (OGC 06–103r4, 2011; OGC 06– 104r4, 2010) and RESQML (RESQML, 2012). • The idea by Chen (2001) to partition the database might be pursued to make the system better performant.

30

70 Ma

reference datum

limestone

69.9 Ma

limestone

69.85 Ma

limestone

68.8 Ma

68.75 Ma

(a) Z

top wall 68.75 Ma 70 Ma 68.85 Ma

foot wall

68.8 Ma

T

69.9 Ma

(b)

Figure 17: Cross sections of the limestone layer: (a) in space, (b) in time.

414

9. Dicussion and conclusion

415

Since geology is to a large extent a historical science, we are interested to represent the geo-

416

logical evolution in a database. On our way to a spatio–temporal geoscience information system,

417

we have developed and implemented an appropriate data model for geoscience data referring to 31

418

space and valid time. Our model features (i) the combinatorial topological G–Map model, (ii) an

419

embedding model best adapted to linear geometries, (iii) assigning geoscience properties to cells

420

of various dimension, (iv) instantaneous evolution of the topology, and (v) continuous evolution

421

of geometry and properties.

422

G–Map is applied to explicitly represent the topological relationships governing the hierarchy

423

of abstract cells corresponding to geometric cells generated by partitioning of geo–objects. G–

424

Map is not restricted in terms of dimension. The correspondence of abstract and geometric cells

425

is provided by an embedding. At this time, the actual embedding is restricted to mapping ab-

426

stract vertices to geometric points and piecewise linear interpolation between points. Geoscience

427

properties are assigned to cells, where the cells should be chosen such that their dimension relates

428

sensitively to the property, e.g. rock type may be assigned to a point while porosity should be

429

assigned to a face or volume.

430

Time is modeled as 1–dimensional valid time, i.e. it is represented as a sequence of instances

431

and a time stamp is assigned to topology, geometry and properties. Since topology cannot evolve

432

continuously in time, it may only evolve in steps at sequential instances along the time axis. The

433

evolution of the geometry and the properties is modeled by interpolation between time instances

434

where the user can choose an appropriate method.

435

To improve the performance of temporal interpolation and thus the retrieval of information

436

referring to a given time, geo–objects are duplicated at each time instance into a pre– and a post–

437

object, such that pre– and post–object may differ in their topological relationships due to instan-

438

taneous changes but share the same geometry. The geometry may change continuously over the

439

interval enclosed by two successive instances from the geometry of the pre–object at the beginning 32

440

of the time interval to the geometry of the post–object at the end of the time interval.

441

Since our data model has a sound mathematical basis, its properties can be proven mathemat-

442

ically. The data model is being prototypically implemented as an extension of our existing GST

443

database software. Future work will include the development of a proper construct operation to

444

build the model.

445

Acknowledgements

446

We would like to express our thanks to Dr. Ralf Hielscher and Dipl.–Geol. Peggy Hielscher for

447

their helpful comments and advice. Many thanks to Dr. Ines G¨orz, without her help the example

448

in Section 7 could not have been completed.

449

We also would like to thank the anonymous reviewers and the editor for their comments and

450

suggestions on the manuscript.

451

Baumgart, B.G., 1975. A polyhedron representation for computer vision. In: American Federation

452

of Information Processing Societies 44, May 19–22, 1975, Anaheim, CA, USA. AFIPS Press,

453

1975. pp. 589–596. doi:10.1145/1499949.1500071.

454

455

Berg, M.D., Cheong, O., Kreveld, M.V., Overmars, M., 2008. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer–Verlag, Heidelberg, Germany, 386pp.

456

Boost, 2012. Boost C++ libraries. http://www.boost.org/ [accessed 16 May 2012]

457

Brisson, E., 1993. Representing geometric structures in d dimension: Topology and order. Journal

458

of Discrete and Computational Geometry 9, 387–426

459

Brisson, E., 1989. Representing Geometric Structures in d Dimensions: Topology and Or-

460

der. In: Proceedings of the Fifth Annual Symposium on Computational Geometry, June 33

461

5–7, 1989, Saarbr¨uchen, Germany. ACM Press, 1989, ISBN 0-89791-318-3. pp. 218–227.

462

doi:10.1145/73833.73858

463

464

465

466

CGAL, 2012. Computational Geometry Algorithms Library. Geometry Factory. http://www. cgal.org/ [accessed 16 May 2012] Chen, C.X., 2001. Data Models and Query Languages of Spatio–Temporal Information. Ph.D. Dissertation, University of California, Los Angeles, CA, USA, 136pp.

467

Damiand, G., Solnon, C., Higuera, C., Janodet, J., Samuel, E., 1960. Polynomial algorithms for

468

subisomorphism of nD open combinatorial maps. Journal of Computer Vision and Image Un-

469

derstanding archive 115(7), 996–1010. doi:10.1016/j.cviu.2010.12.013.

470

Dugundji, J., 1966. Topology, Allyn and Bacon, Inc, 447pp.

471

Edmonds, J., 1960. A combinatorial representation for polyhedral surfaces. Notices of the Ameri-

472

can Mathematical Society 7, 1960. p. 646.

473

Floriani, L.D., Mesmoudi, M.M., Morando, F., Puppo, E., 2002. Non–manifold Decomposition in

474

Arbitrary Dimensions In: Proceedings of the 10th International Conference on Discrete Geom-

475

etry for Computer Imagery, April 3–5, 2002, Bordeaux, France. Springer–Verlag London, UK,

476

2002, ISBN:3-540-43380-5. pp. 69–80

477

Gabriel , P., Gietzel, J., Le, H.H., Schaeben, H., in press. Geosciences in Space and Time Kompo-

478

nenten einer 3D GDI. gis.Science Ausgabe 4/2012. Wichman Verlag, Journal 4/2012 [in Ger-

479

man]

480

481

482

GST, 2012. GST – Geosciences in Space and Time, GiGa Infosystems., http://www. giga-infosystems.com/ [accessed 03 December 2012] L´evy, B., Mallet, J.L., 1999. Cellular Modeling in Arbitrary Dimension using Generalized 34

483

Maps. http://alice.loria.fr/publications/papers/1999/g_maps/g_maps.pdf [ac-

484

cessed 16 May 2012]

485

Lienhardt, P., Fuchs, L., Bertrand, Y., 2009: Combinatorial Models for Topology-Based

486

Geometric Modeling. http://hal-unilim.archives-ouvertes.fr/docs/00/58/07/08/

487

PDF/8qm22.pdf [accessed 16 May 2012]

488

489

Lienhardt, P., 1994. N–Dimensional Generalized Combinatorial Maps and Cellular QuasiManifolds. International Journal on Computational Geometry and Applications, 275-324.

490

Lienhardt, P., 1991. Topological models for boundary representation: a comparison with

491

n-dimensional generalized maps. Journal of Computer-Aided Design 23(1), 59-82. doi:

492

10.1016/0010-4485(91)90082-8.

493

Lienhardt, P., 1989. Subdivisions of n–dimensional spaces and n–dimensional generalized maps.

494

In: Proceedings of the Fifth Annual Symposium on Computational Geometry, June 5–

495

7, 1989, Saarbr¨uchen, Germany. ACM Press, 1989, ISBN 0-89791-318-3. pp. 228–236.

496

doi:10.1145/73833.73859.

497

Mallet, J.L., 2002. Geomodeling, Oxford University Press, Inc, 624pp.

498

OGC 06–103r4, 2011. OpenGIS Implementation Standard for Geographic information – Sim-

499

ple feature access – Part 1: Common architecture. http://www.opengeospatial.org/

500

standards/sfa [accessed 16 May 2012]

501

OGC 06–104r4, 2010: OpenGIS Implementation Standard for Geographic information – Simple

502

feature access – Part 2: SQL option. http://www.opengeospatial.org/standards/sfs

503

[accessed 16 May 2012]

504

Pelekis, N., Theodoulidis, B., Kopanakis, I., Theodoridis, Y., 2004. Literature Review of Spatio– 35

505

Temporal Database Models. Journal of The Knowledge Engineering Review 19(3), 235–274.

506

doi:10.1017/S026988890400013X.

507

Polthier, K., Rumpf, M., 1995. A Concept for Time–Dependent Processes. In: G¨obel, M., M¨uller,

508

H., Urban, B. (Eds.), Visualization in Scientific Computing, Springer–Verlag, 1995, ISBN 3-

509

211-82633-5. pp. 137–153.

510

511

512

PostgreSQL, 2012. PostgreSQL - the world most advanced open source database. PostgreSQL Global Development Group. http://www.postgresql.org/ [accessed 16 May 2012] Raza, A., 2012 Working with Spatio–Temporal Data Type. In:

Proceedings of the

513

XXII Congress of the International Society for Photogrammetry and Remote Sens-

514

ing, August 29 – September 1, 2012, Melbourne, Australia. pp. XXXIX–B2:5–10.

515

http://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XXXIX-B2/

516

5/2012/isprsarchives-XXXIX-B2-5-2012.pdf [accessed 02 December 2012]

517

Raza, A., Kainz, W. 1999 Cell Tuple Based Spatio–Temporal Data Model: An Object Oriented

518

Approach. In: Proceedings of the 7th ACM international symposium on Advances in geographic

519

information systems, Nov 2–6, 1999, Kansas City, USA. ACM press, 1999. pp. 20–25. doi:

520

10.1145/320134.320140.

521

522

523

524

RESQML, 2012. RESQML Version 1.1 specifications http://www.energistics.org/ reservoir/resqml-standards/current-standards [accessed 14 November 2012] Steiner, A., 1998. A Generalisation Approach to Temporal Data Models and Their Implementations. Ph.D. Dissertation, ETA Z¨urich, Switzerland, 163pp. doi:10.3929/ethz-a-001923958

525

Weiler, K., 1985. Edge–Based Data Structures for Solid Modeling in Curved-Surface

526

Environments. Journal of IEEE Computer Graphics and Applications 5(1), 21–40. 36

527

528

529

doi:10.1109/MCG.1985.276271.

List of Figures 1

530

(a) Point, (b) LineString, (c) TIN, (d) Polyhedra, (e)2D Grid, (f)faulted 3D Grid, (g)regular 3D Grid. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

531

2

Graphical display of a 2–G–Map. . . . . . . . . . . . . . . . . . . . . . . . . . .

10

532

3

Violations of the 1 st condition (a), the 2nd condition (b), the 3rd condition (c). . .

11

533

4

Orbits on the example 2–G–Map. . . . . . . . . . . . . . . . . . . . . . . . . . .

12

534

5

An general embedding model. . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

535

6

A linear embedding model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

536

7

Geometry changes over time; (a) preserving the topology, (b) changing the topology. 15

537

8

Topology synchronization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

538

9

Example of an geo–object evolving in spatio–temporal domain. . . . . . . . . . .

16

539

10

(a) Topological function; (b) Geometrical function. . . . . . . . . . . . . . . . .

17

540

11

Topology and Geometry over time. . . . . . . . . . . . . . . . . . . . . . . . . .

18

541

12

Object–relational model of GST. . . . . . . . . . . . . . . . . . . . . . . . . . .

22

542

13

Object–relational model of GST with redundant relation Node. . . . . . . . . . .

23

543

14

Porosity values are assigned either to vertices of a horizontal surface (a), or to

544

3–cells of a geo–object (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

545

15

Object–relational model of GST with properties. . . . . . . . . . . . . . . . . . .

24

546

16

Limestone at time 70 Ma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

547

17

Cross sections of the limestone layer: (a) in space, (b) in time. . . . . . . . . . .

31

37

548

List of Tables

549

1

Relations Feature, TimeT, TimeM. . . . . . . . . . . . . . . . . . . . . . . . . .

26

550

2

Relation Node. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

551

3

Relation Dart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

552

4

Relation Vertex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

38

Reference number: CAGEO 3168 Manuscript: “An Object-Relational Spatio-Temporal Geoscience Data Model” By: Hai Ha Le, Paul Gabriel, Jan Gietzel, Helmut Schaeben

Highlights: •

We develop a new model for spatio-temporal data in the Earth sciences.



The data model is in the form of an object-relational model.



The data model is based on a combinatorial topological model in terms of G-Maps.



Topology, geometry and geosciences properties are represented by functions of time.



The data model is well adapted to represent the objects in between the instances.