text: SMOOTH QUOTIENTS OF ABELIAN VARIETIES BY FINITE GROUPS 7 ∈ ∈ Assume now that λ = 0 for every z W and every pseudoreﬂection σ G. z In particular, W is ﬁxed by every σ, and since these generate the group, we (cid:92) have that W is ﬁxed pointwise by G. Now since G does not ﬁx pointwise any non-trivial abelian subvariety of A, we have that − ⊆ ker(1 τ) A ∈ τ G is ﬁnite and so its preimage in T (A) is discrete. However W is contained in 0 this preimage, and so it must be trivial. (cid:94)¨ We will consider now a new abelian variety B equipped with a G-equivariant isogeny to A, which we will call G-isogeny from now on. Let Λ denote the C C ⊆ A lattice in n such that A = n/Λ . Let Λ Λ be a G-invariant sublattice, A B A and let B := Cn/Λ be the induced abelian variety, along with the G-isogeny B → π : B A, ∈ whose analytic representation is the identity. Note that this implies that σ G is a pseudoreﬂection of B if and only if it is a pseudoreﬂection of A. We may ⊂ then consider the subvarieties E , D A deﬁned as above, which we will σ σ denote by E and D . Now, we can do the same thing for B and hence we σ,A σ,A ⊂ obtain subvarieties E , D B. Note that, by deﬁnition, π sends E to σ,B σ,B σ,B E and D to D . σ,A σ,B σ,A Deﬁne ∆ := ker(π). Since π is G-equivariant, G acts on ∆ and hence we (cid:111) may consider the group ∆ G. This group acts on B in the obvious way: ∆ acts by translations and G by automorphisms. In particular, we see that the (cid:111) quotient B/(∆ G) is isomorphic to A/G. Our goal is to reduce as much as we can the structure of B/G and ∆ and to prove that the latter must be trivial in several cases. Fix then a ∈ ⊂ pseudoreﬂection σ G of order r and consider the subvarieties E , D A ⊂ ∩ σ,A σ,A and E , D B. Deﬁne moreover F = E D and F similarly. σ,B σ,B → σ,A σ,A σ,A σ,B Then the isogeny π : B A sends F to F . σ,B σ,A Lemma 3.3. Let L be the line in T (A) inducing E and E . Assume that → 0 ∩ σ,A ∩ σ,B ⊂ the map F F is surjective and that Λ L = Λ L. Then ∆ D . σ,B σ,A A B σ,B (cid:39) F×σ,A Proof. Since E and D generate A, we have A E D and σ,A σ,A ∩ σ,A ∩ σ,A the same goes for B. Moreover, the hypothesis Λ L = Λ L implies → A B ∈ that π : E E is the identity. We note then that, for x E and σ,B σ,A σ,B ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SMOOTH

text: QUOTIENTS

text: OF

text: ABELIAN

text: VARIETIES

text: BY

text: FINITE

text: GROUPS

text: Assume

text: now

text: that

text: λ

text: for

text: every

text: z

text: W

text: and

text: every

text: pseudoreﬂection

text: σ

text: G.

text: z

text: In

text: particular,

text: W

text: is

text: ﬁxed

text: by

text: every

text: σ,

text: and

text: since

text: these

text: generate

text: the

text: group,

text: we

text: have

text: that

text: W

text: is

text: ﬁxed

text: pointwise

text: by

text: G.

text: Now

text: since

text: G

text: does

text: not

text: ﬁx

text: pointwise

text: any

text: non-trivial

text: abelian

text: subvariety

text: of

text: A,

text: we

text: have

text: that

text: τ)

text: A

text: τ

text: G

text: is

text: ﬁnite

text: and

text: so

text: its

text: preimage

text: in

text: T

text: (A)

text: is

text: discrete.

text: However

text: W

text: is

text: contained

text: in

text: this

text: preimage,

text: and

text: so

text: it

text: must

text: be

text: trivial.

text: We

text: will

text: consider

text: now

text: a

text: new

text: abelian

text: variety

text: B

text: equipped

text: with

text: a

text: G-equivariant

text: isogeny

text: to

text: A,

text: which

text: we

text: will

text: call

text: G-isogeny

text: from

text: now

text: on.

text: Let

text: Λ

text: denote

text: the

text: C

text: C

text: A

text: lattice

text: in

text: n

text: such

text: that

text: A

text: n/Λ

text: Let

text: Λ

text: Λ

text: be

text: a

text: G-invariant

text: sublattice,

text: A

text: B

text: A

text: and

text: let

text: B

text: Cn/Λ

text: be

text: the

text: induced

text: abelian

text: variety,

text: along

text: with

text: the

text: G-isogeny

text: B

text: π

text: B

text: A,

text: whose

text: analytic

text: representation

text: is

text: the

text: identity.

text: Note

text: that

text: this

text: implies

text: that

text: σ

text: G

text: is

text: a

text: pseudoreﬂection

text: of

text: B

text: if

text: and

text: only

text: if

text: it

text: is

text: a

text: pseudoreﬂection

text: of

text: A.

text: We

text: may

text: then

text: consider

text: the

text: subvarieties

text: E

text: D

text: A

text: deﬁned

text: as

text: above,

text: which

text: we

text: will

text: σ

text: σ

text: denote

text: by

text: E

text: and

text: D

text: Now,

text: we

text: can

text: do

text: the

text: same

text: thing

text: for

text: B

text: and

text: hence

text: we

text: σ,A

text: σ,A

text: obtain

text: subvarieties

text: E

text: D

text: B.

text: Note

text: that,

text: by

text: deﬁnition,

text: π

text: sends

text: E

text: to

text: σ,B

text: σ,B

text: σ,B

text: E

text: and

text: D

text: to

text: D

text: σ,A

text: σ,B

text: σ,A

text: Deﬁne

text: ker(π).

text: Since

text: π

text: is

text: G-equivariant,

text: G

text: acts

text: on

text: and

text: hence

text: we

text: may

text: consider

text: the

text: group

text: G.

text: This

text: group

text: acts

text: on

text: B

text: in

text: the

text: obvious

text: way:

text: acts

text: by

text: translations

text: and

text: G

text: by

text: automorphisms.

text: In

text: particular,

text: we

text: see

text: that

text: the

text: quotient

text: B/(∆

text: G)

text: is

text: isomorphic

text: to

text: A/G.

text: Our

text: goal

text: is

text: to

text: reduce

text: as

text: much

text: as

text: we

text: can

text: the

text: structure

text: of

text: B/G

text: and

text: and

text: to

text: prove

text: that

text: the

text: latter

text: must

text: be

text: trivial

text: in

text: several

text: cases.

text: Fix

text: then

text: a

text: pseudoreﬂection

text: σ

text: G

text: of

text: order

text: r

text: and

text: consider

text: the

text: subvarieties

text: E

text: D

text: A

text: σ,A

text: σ,A

text: and

text: E

text: D

text: B.

text: Deﬁne

text: moreover

text: F

text: E

text: D

text: and

text: F

text: similarly.

text: σ,B

text: σ,B

text: σ,A

text: σ,A

text: σ,A

text: σ,B

text: Then

text: the

text: isogeny

text: π

text: B

text: A

text: sends

text: F

text: to

text: F

text: σ,B

text: σ,A

text: Lemma

text: Let

text: L

text: be

text: the

text: line

text: in

text: T

text: (A)

text: inducing

text: E

text: and

text: E

text: Assume

text: that

text: σ,A

text: σ,B

text: the

text: map

text: F

text: F

text: is

text: surjective

text: and

text: that

text: Λ

text: L

text: Λ

text: L.

text: Then

text: D

text: σ,B

text: σ,A

text: A

text: B

text: σ,B

text: F×σ,A

text: Proof.

text: Since

text: E

text: and

text: D

text: generate

text: A,

text: we

text: have

text: A

text: E

text: D

text: and

text: σ,A

text: σ,A

text: σ,A

text: σ,A

text: the

text: same

text: goes

text: for

text: B.

text: Moreover,

text: the

text: hypothesis

text: Λ

text: L

text: Λ

text: L

text: implies

text: A

text: B

text: that

text: π

text: E

text: E

text: is

text: the

text: identity.

text: We

text: note

text: then

text: that,

text: for

text: x

text: E

text: and

text: σ,B

text: σ,A

text: σ,B

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2 A. ENGSTRO¨M, C. GO, AND M.T. STAMPS values of the Betti numbers and anti-lecture hall composition for a 1-parameter family of distributions, including the uniform distribution. We have organized the paper as follows: Section 2 reviews the main objects of interest and describes the one-to-one-to-one correspondence between them. Section 3 then presents new explicit combinatorial mappings between the main objects. Finally, Section 4 contains closed formulas for the expected Betti numbers and anti-lecture hall composition associated to a random threshold graph. We have attempted to use standard notation wherever possible to make it easier for the more knowledgeable reader to skip ahead to later sections. 2. Preliminaries We begin by reviewing the central objects of this paper, revisiting the main deﬁnitions and the relevant results regarding threshold graphs, Betti numbers of quotients of polynomial rings, and anti-lecture hall compositions. The ﬁrst central class of objects we consider in this paper are threshold graphs. A graph is a pair G = (V, E) where V is a ﬁnite set and E is a subset of pairs of elements in V . The set V = V (G) is called the vertex set of G and the set E = E(G) is called the edge set of G. For a comprehensive introduction to graph theory, we recommend the textbooks by Bollob´as [3] and Diestel [11]. → R Deﬁnition 2.1. A graph G is called threshold if there exists a function ω : V (G) and a ∈ R ∈ ≥ real number t such that uv E(G) if and only if ω(u) + ω(v) t. Example 2.2. The following graph is threshold by taking t = 3, ω(0) = ω(1) = ω(2) = 1, ω(3) = 2, ω(4) = 0, and ω(5) = 3. 0 1 5 2 4 3 Figure 2.1. Threshold graph on six vertices. Threshold graphs were introduced by Chvat´al and Hammer in [6] and [7] and have been studied extensively from structural graph theory, (see Mahadev and Peled’s book [22]) to complex networks (see the paper of Hagberg, Swart, and Schult [19]). They are particularly ##LTLine## ##LTLine##

label: paragraph

text: A.

text: ENGSTRO¨M,

text: C.

text: GO,

text: AND

text: M.T.

text: STAMPS

text: values

text: of

text: the

text: Betti

text: numbers

text: and

text: anti-lecture

text: hall

text: composition

text: for

text: a

text: family

text: of

text: distributions,

text: including

text: the

text: uniform

text: distribution.

text: We

text: have

text: organized

text: the

text: paper

text: as

text: follows:

text: Section

text: reviews

text: the

text: main

text: objects

text: of

text: interest

text: and

text: describes

text: the

text: one-to-one-to-one

text: correspondence

text: between

text: them.

text: Section

text: then

text: presents

text: new

text: explicit

text: combinatorial

text: mappings

text: between

text: the

text: main

text: objects.

text: Finally,

text: Section

text: contains

text: closed

text: formulas

text: for

text: the

text: expected

text: Betti

text: numbers

