COMPSCI 752 Big data management Assignment 2 / Semester 1, 2023

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMPSCI 752

Big data management

Assignment 2 / Semester 1, 2023

Graph Databases

Model Answers

Graph databases

Consider a simple application where direct flights between two cities are stored as a property graph. Nodes and edges may have properties.

Fig. 1. Property Graph

Questions:

1. Write down the formal property graph model  (V, E, n, λ, v) for the property graph in Figure 1.         [6 marks]

Solution:

– V = {1, 2, 3}

– E = {10, 11}

– n:

●  10 →l (1, 2), 11 →l (2, 3)

– λ:

● 1 → {city}, 2 → {city}, 3 → {city},

● 10 → {flight}, 11 → {flight}

– v:

● (1, name) → “Papeete”, (1, country) →  “France”

● (2, name) → “Los Angeles”, (2, country) →  “USA”,

● (3, name) → “Paris”, (3, country) →  “France”,

● (10, airline) → “Air Tahiti”, (10, no) → “TN 8”,

● (11, airline) → “Air Tahiti”, (11, no) → “TN 8”,

2. Write the following English language query in regular property graph logic

Return all city nodes that can be reached from the city of Papeete with a sequence of connecting flights with at most two stop-overs.                                                   [4 marks]

Solution:

result(g) 仁 :flight(①, g), ①.name = “Papeete”

result(g) 仁 :flight(①, s1), :flight(s1, g), ①.name = “Papeete”

result(g) 仁 :flight(①, s1), :flight(s1, s2), :flight(s2, g), ①.name = “Papeete”

3. Write the following English language query in regular property graph logic

Return all city nodes that can be reached from the city of Papeete with a sequence of connecting flights that have an unlimited number of stop-overs.                        [4 marks]

Solution:

result(从) 仁 :flight(①, g), :flight* (g, 从), ①.name = “Papeete”

4. Write the following English language query in regular property graph logic

Return all city nodes in France, with a name different from Papeete, that can be reached from the city of Papeete with a sequence of connecting flights that have an unlimited number of stop-overs, where each flight is international and operated by the airline “Air Tahiti” .                                                                                                                   [4 marks]

Solution:

reach(g, 从) 仁 :flight(g, 从) as k, k.airline = “Air Tahiti”, g.country 从.country

result(从) 仁 :reach(①, g), :reach* (g, 从), ①.name = “Papeete” ,

从.country = “France”, 从.name “Papeete”

5. Write down the queries from Questions 2., 3., and 4. in regular property graph algebra.

Solution:

(b)

B司t(Q)rg1  (B司sr(Φ)c(1)1 ,trg1  (:flight)n B司sr(Φ)1 ,trg2  (:flight, :flight)n B司sr(Φ)1 ,trg3  (:flight, :flight, :flight))

Φ 1  : src1.name = “Papeete”

Φ2  : Φ1  A trg1 = src2

Φ3  : Φ2  A trg2 = src3

(c)

B司s(Q)rc1 ╱B司tr(Φ)g2 ,trg2  (:flight, :flight* )、

Φ : src1.name = “Papeete” A trg1 = src2

(d)

B司s(Q)rc1 ╱B司tr(v)g2 ,trg2 ╱flight, ╱B司scr1(Φ) ,trg1  (:flight)、* ))

Φ : edge.airline = “Air Tahiti”A

src1.country trg1.country

ψ : src1.name = “Papeete” A trg1 = src2A

edge1.airline = “Air Tahiti” A src1.country trg1.countryA trg2.country = “France” A trg2.name “Papeete” [12 marks]


2023-06-24