text: and

text: anti-lecture

text: hall

text: composition

text: associated

text: to

text: a

text: random

text: threshold

text: graph.

text: We

text: have

text: attempted

text: to

text: use

text: standard

text: notation

text: wherever

text: possible

text: to

text: make

text: it

text: easier

text: for

text: the

text: more

text: knowledgeable

text: reader

text: to

text: skip

text: ahead

text: to

text: later

text: sections.

text: Preliminaries

text: We

text: begin

text: by

text: reviewing

text: the

text: central

text: objects

text: of

text: this

text: paper,

text: revisiting

text: the

text: main

text: deﬁnitions

text: and

text: the

text: relevant

text: results

text: regarding

text: threshold

text: graphs,

text: Betti

text: numbers

text: of

text: quotients

text: of

text: polynomial

text: rings,

text: and

text: anti-lecture

text: hall

text: compositions.

text: The

text: ﬁrst

text: central

text: class

text: of

text: objects

text: we

text: consider

text: in

text: this

text: paper

text: are

text: threshold

text: graphs.

text: A

text: graph

text: is

text: a

text: pair

text: G

text: (V,

text: E)

text: where

text: V

text: is

text: a

text: ﬁnite

text: set

text: and

text: E

text: is

text: a

text: subset

text: of

text: pairs

text: of

text: elements

text: in

text: V

text: The

text: set

text: V

text: V

text: (G)

text: is

text: called

text: the

text: vertex

text: set

text: of

text: G

text: and

text: the

text: set

text: E

text: E(G)

text: is

text: called

text: the

text: edge

text: set

text: of

text: G.

text: For

text: a

text: comprehensive

text: introduction

text: to

text: graph

text: theory,

text: we

text: recommend

text: the

text: textbooks

text: by

text: Bollob´as

text: and

text: Diestel

text: R

text: Deﬁnition

text: A

text: graph

text: G

text: is

text: called

text: threshold

text: if

text: there

text: exists

text: a

text: function

text: ω

text: V

text: (G)

text: and

text: a

text: R

text: real

text: number

text: t

text: such

text: that

text: uv

text: E(G)

text: if

text: and

text: only

text: if

text: ω(u)

text: ω(v)

text: t.

text: Example

text: The

text: following

text: graph

text: is

text: threshold

text: by

text: taking

text: t

text: and

text: Figure

text: Threshold

text: graph

text: on

text: six

text: vertices.

text: Threshold

text: graphs

text: were

text: introduced

text: by

text: Chvat´al

text: and

text: Hammer

text: in

text: and

text: and

text: have

text: been

text: studied

text: extensively

text: from

text: structural

text: graph

text: theory,

text: (see

text: Mahadev

text: and

text: Peled’s

text: book

text: to

text: complex

text: networks

text: (see

text: the

text: paper

text: of

text: Hagberg,

text: Swart,

text: and

text: Schult

text: They

text: are

text: particularly

text: ##LTLine##

text: ##LTLine##


text: GRADED EXPECTATIONS 7 T B A 2[3] 3 3 3 {} (0, 0, 0) (0, 0, 0) { } 1 (1, 0, 0) (1, 0, 0) { } 2 (2, 1, 0) (1, 1, 0) { } 3 (3, 3, 1) (1, 1, 1) { } 1, 2 (3, 2, 0) (1, 2, 0) { } 1, 3 (4, 4, 1) (1, 2, 1) { } 2, 3 (5, 6, 2) (1, 2, 2) { } 1, 2, 3 (6, 8, 3) (1, 2, 3) T B A Table 1. The correspondence from Theorem 2.15 between , , and , 3 3 3 where the second column contains the subset of isolated vertices for each graph. T B The correspondence between and follows from a standard construction in combinatorial n n { } commutative algebra: To every graph G with vertex set V (G) = 0, 1, . . . , n , we deﬁne the k coedge ideal of G in R = [x , x , . . . , x ] by 0 1 n (cid:104) | ∈ (cid:105) I (G) = x x uv / E(G) . c u v k Fro¨berg [18] proved that the quotient ring [G] = R/I (G) is 2-linear if and only if G is chordal. c (cid:55)→ k T B Thus, since threshold graphs are chordal, G β( [G]) gives a natural mapping from to . n n Engstr¨om and Stamps gave an explicit proof that this mapping is injective in [15], though it appears that experts have been aware of this fact for some time. B A The correspondence between and follows from the Boij-S¨oderberg theorems, which n n were conjectured by Boij and S¨oderberg in [1], proven by Eisenbud and Schreyer in [14] and extended by Boij and S¨oderberg in [2]. The theorems state that the Betti diagrams of a ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: GRADED

text: EXPECTATIONS

text: T

label: table

text: B

text: A

text: T

label: caption

text: B

text: A

text: Table

text: The

text: correspondence

text: from

text: Theorem

text: between

text: and

text: where

text: the

text: second

text: column

text: contains

text: the

text: subset

text: of

text: isolated

text: vertices

text: for

text: each

text: graph.

text: T

text: B

text: The

text: correspondence

text: between

text: and

text: follows

text: from

text: a

text: standard

text: construction

text: in

text: combinatorial

text: n

text: n

text: commutative

text: algebra:

text: To

text: every

text: graph

text: G

text: with

text: vertex

text: set

text: V

text: (G)

text: n

text: we

text: deﬁne

text: the

text: k

text: coedge

text: ideal

text: of

text: G

text: in

text: R

text: [x

text: x

text: x

text: by

text: n

text: I

text: (G)

text: x

text: x

text: uv

text: E(G)

text: c

text: u

text: v

text: k

text: Fro¨berg

text: proved

text: that

text: the

text: quotient

text: ring

text: [G]

text: R/I

text: (G)

text: is

text: if

text: and

text: only

text: if

text: G

text: is

text: chordal.

text: c

text: k

text: T

text: B

text: Thus,

text: since

text: threshold

text: graphs

text: are

text: chordal,

text: G

text: β(

text: [G])

text: gives

text: a

text: natural

text: mapping

text: from

text: to

text: n

text: n

text: Engstr¨om

text: and

text: Stamps

text: gave

text: an

text: explicit

text: proof

text: that

text: this

text: mapping

text: is

text: injective

text: in

text: though

text: it

text: appears

text: that

text: experts

text: have

text: been

text: aware

text: of

text: this

text: fact

text: for

text: some

text: time.

text: B

text: A

text: The

text: correspondence

text: between

text: and

text: follows

text: from

text: the

text: Boij-S¨oderberg

text: theorems,

text: which

text: n

text: n

text: were

text: conjectured

text: by

text: Boij

text: and

text: S¨oderberg

text: in

text: proven

text: by

text: Eisenbud

text: and

text: Schreyer

text: in

text: and

text: extended

text: by

text: Boij

text: and

text: S¨oderberg

text: in

text: The

text: theorems

text: state

text: that

text: the

text: Betti

text: diagrams

text: of

text: a

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: − − − E (a) after γ0 and γ1 are restricted to the index subset (cid:15)γ−1( bad), there is a proper homotopy between 0 them. ∈ − E ∪ E ∩ − E ∪ E (b) for e−ach s −(cid:15)γ0−1( bad O) (cid:15)γ0+1( bad O), the local orientations of the corresponding rays in γ and γ induce the same orientation of the end if there is one, and otherwise correspond 0 1 under the proper homotopy of (a). (c) the two analogous conditions apply to γ+. i ± Let Z be the result of attaching 1-handles to X along γ (for any choice of orientation-preserving tubular i ± i neighborhood maps ν ). Then there is a cat homeomorphism from Z to Z sending the submanifold X i 0 1 onto itself by a cat homeomorphism cat ambiently isotopic in X to the identity map. It follows that 1-handle attaching is not aﬀected by reparametrization of the rays (a proper homotopy), ± ± or changing the auxiliary diﬀeomorphisms ϕ and ρ occurring in Deﬁnition 2.1 (which only results in changing the parametrization and tubular neighborhood maps, respectively). ≥ Corollary 4.7. For an oriented cat n-manifold X with n 4, every countable multiset of (unordered) pairs of Mittag-Leﬄer ends canonically determines a cat manifold obtained from X by attaching 1- (cid:3) handles at inﬁnity to those pairs of ends, respecting the orientation. R Since the end of n is Mittag-Leﬄer, we immediately obtain cancellation of 0/1-handle pairs at inﬁnity: ≥ R Corollary 4.8. For n 4, every end sum of a cat n-manifold X with n (or countably many copies R (cid:3) of n) is cat homeomorphic to X. See Section for further discussion of 0-handles at inﬁnity. This corollary shows that end summing with an R exotic 4 doesn’t change the homeomorphism type of a smooth 4-manifold (although it typically changes its diﬀeomorphism type); cf. Section . It also shows: ≥ Corollary 4.9. Suppose X and X are connected, oriented cat n-manifolds with n 4, and that X 0 1 − 0 has an end (cid:15) that is cat collared by Sn 1. Then all manifolds obtained as the oriented end sum of X 0 with X at the end (cid:15) are cat homeomorphic. 1 R (cid:3) Proof. Write X as a connected sum X# n. Then any such end sum is X#X . 0 1 The following corollary shows that 1-handles at inﬁnity respect Stein structures. This will be applied to 4-manifold smoothing theory in Theorem 5.4. Corollary 4.10. Every manifold Z obtained from a Stein manifold X by attaching 1-handles at inﬁnity, respecting the complex orientation, admits a Stein structure. The resulting almost-complex structure on Z can be assumed to restrict to the given one on X, up to homotopy. Proof. Since every open, oriented surface has a Stein structure and a contractible space of almost complex ≥ structures, we assume X has real dimension 2m 4. Since X is Stein, it has an exhausting Morse function with indices at most m. It can then be described as the interior of a smooth (self-indexed) handlebody whose handles have index at most m. This is well-known when there are only ﬁnitely many critical points. A proof of the inﬁnite case is given in the appendix of [G09], which also shows that when m = 2 one can preserve the extra framing condition that arises for 2-handles, encoding the given almost-complex structure. By Corollaries 4.4 and 4.7, we can realize the 1-handles at inﬁnity by attaching compact handles to the handlebody before passing to the interior (and after adding inﬁnitely many canceling 0-1 pairs if necessary to accommodate inﬁnitely many new 1-handles, avoiding compactness issues). Now we can convert the handlebody interior back into a Stein manifold by Eliashberg’s Theorem; see [CE12]. (cid:3) The almost-complex structures then correspond by construction. The proof of Theorem 4.6 follows from two lemmas. The ﬁrst guarantees that (a) Mittag-Leﬄer ends are well-deﬁned and (b) singular multirays with a given Mittag-Leﬄer end function are unique up to proper homotopy. 11

label: list

text: E

text: (a)

text: after

text: γ0

text: and

text: γ1

text: are

text: restricted

text: to

text: the

text: index

text: subset

text: bad),

text: there

text: is

text: a

text: proper

text: homotopy

text: between

text: them.

text: E

text: E

text: E

text: E

text: (b)

text: for

text: e−ach

text: s

text: bad

text: O)

text: bad

text: O),

text: the

text: local

text: orientations

text: of

text: the

text: corresponding

text: rays

text: in

text: γ

text: and

text: γ

text: induce

text: the

text: same

text: orientation

text: of

text: the

text: end

text: if

text: there

text: is

text: one,

text: and

text: otherwise

text: correspond

text: under

text: the

text: proper

text: homotopy

text: of

text: (a).

text: (c)

text: the

text: two

text: analogous

text: conditions

text: apply

text: to

text: γ+.

text: i

text: Let

text: Z

text: be

text: the

text: result

text: of

text: attaching

text: to

text: X

text: along

text: γ

text: (for

text: any

text: choice

text: of

text: orientation-preserving

text: tubular

text: i

text: i

text: neighborhood

text: maps

text: ν

text: Then

text: there

text: is

text: a

text: cat

text: homeomorphism

text: from

text: Z

text: to

text: Z

text: sending

text: the

text: submanifold

text: X

text: i

text: onto

text: itself

text: by

text: a

text: cat

text: homeomorphism

text: cat

text: ambiently

text: isotopic

text: in

text: X

text: to

text: the

text: identity

text: map.

text: It

text: follows

text: that

text: attaching

text: is

text: not

text: aﬀected

text: by

text: reparametrization

text: of

text: the

text: rays

text: (a

text: proper

text: homotopy),

text: or

text: changing

text: the

text: auxiliary

text: diﬀeomorphisms

text: ϕ

text: and

text: ρ

text: occurring

text: in

text: Deﬁnition

text: (which

text: only

text: results

text: in

text: changing

text: the

text: parametrization

text: and

text: tubular

text: neighborhood

text: maps,

text: respectively).

text: Corollary

text: For

text: an

text: oriented

text: cat

text: n-manifold

text: X

text: with

text: n

text: every

text: countable

text: multiset

text: of

text: (unordered)

text: pairs

text: of

text: Mittag-Leﬄer

text: ends

text: canonically

text: determines

text: a

text: cat

text: manifold

text: obtained

text: from

text: X

text: by

text: attaching

text: handles

text: at

text: inﬁnity

text: to

text: those

text: pairs

text: of

text: ends,

text: respecting

text: the

text: orientation.

text: R

text: Since

text: the

text: end

text: of

text: n

text: is

text: Mittag-Leﬄer,

text: we

text: immediately

text: obtain

text: cancellation

text: of

text: pairs

text: at

text: inﬁnity:

text: R

text: Corollary

text: For

text: n

text: every

text: end

text: sum

text: of

text: a

text: cat

text: n-manifold

text: X

text: with

text: n

text: (or

text: countably

text: many

text: copies

text: R

text: of

text: n)

text: is

text: cat

text: homeomorphic

text: to

text: X.

text: See

text: Section

text: for

text: further

text: discussion

text: of

text: at

text: inﬁnity.

text: This

text: corollary

text: shows

text: that

text: end

text: summing

text: with

text: an

text: R

text: exotic

text: doesn’t

text: change

text: the

text: homeomorphism

text: type

text: of

text: a

text: smooth

text: (although

text: it

text: typically

text: changes

text: its

text: diﬀeomorphism

text: type);

text: cf.

text: Section

text: It

text: also

text: shows:

text: Corollary

text: Suppose

text: X

text: and

text: X

text: are

text: connected,

text: oriented

text: cat

text: n-manifolds

text: with

text: n

text: and

text: that

text: X

text: has

text: an

text: end

text: that

text: is

text: cat

text: collared

text: by

text: Sn

text: Then

text: all

text: manifolds

text: obtained

text: as

text: the

text: oriented

text: end

text: sum

text: of

text: X

text: with

text: X

text: at

text: the

text: end

text: are

text: cat

text: homeomorphic.

text: R

text: Proof.

text: Write

text: X

text: as

text: a

text: connected

text: sum

text: X#

text: n.

text: Then

text: any

text: such

text: end

text: sum

text: is

text: X#X

text: The

text: following

text: corollary

text: shows

text: that

text: at

text: inﬁnity

text: respect

text: Stein

text: structures.

text: This

text: will

text: be

text: applied

text: to

text: smoothing

text: theory

text: in

text: Theorem

text: Corollary

text: Every

text: manifold

text: Z

text: obtained

text: from

text: a

text: Stein

text: manifold

text: X

text: by

text: attaching

text: at

text: inﬁnity,

text: respecting

text: the

text: complex

text: orientation,

text: admits

text: a

text: Stein

text: structure.

text: The

text: resulting

text: almost-complex

text: structure

text: on

text: Z

text: can

text: be

text: assumed

text: to

text: restrict

text: to

text: the

text: given

text: one

text: on

text: X,

text: up

text: to

text: homotopy.

text: Proof.

text: Since

text: every

text: open,

text: oriented

text: surface

text: has

text: a

text: Stein

text: structure

text: and

text: a

text: contractible

text: space

text: of

text: almost

text: complex

text: structures,

text: we

text: assume

text: X

text: has

text: real

text: dimension

text: Since

text: X

text: is

text: Stein,

text: it

text: has

text: an

text: exhausting

text: Morse

text: function

text: with

text: indices

text: at

text: most

text: m.

text: It

text: can

text: then

text: be

text: described

text: as

text: the

text: interior

text: of

text: a

text: smooth

text: (self-indexed)

text: handlebody

text: whose

text: handles

text: have

text: index

text: at

text: most

text: m.

text: This

text: is

text: well-known

text: when

text: there

text: are

text: only

text: ﬁnitely

text: many

text: critical

text: points.

text: A

text: proof

text: of

text: the

text: inﬁnite

text: case

text: is

text: given

text: in

text: the

text: appendix

text: of

text: which

text: also

text: shows

text: that

text: when

text: m

text: one

text: can

text: preserve

text: the

text: extra

text: framing

text: condition

text: that

text: arises

text: for

text: encoding

text: the

text: given

text: almost-complex

text: structure.

text: By

text: Corollaries

text: and

text: we

text: can

text: realize

text: the

text: at

text: inﬁnity

text: by

text: attaching

text: compact

text: handles

text: to

text: the

text: handlebody

text: before

text: passing

text: to

text: the

text: interior

text: (and

text: after

text: adding

text: inﬁnitely

text: many

text: canceling

text: pairs

text: if

text: necessary

text: to

text: accommodate

text: inﬁnitely

text: many

text: new

text: avoiding

text: compactness

text: issues).

text: Now

text: we

text: can

text: convert

text: the

text: handlebody

text: interior

text: back

text: into

text: a

text: Stein

text: manifold

text: by

text: Eliashberg’s

text: Theorem;

text: see

text: The

text: almost-complex

text: structures

text: then

text: correspond

text: by

text: construction.

text: The

text: proof

text: of

text: Theorem

text: follows

text: from

text: two

text: lemmas.

text: The

text: ﬁrst

text: guarantees

text: that

text: (a)

text: Mittag-Leﬄer

text: ends

text: are

text: well-deﬁned

text: and

text: (b)

text: singular

text: multirays

text: with

text: a

text: given

text: Mittag-Leﬄer

text: end

text: function

text: are

text: unique

text: up

text: to

text: proper

text: homotopy.


text: oriented union of 0- and 1-handles at inﬁnity is determined by its ﬁrst Betti number. As an application of Theorem 6.1, we give a very natural and partly novel proof of the hyperplane unknotting theorem. The novelty here is that 0- and 1-handles at inﬁnity provide the basic framework in which we employ Mazur’s inﬁnite swindle. For simplicity, we assume throughout this section that all manifolds are oriented and all handle addi- tions respect orientations. (cid:70) ≥ (cid:70) Let X be a possibly disconnected cat n-manifold where n 4. Add to X a collection of 0-handles at R inﬁnity W = ∈ w where each w is cat homeomorphic to n. The index set J and all others below i J i i (cid:116) are discrete and countable. Attach to X W a collection of 1-handles at inﬁnity H = ∈ h where × R − i S i each h is cat homeomorphic to [0, 1] n 1 (see Figure 2). By Deﬁnition 2.1 and Theorem 4.6, H is i − × ∞ → (cid:116) determined by multiray data γ , γ+ : S [0, )(cid:44) X W with disjoint images. X h h 1 7 w 1 h w 2 3 h h 3 4 h h 5 8 w 2 w h 4 6 h 9 h w w 10 5 h 6 h h 12 13 11 Figure 2. Manifold Z obtained from the manifold X by adding 0- and 1-handles at inﬁnity, the latter denoted by arcs. { | ∈ } To this data, we associate a graph G deﬁned as follows (see Figure 3). Let v i I be the set i C v 1 1 w 1 D 1 v 2 w 3 P 1 = {v 1 , v 2 , v 4} C 2 v 3 w 4 P 2 = {v 3} w v 4 2 P 3 = {v 5} C 3 w w v 5 6 5 Figure 3. Graph G associated to the construction in Figure 2, and induced partition of the vertices v in X. i 19 ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: oriented

text: union

text: of

text: and

text: at

text: inﬁnity

text: is

text: determined

text: by

text: its

text: ﬁrst

text: Betti

text: number.

text: As

text: an

text: application

text: of

text: Theorem

text: we

text: give

text: a

text: very

text: natural

text: and

text: partly

text: novel

text: proof

text: of

text: the

text: hyperplane

text: unknotting

text: theorem.

text: The

text: novelty

text: here

text: is

text: that

text: and

text: at

text: inﬁnity

text: provide

text: the

text: basic

text: framework

text: in

text: which

text: we

text: employ

text: Mazur’s

text: inﬁnite

text: swindle.

text: For

text: simplicity,

text: we

text: assume

text: throughout

text: this

text: section

text: that

text: all

text: manifolds

text: are

text: oriented

text: and

text: all

text: handle

text: addi-

text: tions

text: respect

text: orientations.

text: Let

text: X

text: be

text: a

text: possibly

text: disconnected

text: cat

text: n-manifold

text: where

text: n

text: Add

text: to

text: X

text: a

text: collection

text: of

text: at

text: R

text: inﬁnity

text: W

text: w

text: where

text: each

text: w

text: is

text: cat

text: homeomorphic

text: to

text: n.

text: The

text: index

text: set

text: J

text: and

text: all

text: others

text: below

text: i

text: J

text: i

text: i

text: are

text: discrete

text: and

text: countable.

text: Attach

text: to

text: X

text: W

text: a

text: collection

text: of

text: at

text: inﬁnity

text: H

text: h

text: where

text: R

text: i

text: S

text: i

text: each

text: h

text: is

text: cat

text: homeomorphic

text: to

text: n

text: (see

text: Figure

text: By

text: Deﬁnition

text: and

text: Theorem

text: H

text: is

text: i

text: determined

text: by

text: multiray

text: data

text: γ

text: γ+

text: S

text: X

text: W

text: with

text: disjoint

text: images.

text: X

text: h

text: h

text: w

text: h

text: w

text: h

text: h

text: h

text: h

text: w

text: w

text: h

text: h

text: h

text: w

text: w

text: h

text: h

text: h

text: Figure

text: Manifold

text: Z

text: obtained

text: from

text: the

text: manifold

text: X

text: by

text: adding

text: and

text: at

text: inﬁnity,

text: the

text: latter

text: denoted

text: by

text: arcs.

text: To

text: this

text: data,

text: we

text: associate

text: a

text: graph

text: G

text: deﬁned

text: as

text: follows

text: (see

text: Figure

text: Let

text: v

text: i

text: I

text: be

text: the

text: set

text: i

text: C

text: v

text: w

text: D

text: v

text: w

text: P

text: {v

text: v

text: v

text: C

text: v

text: w

text: P

text: {v

text: w

text: v

text: P

text: {v

text: C

text: w

text: w

text: v

text: Figure

text: Graph

text: G

text: associated

text: to

text: the

text: construction

text: in

text: Figure

text: and

text: induced

text: partition

text: of

text: the

text: vertices

text: v

text: in

text: X.

text: i

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 14 Luis A. Mateos, Markus Vincze 27. Frisoli, A. and Sotgiu, E. and Procopio, C. and Berga- masco, M. and Rossi, B. and Chisari, C., Rehabilitation Robotics (ICORR), 2011 IEEE International Conference on, Design and implementation of a training strategy in chronic stroke with an arm robotic exoskeleton, 2011, 1-8, 10.1109/ICORR.2011.5975512, 1945-7898 28. Sankai, Y., SICE-ICASE, 2006. International Joint Con- ference, Leading Edge of Cybernics: Robot Suit HAL, 2006, P-1-P-2, 10.1109/SICE.2006.314982 29. Yoshimitsu, T. and Yamamoto, K., SICE 2004 Annual Conference, Development of a power assist suit for nursing work, 2004, 577-580 vol. 1 30. Taal, S.R. and Sankai, Y., Robotics and Automa- tion (ICRA), 2011 IEEE International Conference on, Exoskeletal spine and shoulder girdle for full body exoskeletons with human versatility, 2011, 2217-2222, 10.1109/ICRA.2011.5979863, 1050-4729 31. Sankai, Y., SICE-ICASE, 2006. International Joint Con- ference, Leading Edge of Cybernics: Robot Suit HAL, 2006, P-1-P-2, 10.1109/SICE.2006.314982 32. Dong-hai Wang and Jiajie Guo and Kok-Meng Lee and Can-Jun Yang and Hui Yu, Robotics and Automation (ICRA), 2011 IEEE International Conference on, An adap- tive knee joint exoskeleton based on biological geometries, 2011, 1386-1391, 10.1109/ICRA.2011.5979761, 1050-4729 33. Banchadit, W. and Temram, A. and Sukwan, T. and Owatchaiyapong, P. and Suthakorn, J., Robotics and Biomimetics (ROBIO), 2012 IEEE International Confer- ence on, Design and implementation of a new motorized- mechanical exoskeleton based on CGA Patternized Control, 2012, 1668-1673, 10.1109/ROBIO.2012.6491207 34. Mateos, L. A. and Sousa, M. and Vincze, M., book, 2011 15th International Conference on Advanced Robotics (ICAR), DeWaLoP Remote control for in-pipe robot, 2011, 518 -523 ##LTLine##

text: Luis

label: author

text: A.

text: Mateos,

text: Markus

text: Vincze

label: reference

text: Frisoli,

text: A.

text: and

text: Sotgiu,

text: E.

text: and

text: Procopio,

text: C.

text: and

text: Berga-

text: masco,

text: M.

text: and

text: Rossi,

text: B.

text: and

text: Chisari,

text: C.,

text: Rehabilitation

text: Robotics

text: (ICORR),

text: IEEE

text: International

text: Conference

text: on,

text: Design

text: and

text: implementation

text: of

text: a

text: training

text: strategy

text: in

text: chronic

text: stroke

text: with

text: an

text: arm

text: robotic

text: exoskeleton,

text: Sankai,

text: Y.,

text: SICE-ICASE,

text: International

text: Joint

text: Con-

text: ference,

text: Leading

text: Edge

text: of

text: Cybernics:

text: Robot

text: Suit

text: HAL,

text: Yoshimitsu,

text: T.

text: and

text: Yamamoto,

text: K.,

text: SICE

text: Annual

text: Conference,

text: Development

text: of

text: a

text: power

text: assist

text: suit

text: for

text: nursing

text: work,

text: vol.

text: Taal,

text: S.R.

text: and

text: Sankai,

text: Y.,

text: Robotics

text: and

text: Automa-

text: tion

text: (ICRA),

text: IEEE

text: International

text: Conference

text: on,

text: Exoskeletal

text: spine

text: and

text: shoulder

text: girdle

text: for

text: full

text: body

text: exoskeletons

text: with

text: human

text: versatility,

text: Sankai,

text: Y.,

text: SICE-ICASE,

text: International

text: Joint

text: Con-

text: ference,

text: Leading

text: Edge

text: of

text: Cybernics:

text: Robot

text: Suit

text: HAL,

text: Dong-hai

text: Wang

text: and

text: Jiajie

text: Guo

text: and

text: Kok-Meng

text: Lee

text: and

text: Can-Jun

text: Yang

text: and

text: Hui

text: Yu,

text: Robotics

text: and

text: Automation

text: (ICRA),

text: IEEE

text: International

text: Conference

text: on,

text: An

text: adap-

text: tive

text: knee

text: joint

text: exoskeleton

text: based

text: on

text: biological

text: geometries,

text: Banchadit,

text: W.

text: and

text: Temram,

text: A.

text: and

text: Sukwan,

text: T.

text: and

text: Owatchaiyapong,

text: P.

text: and

text: Suthakorn,

text: J.,

text: Robotics

text: and

text: Biomimetics

text: (ROBIO),

text: IEEE

text: International

text: Confer-

text: ence

text: on,

text: Design

text: and

text: implementation

text: of

text: a

text: new

text: motorized-

text: mechanical

text: exoskeleton

text: based

text: on

text: CGA

text: Patternized

text: Control,

text: Mateos,

text: L.

text: A.

text: and

text: Sousa,

text: M.

text: and

text: Vincze,

text: M.,

text: book,

text: International

text: Conference

text: on

text: Advanced

text: Robotics

text: (ICAR),

text: DeWaLoP

text: Remote

text: control

text: for

text: in-pipe

text: robot,

text: ##LTLine##


text: 6 Luis A. Mateos, Markus Vincze Fig. 6 DeWaLoP in-pipe robot perspective view. 5 Evaluation of the LaMMos Mechanism in DeWaLoP in-pipe Robot Stiﬀness to extended wheeled-legs Another constraint of the in-pipe robot is that once inside the pipe and in locations where its required to The LaMMos mechanism is intended to improve the rehabilitate the pipe. The wheeled-legs extend creating DeWaLoP robot in two diﬀerent ways. The ﬁrst is to a centered structure. However, the maximum force the reconﬁgure the top wheeled-legs for easy input of the legs can hold is limited to linear actuator speciﬁcations. robot in the smaller pipe diameter. And the second is Hence, if a locking mechanism attaches each wheeled- to add stiﬀness to the wheeled-legs once they are ex- leg to the maintenance unit structure, then the dynam- tended forming a centered structure inside the pipe. ical structure formed by extending the legs increases its stiﬀness. Easy robot insertion The DeWaLoP robot has been designed to work in In following sections we will ﬁrst describe the struc- pipes with diameters ranging from 800mm to 1000mm, ture of the robot wheeled-legs, then how we install the where the robot is able to move and perform the rede- velopment task. However, to insert the robot into the 800mm diameter pipe requires precision and eﬀort, as the gas springs of each wheeled-leg must be compressed by 30mm for creating the space to enter the pipe, as shown in Fig. 7a. The compress force needs to be at least 400N. In other words, the operators must push the robot into the pipe and at the same time push each ≥ of its wheeled-legs with a force F 400N, to compress the springs and insert the robot into the 800mm diam- eter pipe. Fig. 7 DeWaLoP in-pipe robot front view. a) Before in- Instead of using brute force to insert the robot into stalling the LaMMos mechanism, to insert the robot into the the pipe, an alternative solution is to lower its top 800mm diameter pipe. All wheeled-legs must compress its wheeled-legs. In such way, the robot can be easily in- 400N gas spring by 30mm for clearance of the legs to the serted into the pipe with minimal eﬀort, protecting the pipe. b) Inserting the robot into the 800mm diameter pipe with the top wheeled-legs lowered by LaMMos mechanism, legs from hitting the pipe while entering it, as shown in enabling a clearance distance of 116mm for easy insertion Fig. 7b. And once inside the pipe the robot reconﬁgure and protection of the wheeled-legs from hitting the pipe while the wheeled-legs as original. entering. ##LTFigure## ##LTFigure## ##LTLine##

text: Luis

text: A.

text: Mateos,

text: Markus

text: Vincze

text: Fig.

text: DeWaLoP

text: in-pipe

text: robot

text: perspective

text: view.

label: section

text: Evaluation

text: of

text: the

text: LaMMos

text: Mechanism

text: in

text: DeWaLoP

text: in-pipe

text: Robot

text: Stiﬀness

text: to

text: extended

text: wheeled-legs

text: Another

text: constraint

text: of

text: the

text: in-pipe

text: robot

text: is

text: that

text: once

text: inside

text: the

text: pipe

text: and

text: in

text: locations

text: where

text: its

text: required

text: to

text: The

text: LaMMos

text: mechanism

text: is

text: intended

text: to

text: improve

text: the

text: rehabilitate

text: the

text: pipe.

text: The

text: wheeled-legs

text: extend

text: creating

text: DeWaLoP

text: robot

text: in

text: two

text: diﬀerent

text: ways.

text: The

text: ﬁrst

text: is

text: to

text: a

text: centered

text: structure.

text: However,

text: the

text: maximum

text: force

text: the

text: reconﬁgure

text: the

text: top

text: wheeled-legs

text: for

text: easy

text: input

text: of

text: the

text: legs

text: can

text: hold

text: is

text: limited

text: to

text: linear

text: actuator

text: speciﬁcations.

text: robot

text: in

text: the

text: smaller

text: pipe

text: diameter.

text: And

text: the

text: second

text: is

text: Hence,

text: if

text: a

text: locking

text: mechanism

text: attaches

text: each

text: wheeled-

text: to

text: add

text: stiﬀness

text: to

text: the

text: wheeled-legs

text: once

text: they

text: are

text: ex-

text: leg

text: to

text: the

text: maintenance

text: unit

text: structure,

text: then

text: the

text: dynam-

text: tended

text: forming

text: a

text: centered

text: structure

text: inside

text: the

text: pipe.

text: ical

text: structure

text: formed

text: by

text: extending

text: the

text: legs

text: increases

text: its

text: stiﬀness.

text: Easy

text: robot

text: insertion

text: The

text: DeWaLoP

text: robot

text: has

text: been

text: designed

text: to

text: work

text: in

text: In

text: following

text: sections

text: we

text: will

text: ﬁrst

text: describe

text: the

text: struc-

text: pipes

text: with

text: diameters

text: ranging

text: from

text: to

text: ture

text: of

text: the

text: robot

text: wheeled-legs,

text: then

text: how

text: we

text: install

text: the

text: where

text: the

text: robot

text: is

text: able

text: to

text: move

text: and

text: perform

text: the

text: rede-

text: velopment

text: task.

text: However,

text: to

text: insert

text: the

text: robot

text: into

text: the

text: diameter

text: pipe

text: requires

text: precision

text: and

text: eﬀort,

text: as

text: the

text: gas

text: springs

text: of

text: each

text: wheeled-leg

text: must

text: be

text: compressed

text: by

text: for

text: creating

text: the

text: space

text: to

text: enter

text: the

text: pipe,

text: as

text: shown

text: in

text: Fig.

text: The

text: compress

text: force

text: needs

text: to

text: be

text: at

text: least

text: In

text: other

text: words,

text: the

text: operators

text: must

text: push

text: the

text: robot

text: into

text: the

text: pipe

text: and

text: at

text: the

text: same

text: time

text: push

text: each

text: of

text: its

text: wheeled-legs

text: with

text: a

text: force

text: F

text: to

text: compress

text: the

text: springs

text: and

text: insert

text: the

text: robot

text: into

text: the

text: diam-

text: eter

text: pipe.

text: Fig.

text: DeWaLoP

text: in-pipe

text: robot

text: front

text: view.

text: a)

text: Before

text: in-

text: Instead

text: of

text: using

text: brute

text: force

text: to

text: insert

text: the

text: robot

text: into

text: stalling

text: the

text: LaMMos

text: mechanism,

text: to

text: insert

text: the

text: robot

text: into

text: the

text: the

text: pipe,

text: an

text: alternative

text: solution

text: is

text: to

text: lower

text: its

text: top

text: diameter

text: pipe.

text: All

text: wheeled-legs

text: must

text: compress

text: its

text: wheeled-legs.

text: In

text: such

text: way,

text: the

text: robot

text: can

text: be

text: easily

text: in-

text: gas

text: spring

text: by

text: for

text: clearance

text: of

text: the

text: legs

text: to

text: the

text: serted

text: into

text: the

text: pipe

text: with

text: minimal

text: eﬀort,

text: protecting

text: the

text: pipe.

text: b)

text: Inserting

text: the

text: robot

text: into

text: the

text: diameter

text: pipe

text: with

text: the

text: top

text: wheeled-legs

text: lowered

text: by

text: LaMMos

text: mechanism,

text: legs

text: from

text: hitting

text: the

text: pipe

text: while

text: entering

text: it,

text: as

text: shown

text: in

text: enabling

text: a

text: clearance

text: distance

text: of

text: for

text: easy

text: insertion

text: Fig.

text: And

text: once

text: inside

text: the

text: pipe

text: the

text: robot

text: reconﬁgure

text: and

text: protection

text: of

text: the

text: wheeled-legs

text: from

text: hitting

text: the

text: pipe

text: while

text: the

text: wheeled-legs

text: as

text: original.

text: entering.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: ∗ An introduction to Graph Data Management Renzo Angles1,3 and Claudio Gutierrez2,3 1Dept. of Computer Science, Universidad de Talca, Chile (rangles@utalca.cl) 2Dept. of Computer Science, Universidad de Chile, Chile (cgutierr@dcc.uchile.cl) 3Center for Semantic Web Research (http://ciws.cl/) Abstract A graph database is a database where the data structures for the schema and/or instances are modeled as a (labeled)(directed) graph or generalizations of it, and where querying is expressed by graph- oriented operations and type constructors. In this article we present the basic notions of graph databases, give an historical overview of its main development, and study the main current systems that implement them. 1 Introduction It has been long recognized that graphs are a natural way to represent information and knowledge. In fact, the notion of “graph database” has a long development, at least since the 1980’s. But it is only recently that sev- eral technological developments have made it possible to make this abstract idea a reality. Powerful hardware to store and process graphs, powerful sensors to record directly the information, powerful machines that allow to analyze and visualize graphs, among other factors, have given rise to the current ﬂourishing in the area of graph data management. ∗ Work funded by the Millennium Nucleus Center for Semantic Web Research under Grant NC120004. 1 ##LTLine##

label: title

text: An

text: introduction

text: to

text: Graph

text: Data

text: Management

text: Renzo

text: and

text: Claudio

text: of

text: Computer

text: Science,

text: Universidad

text: de

text: Talca,

text: Chile

text: (rangles@utalca.cl)

text: of

text: Computer

text: Science,

text: Universidad

text: de

text: Chile,

text: Chile

text: (cgutierr@dcc.uchile.cl)

text: for

text: Semantic

text: Web

text: Research

text: Abstract

text: A

label: abstract

text: graph

text: database

text: is

text: a

text: database

text: where

text: the

text: data

text: structures

text: for

text: the

text: schema

text: and/or

text: instances

text: are

text: modeled

text: as

text: a

text: (labeled)(directed)

text: graph

text: or

text: generalizations

text: of

text: it,

text: and

text: where

text: querying

text: is

text: expressed

text: by

text: graph-

text: oriented

text: operations

text: and

text: type

text: constructors.

text: In

text: this

text: article

text: we

text: present

text: the

text: basic

text: notions

text: of

text: graph

text: databases,

text: give

text: an

text: historical

text: overview

text: of

text: its

text: main

text: development,

text: and

text: study

text: the

text: main

text: current

text: systems

text: that

text: implement

text: them.

text: Introduction

text: It

text: has

text: been

text: long

text: recognized

text: that

text: graphs

text: are

text: a

text: natural

text: way

text: to

text: represent

text: information

text: and

text: knowledge.

text: In

text: fact,

text: the

text: notion

text: of

text: “graph

text: database”

text: has

text: a

text: long

text: development,

text: at

text: least

text: since

text: the

text: But

text: it

text: is

text: only

text: recently

text: that

text: sev-

text: eral

text: technological

text: developments

text: have

text: made

text: it

text: possible

text: to

text: make

text: this

text: abstract

text: idea

text: a

text: reality.

text: Powerful

text: hardware

text: to

text: store

text: and

text: process

text: graphs,

text: powerful

text: sensors

text: to

text: record

text: directly

text: the

text: information,

text: powerful

text: machines

text: that

text: allow

text: to

text: analyze

text: and

text: visualize

text: graphs,

text: among

text: other

text: factors,

text: have

text: given

text: rise

text: to

text: the

text: current

text: ﬂourishing

text: in

text: the

text: area

text: of

text: graph

text: data

text: management.

text: Work

text: funded

text: by

text: the

text: Millennium

text: Nucleus

text: Center

text: for

text: Semantic

text: Web

text: Research

text: under

text: Grant

text: ##LTLine##


text: There are two broad and interrelated topics in this area that from our perspective deserve to be treated separately today. One is the area of graph database models, which comprises general principles that ideally should guide the design of systems. The second is graph database systems them- selves, which are system that deal with graph data processing, sometimes addressing directly demands of users, thus emphasizing factors such as eﬃ- ciency, usability and direct solutions to urgent data management problems. Graph database models. The fundamental abstraction behind a database system is its database model. In the most general sense, a database model (or just data model) is a conceptual tool used to model representations of real world entities and the relationships among them. As is well known, a data model can be characterized by three basic components, namely data structures, query and transformation language, and integrity constraints. Following this deﬁnition, a graph database model is a model where data structures for the schema and/or instances are modeled as graphs (or gen- eralizations of them), where the data manipulation is expressed by graph- oriented operations (i.e. a graph query language), and appropriate integrity constraints can be deﬁned over the graph structure The main characteristic of a graph database is that the data are concep- tually modeled and presented to the user as a graph, that is, the data struc- tures (data and/or schema) are represented by graphs, or by data structures generalizing the notion of graph (e.g. hypergraphs or hypernodes). One of the main features of a graph structure is the simplicity to model unstruc- tured data. Therefore, in graph models the separation between schema and data (instances) is less marked than in the classical relational model. Regarding data manipulation and querying, it is is expressed by graph transformations, or by operations whose main primitives are based on graph features like paths, neighborhoods, subgraphs, graph patterns, connectivity, and graph statistics (diameter, centrality, etc.). Some graph models deﬁne a ﬂexible collection of type constructors and operations, which are used to create and access the graph data structures. Another approach is to express all queries using a few powerful graph manipulation primitives. Usually the query language is what gives a database model its particular ﬂavor. In fact, the diﬀerences among graph data structures are usually minors as compared to diﬀerences among graph query languages. Finally, integrity constraints enforce data consistency. These constraints can be grouped in schema-instance consistency, identity and referential in- tegrity, and functional and inclusion dependencies. Examples of these are labels with unique names, typing constraints on nodes functional dependen- cies, domain and range of properties, etc. 2

text: There

text: are

text: two

text: broad

text: and

text: interrelated

text: topics

text: in

text: this

text: area

text: that

text: from

text: our

text: perspective

text: deserve

text: to

text: be

text: treated

text: separately

text: today.

text: One

text: is

text: the

text: area

text: of

text: graph

text: database

text: models,

text: which

text: comprises

text: general

text: principles

text: that

text: ideally

text: should

text: guide

text: the

text: design

text: of

text: systems.

text: The

text: second

text: is

text: graph

text: database

text: systems

text: them-

text: selves,

text: which

text: are

text: system

text: that

text: deal

text: with

text: graph

text: data

text: processing,

text: sometimes

text: addressing

text: directly

text: demands

text: of

text: users,

text: thus

text: emphasizing

text: factors

text: such

text: as

text: eﬃ-

text: ciency,

text: usability

text: and

text: direct

text: solutions

text: to

text: urgent

text: data

text: management

text: problems.

text: Graph

text: database

text: models.

text: The

text: fundamental

text: abstraction

text: behind

text: a

text: database

text: system

text: is

text: its

text: database

text: model.

text: In

text: the

text: most

text: general

text: sense,

text: a

text: database

text: model

text: (or

text: just

text: data

text: model)

text: is

text: a

text: conceptual

text: tool

text: used

text: to

text: model

text: representations

text: of

text: real

text: world

text: entities

text: and

text: the

text: relationships

text: among

text: them.

text: As

text: is

text: well

text: known,

text: a

text: data

text: model

text: can

text: be

text: characterized

text: by

text: three

text: basic

text: components,

text: namely

text: data

text: structures,

text: query

text: and

text: transformation

text: language,

text: and

text: integrity

text: constraints.

text: Following

text: this

text: deﬁnition,

text: a

text: graph

text: database

text: model

text: is

text: a

text: model

text: where

text: data

text: structures

text: for

text: the

text: schema

text: and/or

text: instances

text: are

text: modeled

text: as

text: graphs

text: (or

text: gen-

text: eralizations

text: of

text: them),

text: where

text: the

text: data

text: manipulation

text: is

text: expressed

text: by

text: graph-

text: oriented

text: operations

text: (i.e.

text: a

text: graph

text: query

text: language),

text: and

text: appropriate

text: integrity

text: constraints

text: can

text: be

text: deﬁned

text: over

text: the

text: graph

text: structure

text: The

text: main

text: characteristic

text: of

text: a

text: graph

text: database

text: is

text: that

text: the

text: data

text: are

text: concep-

text: tually

text: modeled

text: and

text: presented

text: to

text: the

text: user

text: as

text: a

text: graph,

text: that

text: is,

text: the

text: data

text: struc-

text: tures

text: (data

text: and/or

text: schema)

text: are

text: represented

text: by

text: graphs,

text: or

text: by

text: data

text: structures

text: generalizing

text: the

text: notion

text: of

text: graph

text: (e.g.

text: hypergraphs

text: or

text: hypernodes).

text: One

text: of

text: the

text: main

text: features

text: of

text: a

text: graph

text: structure

text: is

text: the

text: simplicity

text: to

text: model

text: unstruc-

text: tured

text: data.

text: Therefore,

text: in

text: graph

text: models

text: the

text: separation

text: between

text: schema

text: and

text: data

text: (instances)

text: is

text: less

text: marked

text: than

text: in

text: the

text: classical

text: relational

text: model.

text: Regarding

text: data

text: manipulation

text: and

text: querying,

text: it

text: is

text: is

text: expressed

text: by

text: graph

text: transformations,

text: or

text: by

text: operations

text: whose

text: main

text: primitives

text: are

text: based

text: on

text: graph

text: features

text: like

text: paths,

text: neighborhoods,

text: subgraphs,

text: graph

text: patterns,

text: connectivity,

text: and

text: graph

text: statistics

text: (diameter,

text: centrality,

text: etc.).

text: Some

text: graph

text: models

text: deﬁne

text: a

text: ﬂexible

text: collection

text: of

text: type

text: constructors

text: and

text: operations,

text: which

text: are

text: used

text: to

text: create

text: and

text: access

text: the

text: graph

text: data

text: structures.

text: Another

text: approach

text: is

text: to

text: express

text: all

text: queries

text: using

text: a

text: few

text: powerful

text: graph

text: manipulation

text: primitives.

text: Usually

text: the

text: query

text: language

text: is

text: what

text: gives

text: a

text: database

text: model

text: its

text: particular

text: ﬂavor.

text: In

text: fact,

text: the

text: diﬀerences

text: among

text: graph

text: data

text: structures

text: are

text: usually

text: minors

text: as

text: compared

text: to

text: diﬀerences

text: among

text: graph

text: query

text: languages.

text: Finally,

text: integrity

text: constraints

text: enforce

text: data

text: consistency.

text: These

text: constraints

text: can

text: be

text: grouped

text: in

text: schema-instance

text: consistency,

text: identity

text: and

text: referential

text: in-

text: tegrity,

text: and

text: functional

text: and

text: inclusion

text: dependencies.

text: Examples

text: of

text: these

text: are

text: labels

text: with

text: unique

text: names,

text: typing

text: constraints

text: on

text: nodes

text: functional

text: dependen-

text: cies,

text: domain

text: and

text: range

text: of

text: properties,

text: etc.


text: Figure 6: RDF data model. Note that schema and instance are mixed together. The edges labeled type disconnect the instance from the schema. The instance is built by the subgraphs obtained by instantiating the nodes of the schema, and establishing the corresponding parent edges between these subgraphs. expression is a set of such triples called an RDF Graph (see example in Figure 6), which can be intuitively considered as a semantic network. From the second perspective, the RDF model is the most general representation of a graph, where edges are also considered nodes. In this sense, formally is not a traditional graph [84]. This allows to self-references, reiﬁcation (i.e. making statements over statements), and essentially be self-contained. The drawback of all this niceties are the complexity that come with this generalization, particularly for eﬃcient implementation. SPARQL [124] is the standard query language for RDF. It is able to express complex graph patterns by means of a collection of triple patterns whose solutions can be combined and restricted by using several operators (i.e. AND, UNION, OPTIONAL, and FILTER). The latest version of the language, SPARQL 1.1 [71], includes explicit operators to express negation of graph patterns, arbitrary length path matching (i.e. reachability), aggregate operators (e.g. COUNT), subqueries, and query federation. 3.6 Nodes, edges and properties: The Property graph model 13 ##LTFigure##

text: Figure

text: RDF

text: data

text: model.

text: Note

text: that

text: schema

text: and

text: instance

text: are

text: mixed

text: together.

text: The

text: edges

text: labeled

text: type

text: disconnect

text: the

text: instance

text: from

text: the

text: schema.

text: The

text: instance

text: is

text: built

text: by

text: the

text: subgraphs

text: obtained

text: by

text: instantiating

text: the

text: nodes

text: of

text: the

text: schema,

text: and

text: establishing

text: the

text: corresponding

text: parent

text: edges

text: between

text: these

text: subgraphs.

text: expression

text: is

text: a

text: set

text: of

text: such

text: triples

text: called

text: an

text: RDF

text: Graph

text: (see

text: example

text: in

text: Figure

text: which

text: can

text: be

text: intuitively

text: considered

text: as

text: a

text: semantic

text: network.

text: From

text: the

text: second

text: perspective,

text: the

text: RDF

text: model

text: is

text: the

text: most

text: general

text: representation

text: of

text: a

text: graph,

text: where

text: edges

text: are

text: also

text: considered

text: nodes.

text: In

text: this

text: sense,

text: formally

text: is

text: not

text: a

text: traditional

text: graph

text: This

text: allows

text: to

text: self-references,

text: reiﬁcation

text: (i.e.

text: making

text: statements

text: over

text: statements),

text: and

text: essentially

text: be

text: self-contained.

text: The

text: drawback

text: of

text: all

text: this

text: niceties

text: are

text: the

text: complexity

text: that

text: come

text: with

text: this

text: generalization,

text: particularly

text: for

text: eﬃcient

text: implementation.

text: SPARQL

text: is

text: the

text: standard

text: query

text: language

text: for

text: RDF.

text: It

text: is

text: able

text: to

text: express

text: complex

text: graph

text: patterns

text: by

text: means

text: of

text: a

text: collection

text: of

text: triple

text: patterns

text: whose

text: solutions

text: can

text: be

text: combined

text: and

text: restricted

text: by

text: using

text: several

text: operators

text: (i.e.

text: AND,

text: UNION,

text: OPTIONAL,

text: and

text: FILTER).

text: The

text: latest

text: version

text: of

text: the

text: language,

text: SPARQL

text: includes

text: explicit

text: operators

text: to

text: express

text: negation

text: of

text: graph

text: patterns,

text: arbitrary

text: length

text: path

text: matching

text: (i.e.

text: reachability),

text: aggregate

text: operators

text: (e.g.

text: COUNT),

text: subqueries,

text: and

text: query

text: federation.

text: Nodes,

text: edges

text: and

text: properties:

text: The

text: Property

text: graph

text: model

text: ##LTFigure##


text: via special operators that allow to summarize the query results, or by ad-hoc functions hiding complex algorithms. Summarization queries can be expressed in a query language by using the so-called aggregate operators (e.g., average, count, maximum, etc.). These operators can be used to calculate the order of the graph (i.e., the number of vertices), the degree of a node (i.e., the number of neighbors of the node), the minimum / maximum / average degree in the graph, the length of a path (i.e., the number of edges in the path), the distance between nodes (i.e., the length of a shortest path between the nodes), among others “simple” analytical queries. Complex analytical queries are related to compute important algorithms for graph analysis and mining (see [36] for a extensive review). Examples of such graph algorithms are: • Characteristic path length. It is the average shortest path length in a network. It measures the average degree of separation between the nodes. • Connected components. It is an algorithm for extracting groups of vertices that can reach each other via graph edges. • Community detection. This algorithm deals with the discovery of groups whose constituent nodes form more relationships within the group than with nodes outside the group. • Clustering coeﬃcient. The clustering coeﬃcient of a node is the prob- ability that the neighbors of the node are also connected to each other. The average clustering coeﬃcient of the whole graph is the average of the clustering coeﬃcients of all individual nodes. • PageRank This algorithm, created in the context of web searching, models the behavior of an idealized random Web surfer. The PageR- ank score of a webpage represents the probability that the random Web surfer chooses to view the webpage. This algorithm can be an eﬀective method to measure the relative importance of nodes in a data graph. Complex analytical queries are the speciality of graph processing frame- works due to their facilities for implementing and running complex algo- rithms over large graphs. More details about these queries can be found in articles comparing graph processing frameworks (e.g. [78] and [149]). 19

text: via

text: special

text: operators

text: that

text: allow

text: to

text: summarize

text: the

text: query

text: results,

text: or

text: by

text: ad-hoc

text: functions

text: hiding

text: complex

text: algorithms.

text: Summarization

text: queries

text: can

text: be

text: expressed

text: in

text: a

text: query

text: language

text: by

text: using

text: the

text: so-called

text: aggregate

text: operators

text: (e.g.,

text: average,

text: count,

text: maximum,

text: etc.).

text: These

text: operators

text: can

text: be

text: used

text: to

text: calculate

text: the

text: order

text: of

text: the

text: graph

text: (i.e.,

text: the

text: number

text: of

text: vertices),

text: the

text: degree

text: of

text: a

text: node

text: (i.e.,

text: the

text: number

text: of

text: neighbors

text: of

text: the

text: node),

text: the

text: minimum

text: maximum

text: average

text: degree

text: in

text: the

text: graph,

text: the

text: length

text: of

text: a

text: path

text: (i.e.,

text: the

text: number

text: of

text: edges

text: in

text: the

text: path),

text: the

text: distance

text: between

text: nodes

text: (i.e.,

text: the

text: length

text: of

text: a

text: shortest

text: path

text: between

text: the

text: nodes),

text: among

text: others

text: “simple”

text: analytical

text: queries.

text: Complex

text: analytical

text: queries

text: are

text: related

text: to

text: compute

text: important

text: algorithms

text: for

text: graph

text: analysis

text: and

text: mining

text: (see

text: for

text: a

text: extensive

text: review).

text: Examples

text: of

text: such

text: graph

text: algorithms

text: are:

text: Characteristic

text: path

text: length.

text: It

text: is

text: the

text: average

text: shortest

text: path

text: length

text: in

text: a

text: network.

text: It

text: measures

text: the

text: average

text: degree

text: of

text: separation

text: between

text: the

text: nodes.

text: Connected

text: components.

text: It

text: is

text: an

text: algorithm

text: for

text: extracting

text: groups

text: of

text: vertices

text: that

text: can

text: reach

text: each

text: other

text: via

text: graph

text: edges.

text: Community

text: detection.

text: This

text: algorithm

text: deals

text: with

text: the

text: discovery

text: of

text: groups

text: whose

text: constituent

text: nodes

text: form

text: more

text: relationships

text: within

text: the

text: group

text: than

text: with

text: nodes

text: outside

text: the

text: group.

text: Clustering

text: coeﬃcient.

text: The

text: clustering

text: coeﬃcient

text: of

text: a

text: node

text: is

text: the

text: prob-

text: ability

text: that

text: the

text: neighbors

text: of

text: the

text: node

text: are

text: also

text: connected

text: to

text: each

text: other.

text: The

text: average

text: clustering

text: coeﬃcient

text: of

text: the

text: whole

text: graph

text: is

text: the

text: average

text: of

text: the

text: clustering

text: coeﬃcients

text: of

text: all

text: individual

text: nodes.

text: PageRank

text: This

text: algorithm,

text: created

text: in

text: the

text: context

text: of

text: web

text: searching,

text: models

text: the

text: behavior

text: of

text: an

text: idealized

text: random

text: Web

text: surfer.

text: The

text: PageR-

text: ank

text: score

text: of

text: a

text: webpage

text: represents

text: the

text: probability

text: that

text: the

text: random

text: Web

text: surfer

text: chooses

text: to

text: view

text: the

text: webpage.

text: This

text: algorithm

text: can

text: be

text: an

text: eﬀective

text: method

text: to

text: measure

text: the

text: relative

text: importance

text: of

text: nodes

text: in

text: a

text: data

text: graph.

text: Complex

text: analytical

text: queries

text: are

text: the

text: speciality

text: of

text: graph

text: processing

text: frame-

text: works

text: due

text: to

text: their

text: facilities

text: for

text: implementing

text: and

text: running

text: complex

text: algo-

text: rithms

text: over

text: large

text: graphs.

text: More

text: details

text: about

text: these

text: queries

text: can

text: be

text: found

text: in

text: articles

text: comparing

text: graph

text: processing

text: frameworks

text: (e.g.

text: and


text: 4.2 A short review of graph query languages In the literature of graph data management there is substantial work on graph query languages (GQLs). A review of GQLs proposed during the ﬁrst wave of graph databases was presented in [42]. Based on this, Wood [143] studied several GQLs focusing on their expressive power and computational complexity. A review and comparison of practical query languages provided by graph databases (available at the time) was presented in [39]. Recently, Barcelo [44] studied the problem of querying graph databases, in particular the expressiveness and complexity of several navigational query languages. To the best of our knowledge, the ﬁrst graph query language was pro- posed in 1987 by Cruz, Mendelzon and Wood (i.e. the language G). After that, several theoretical GQLs have been proposed, in some cases accom- panying the deﬁnition of a graph data model. It has been just in the last ten years that practical GQLs are available thanks to the release of graph database systems. Example of this is Cypher, the query language provided by the Neo4j graph database. Although a GQL is normally related to a graph database model, this relation is no exclusive. For instance, several object-oriented data models deﬁned graph-based languages to manipulate the objects in the database (e.g. GraphDB [126] and G-Log[121]), or to represent database transfor- mations (e.g. GOOD [80] and GUL [86]). A similar situation occurred for semistructured data models when graph-oriented operations are used to navigate the tree-based data (e.g. Lorel [34] and UnQL [51]). Additionally, several graph-based query languages have been designed for speciﬁc applica- tions domains, in particular those related to complex networks, for instance social networks (e.g. SoQL [129]), biological networks (e.g. DNAQL [48]), bibliographical networks (e.g. BiQL [68]), the Web (e.g. WebSQL [68]) and the Semantic Web (e.g. SPARQL [83]). For the sake of space we will not present a complete review of graph query languages. Instead we describe some of the languages we consider relevant and useful to show the developments in the area. Moreover, we restrict our review to “pure” GQLs, that is those languages speciﬁcally designed to work with graph data models. Figure 8 presents this subset of languages in chronological order. As we mentioned before, Cruz et al. [63] proposed the query language G. This language introduced the notion of graphical query as a set of query graphs. A query graph (pattern) is a labeled directed multigraph in which the node labels may be either variables or constants, and the edge labels can be regular expressions combining variables and constants. The result 20

text: A

text: short

text: review

text: of

text: graph

text: query

text: languages

text: In

text: the

text: literature

text: of

text: graph

text: data

text: management

text: there

text: is

text: substantial

text: work

text: on

text: graph

text: query

text: languages

text: (GQLs).

text: A

text: review

text: of

text: GQLs

text: proposed

text: during

text: the

text: ﬁrst

text: wave

text: of

text: graph

text: databases

text: was

text: presented

text: in

text: Based

text: on

text: this,

text: Wood

text: studied

text: several

text: GQLs

text: focusing

text: on

text: their

text: expressive

text: power

text: and

text: computational

text: complexity.

text: A

text: review

text: and

text: comparison

text: of

text: practical

text: query

text: languages

text: provided

text: by

text: graph

text: databases

text: (available

text: at

text: the

text: time)

text: was

text: presented

text: in

text: Recently,

text: Barcelo

text: studied

text: the

text: problem

text: of

text: querying

text: graph

text: databases,

text: in

text: particular

text: the

text: expressiveness

text: and

text: complexity

text: of

text: several

text: navigational

text: query

text: languages.

text: To

text: the

text: best

text: of

text: our

text: knowledge,

text: the

text: ﬁrst

text: graph

text: query

text: language

text: was

text: pro-

text: posed

text: in

text: by

text: Cruz,

text: Mendelzon

text: and

text: Wood

text: (i.e.

text: the

text: language

text: G).

text: After

text: that,

text: several

text: theoretical

text: GQLs

text: have

text: been

text: proposed,

text: in

text: some

text: cases

text: accom-

text: panying

text: the

text: deﬁnition

text: of

text: a

text: graph

text: data

text: model.

text: It

text: has

text: been

text: just

text: in

text: the

text: last

text: ten

text: years

text: that

text: practical

text: GQLs

text: are

text: available

text: thanks

text: to

text: the

text: release

text: of

text: graph

text: database

text: systems.

text: Example

text: of

text: this

text: is

text: Cypher,

text: the

text: query

text: language

text: provided

text: by

text: the

text: graph

text: database.

text: Although

text: a

text: GQL

text: is

text: normally

text: related

text: to

text: a

text: graph

text: database

text: model,

text: this

text: relation

text: is

text: no

text: exclusive.

text: For

text: instance,

text: several

text: object-oriented

text: data

text: models

text: deﬁned

text: graph-based

text: languages

text: to

text: manipulate

text: the

text: objects

text: in

text: the

text: database

text: (e.g.

text: GraphDB

text: and

text: or

text: to

text: represent

text: database

text: transfor-

text: mations

text: (e.g.

text: GOOD

text: and

text: GUL

text: A

text: similar

text: situation

text: occurred

text: for

text: semistructured

text: data

text: models

text: when

text: graph-oriented

text: operations

text: are

text: used

text: to

text: navigate

text: the

text: tree-based

text: data

text: (e.g.

text: Lorel

text: and

text: UnQL

text: Additionally,

text: several

text: graph-based

text: query

text: languages

text: have

text: been

text: designed

text: for

text: speciﬁc

text: applica-

text: tions

text: domains,

text: in

text: particular

text: those

text: related

text: to

text: complex

text: networks,

text: for

text: instance

text: social

text: networks

text: (e.g.

text: SoQL

text: biological

text: networks

text: (e.g.

text: DNAQL

text: bibliographical

text: networks

text: (e.g.

text: BiQL

text: the

text: Web

text: (e.g.

text: WebSQL

text: and

text: the

text: Semantic

text: Web

text: (e.g.

text: SPARQL

text: For

text: the

text: sake

text: of

text: space

text: we

text: will

text: not

text: present

text: a

text: complete

text: review

text: of

text: graph

text: query

text: languages.

text: Instead

text: we

text: describe

text: some

text: of

text: the

text: languages

text: we

text: consider

text: relevant

text: and

text: useful

text: to

text: show

text: the

text: developments

text: in

text: the

text: area.

text: Moreover,

text: we

text: restrict

text: our

text: review

text: to

text: “pure”

text: GQLs,

text: that

text: is

text: those

text: languages

text: speciﬁcally

text: designed

text: to

text: work

text: with

text: graph

text: data

text: models.

text: Figure

text: presents

text: this

text: subset

text: of

text: languages

text: in

text: chronological

text: order.

text: As

text: we

text: mentioned

text: before,

text: Cruz

text: et

text: al.

text: proposed

text: the

text: query

text: language

text: G.

text: This

text: language

text: introduced

text: the

text: notion

text: of

text: graphical

text: query

text: as

text: a

text: set

text: of

text: query

text: graphs.

text: A

text: query

text: graph

text: (pattern)

text: is

text: a

text: labeled

text: directed

text: multigraph

text: in

text: which

text: the

text: node

text: labels

text: may

text: be

text: either

text: variables

text: or

text: constants,

text: and

text: the

text: edge

text: labels

text: can

text: be

text: regular

text: expressions

text: combining

text: variables

text: and

text: constants.

text: The

text: result


text: this sense, these provide eﬃcient single-node solutions with limited scalabil- ity. On the other hand, graph processing frameworks aim to provide batch processing and analysis of large graphs often in a distributed environment with multiple machines. These solutions usually process the graph in mem- ory, but diﬀerent parts of the graph are managed by distinct, distributed nodes. Closely related to graph databases are the systems for managing RDF data. These systems, called RDF Triple Stores or RDF databases, are specif- ically designed to store collections of RDF triples, to support the standard SPARQL query language, and possibly to allow some kind of inference via semantic rules. Although Triple Stores are based on the RDF graph data model, they are specialized databases with their own characteristics. There- fore, we will study them separately. Next we present a review of current systems in the above categories, including a short description of each of them. 5.1 Graph database systems A graph database system (GDBS) – or just graph database – is a sys- tem speciﬁcally designed for managing graph-like data following the basic principles of database systems, i.e. persistent data storage, physical/logical data independence, data integrity and consistency. The research on graph databases have a long history, at least since the 1980’s. Although the ﬁrst of these were primarily theoretical proposals (with emphasis on graph database models), it is only recently that several technological developments (e.g. powerful hardware to store and process graphs) have made it possible to have practical systems. The current “market” of graph databases includes more than 15 systems with diﬀerent levels of development. All these systems provide most of the major components in database management systems, including: storage en- gine (with innate support for graph structures), database languages (for data deﬁnition, manipulation and querying), indexes and query optimizer, trans- actions and concurrency controllers, and external interfaces (user interface or API) for system management. Considering their internal implementation, we classify graph databases in two types: native and non-native graph databases. Native graph databases implement ad-hoc data structures and indexes for storing and querying graphs. Non-native graph databases make use of other database systems to store graph data and implement query interfaces to execute graph queries over the back-end system. In the group of native graph databases we found: AllegroGraph [3], Bitsy 25

text: this

text: sense,

text: these

text: provide

text: eﬃcient

text: single-node

text: solutions

text: with

text: limited

text: scalabil-

text: ity.

text: On

text: the

text: other

text: hand,

text: graph

text: processing

text: frameworks

text: aim

text: to

text: provide

text: batch

text: processing

text: and

text: analysis

text: of

text: large

text: graphs

text: often

text: in

text: a

text: distributed

text: environment

text: with

text: multiple

text: machines.

text: These

text: solutions

text: usually

text: process

text: the

text: graph

text: in

text: mem-

text: ory,

text: but

text: diﬀerent

text: parts

text: of

text: the

text: graph

text: are

text: managed

text: by

text: distinct,

text: distributed

text: nodes.

text: Closely

text: related

text: to

text: graph

text: databases

text: are

text: the

text: systems

text: for

text: managing

text: RDF

text: data.

text: These

text: systems,

text: called

text: RDF

text: Triple

text: Stores

text: or

text: RDF

text: databases,

text: are

text: specif-

text: ically

text: designed

text: to

text: store

text: collections

text: of

text: RDF

text: triples,

text: to

text: support

text: the

text: standard

text: SPARQL

text: query

text: language,

text: and

text: possibly

text: to

text: allow

text: some

text: kind

text: of

text: inference

text: via

text: semantic

text: rules.

text: Although

text: Triple

text: Stores

text: are

text: based

text: on

text: the

text: RDF

text: graph

text: data

text: model,

text: they

text: are

text: specialized

text: databases

text: with

text: their

text: own

text: characteristics.

text: There-

text: fore,

text: we

text: will

text: study

text: them

text: separately.

text: Next

text: we

text: present

text: a

text: review

text: of

text: current

text: systems

text: in

text: the

text: above

text: categories,

text: including

text: a

text: short

text: description

text: of

text: each

text: of

text: them.

text: Graph

text: database

text: systems

text: A

text: graph

text: database

text: system

text: (GDBS)

text: or

text: just

text: graph

text: database

text: is

text: a

text: sys-

text: tem

text: speciﬁcally

text: designed

text: for

text: managing

text: graph-like

text: data

text: following

text: the

text: basic

text: principles

text: of

text: database

text: systems,

text: i.e.

text: persistent

text: data

text: storage,

text: physical/logical

text: data

text: independence,

text: data

text: integrity

text: and

text: consistency.

text: The

text: research

text: on

text: graph

text: databases

text: have

text: a

text: long

text: history,

text: at

text: least

text: since

text: the

text: Although

text: the

text: ﬁrst

text: of

text: these

text: were

text: primarily

text: theoretical

text: proposals

text: (with

text: emphasis

text: on

text: graph

text: database

text: models),

text: it

text: is

text: only

text: recently

text: that

text: several

text: technological

text: developments

text: (e.g.

text: powerful

text: hardware

text: to

text: store

text: and

text: process

text: graphs)

text: have

text: made

text: it

text: possible

text: to

text: have

text: practical

text: systems.

text: The

text: current

text: “market”

text: of

text: graph

text: databases

text: includes

text: more

text: than

text: systems

text: with

text: diﬀerent

text: levels

text: of

text: development.

text: All

text: these

text: systems

text: provide

text: most

text: of

text: the

text: major

text: components

text: in

text: database

text: management

text: systems,

text: including:

text: storage

text: en-

text: gine

text: (with

text: innate

text: support

text: for

text: graph

text: structures),

text: database

text: languages

text: (for

text: data

text: deﬁnition,

text: manipulation

text: and

text: querying),

text: indexes

text: and

text: query

text: optimizer,

text: trans-

text: actions

text: and

text: concurrency

text: controllers,

text: and

text: external

text: interfaces

text: (user

text: interface

text: or

text: API)

text: for

text: system

text: management.

text: Considering

text: their

text: internal

text: implementation,

text: we

text: classify

text: graph

text: databases

text: in

text: two

text: types:

text: native

text: and

text: non-native

text: graph

text: databases.

text: Native

text: graph

text: databases

text: implement

text: ad-hoc

text: data

text: structures

text: and

text: indexes

text: for

text: storing

text: and

text: querying

text: graphs.

text: Non-native

text: graph

text: databases

text: make

text: use

text: of

text: other

text: database

text: systems

text: to

text: store

text: graph

text: data

text: and

text: implement

text: query

text: interfaces

text: to

text: execute

text: graph

text: queries

text: over

text: the

text: back-end

text: system.

text: In

text: the

text: group

text: of

text: native

text: graph

text: databases

text: we

text: found:

text: AllegroGraph

text: Bitsy


text: tributed memory cloud. Trinity implements a globally addressable dis- tributed memory storage, and provides a random access abstraction for large graph computation. Hence, it supports both online graph query processing and oﬄine graph analytics. Its query languages, called TSL, allows users to declare data schema and communication protocols. 5.2 Graph processing frameworks In addition to graph databases, a number of graph processing frameworks have been proposed to address the needs of processing complex and large- scale graph datasets. These frameworks are characterized by in-memory batch processing and the use of distributed and parallel processing strategies. Note that, distributed systems with more computing and memory resources are able to process large-scale graphs, but they can be less eﬃcient than single-node platforms when speciﬁc graph queries are executed. On the one hand, generic data processing systems such as Hadoop [5], YARN [6], Stratosphere [28] and Pegasus [91] have been adapted for graph processing due to their facilities for batch data processing. Most of these systems are based on the MapReduce programming model and implemented on top of the Hadoop platform, the open source version of MapReduce. By exploiting data-parallelism, these systems are highly scalable and support a range of fault-tolerance strategies. Though these systems improve the performance of iterative queries, users still need to “think” their analytical graph queries as MapReduce jobs. In fact, naively expressing graph com- putation and graph algorithms in these data-parallel abstractions can be challenging [145]. Additionally, these systems cannot take advantage of the characteristics of graph-structure data and often result in complex job chains and excessive data movement when implementing iterative graph algorithms [149]. On the other hand, graph-speciﬁc platforms such as Pregel [111], Apache Giraph [4], GraphLab [109, 108], Apache Hama, Catch de Wind [134], GPS [131], Mizan [93], PowerGraph [76], GraphX [18], TurboGraph [82] and GraphChi [100] provide diﬀerent programming interfaces for expressing graph analytic algorithms. These platforms, also called oﬄine graph ana- lytic systems, perform an iterative, batch processing over the entire graph dataset until the computation satisﬁes a ﬁxed-point or stopping criterion. Therefore, these systems are particularly designed for computing graph al- gorithms which require iterative, batch processing, e.g., PageRank, recursive relational queries, clustering, social network analysis, machine learning and data mining algorithms [92]. Next we brieﬂy describe some of these systems. Pregel [111] is a system that provides a native API speciﬁcally designed 27

text: tributed

text: memory

text: cloud.

text: Trinity

text: implements

text: a

text: globally

text: addressable

text: dis-

text: tributed

text: memory

text: storage,

text: and

text: provides

text: a

text: random

text: access

text: abstraction

text: for

text: large

text: graph

text: computation.

text: Hence,

text: it

text: supports

text: both

text: online

text: graph

text: query

text: processing

text: and

text: oﬄine

text: graph

text: analytics.

text: Its

text: query

text: languages,

text: called

text: TSL,

text: allows

text: users

text: to

text: declare

text: data

text: schema

text: and

text: communication

text: protocols.

text: Graph

text: processing

text: frameworks

text: In

text: addition

text: to

text: graph

text: databases,

text: a

text: number

text: of

text: graph

text: processing

text: frameworks

text: have

text: been

text: proposed

text: to

text: address

text: the

text: needs

text: of

text: processing

text: complex

text: and

text: large-

text: scale

text: graph

text: datasets.

text: These

text: frameworks

text: are

text: characterized

text: by

text: in-memory

text: batch

text: processing

text: and

text: the

text: use

text: of

text: distributed

text: and

text: parallel

text: processing

text: strategies.

text: Note

text: that,

text: distributed

text: systems

text: with

text: more

text: computing

text: and

text: memory

text: resources

text: are

text: able

text: to

text: process

text: large-scale

text: graphs,

text: but

text: they

text: can

text: be

text: less

text: eﬃcient

text: than

text: single-node

text: platforms

text: when

text: speciﬁc

text: graph

text: queries

text: are

text: executed.

text: On

text: the

text: one

text: hand,

text: generic

text: data

text: processing

text: systems

text: such

text: as

text: Hadoop

text: YARN

text: Stratosphere

text: and

text: Pegasus

text: have

text: been

text: adapted

text: for

text: graph

text: processing

text: due

text: to

text: their

text: facilities

text: for

text: batch

text: data

text: processing.

text: Most

text: of

text: these

text: systems

text: are

text: based

text: on

text: the

text: MapReduce

text: programming

text: model

text: and

text: implemented

text: on

text: top

text: of

text: the

text: Hadoop

text: platform,

text: the

text: open

text: source

text: version

text: of

text: MapReduce.

text: By

text: exploiting

text: data-parallelism,

text: these

text: systems

text: are

text: highly

text: scalable

text: and

text: support

text: a

text: range

text: of

text: fault-tolerance

text: strategies.

text: Though

text: these

text: systems

text: improve

text: the

text: performance

text: of

text: iterative

text: queries,

text: users

text: still

text: need

text: to

text: “think”

text: their

text: analytical

text: graph

text: queries

text: as

text: MapReduce

text: jobs.

text: In

text: fact,

text: naively

text: expressing

text: graph

text: com-

text: putation

text: and

text: graph

text: algorithms

text: in

text: these

text: data-parallel

text: abstractions

text: can

text: be

text: challenging

text: Additionally,

text: these

text: systems

text: cannot

text: take

text: advantage

text: of

text: the

text: characteristics

text: of

text: graph-structure

text: data

text: and

text: often

text: result

text: in

text: complex

text: job

text: chains

text: and

text: excessive

text: data

text: movement

text: when

text: implementing

text: iterative

text: graph

text: algorithms

text: On

text: the

text: other

text: hand,

text: graph-speciﬁc

text: platforms

text: such

text: as

text: Pregel

text: Apache

text: Giraph

text: GraphLab

text: Apache

text: Hama,

text: Catch

text: de

text: Wind

text: GPS

text: Mizan

text: PowerGraph

text: GraphX

text: TurboGraph

text: and

text: GraphChi

text: provide

text: diﬀerent

text: programming

text: interfaces

text: for

text: expressing

text: graph

text: analytic

text: algorithms.

text: These

text: platforms,

text: also

text: called

text: oﬄine

text: graph

text: ana-

text: lytic

text: systems,

text: perform

text: an

text: iterative,

text: batch

text: processing

text: over

text: the

text: entire

text: graph

text: dataset

text: until

text: the

text: computation

text: satisﬁes

text: a

text: ﬁxed-point

text: or

text: stopping

text: criterion.

text: Therefore,

text: these

text: systems

text: are

text: particularly

text: designed

text: for

text: computing

text: graph

text: al-

text: gorithms

text: which

text: require

text: iterative,

text: batch

text: processing,

text: e.g.,

text: PageRank,

text: recursive

text: relational

text: queries,

text: clustering,

text: social

text: network

text: analysis,

text: machine

text: learning

text: and

text: data

text: mining

text: algorithms

text: Next

text: we

text: brieﬂy

text: describe

text: some

text: of

text: these

text: systems.

text: Pregel

text: is

text: a

text: system

text: that

text: provides

text: a

text: native

text: API

text: speciﬁcally

text: designed