* Wolde et al. (2023) Daniel ten Wolde, Gábor Szárnyas, and Peter Boncz. 2023.  DuckPGQ: Bringing SQL/PGQ to DuckDB.  _Proc. VLDB Endow._ 16, 12 (aug 2023), 4034–4037.
  * Wu et al. (2017) Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017.  An Empirical Evaluation of In-Memory Multi-Version Concurrency Control.  _Proc. VLDB Endow._ 10, 7 (2017), 781–792.
  * Yakout et al. (2012) Mohamed Yakout, Kris Ganjam, Kaushik Chakrabarti, and Surajit Chaudhuri. 2012.  InfoGather: Entity Augmentation and Attribute Discovery by Holistic Matching with Web Tables. In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ _(SIGMOD ’12)_. Association for Computing Machinery, New York, NY, USA, 97–108.
  * Yang et al. (2021) Zhengyi Yang, Longbin Lai, Xuemin Lin, Kongzhang Hao, and Wenjie Zhang. 2021.  HUGE: An Efficient and Scalable Subgraph Enumeration System. In _SIGMOD_. 2049–2062.
  * Zhang et al. (2015) Hao Zhang, Gang Chen, Beng Chin Ooi, Kian-Lee Tan, and Meihui Zhang. 2015.  In-Memory Big Data Management and Processing: A Survey.  _IEEE Trans. Knowl. Data Eng._ 27, 7 (2015), 1920–1948.
  * Zhang et al. (2022) Hao Zhang, Jeffrey Xu Yu, Yikai Zhang, and Kangfei Zhao. 2022\.  Parallel Query Processing: To Separate Communication from Computation. In _SIGMOD_. ACM, 1447–1461.
  * Zhao and Yu (2017) Kangfei Zhao and Jeffrey Xu Yu. 2017.  All-in-One: Graph Processing in RDBMSs Revisited. In _SIGMOD_. 1165–1180.
  * Zhou and Ross (2002) Jingren Zhou and Kenneth A. Ross. 2002.  Implementing Database Operations Using SIMD Instructions. In _Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data_ _(SIGMOD ’02)_. Association for Computing Machinery, New York, NY, USA, 145–156.
  * Zhou et al. (2022) Xuanhe Zhou, Chengliang Chai, Guoliang Li, and Ji Sun. 2022\.  Database Meets Artificial Intelligence: A Survey.  _IEEE Transactions on Knowledge and Data Engineering_ 34, 3 (2022), 1096–1116.
  * Zhu and Risch (2011) Minpeng Zhu and Tore Risch. 2011.  Querying combined cloud-based and relational databases. In _CSC_. 330–335.

## Appendix

###  A. Extended Query Graph Definition

We provide a formal definition of the extended query graph here, based on its
counterpart in (Moerkotte and Neumann, 2008).

Extended query graph. Given a $\mathsf{RG}$ schema
${\mathcal{R}}^{E}=(R_{1}^{E},\ldots,R_{m}^{E})$. The extended query graph is
defined as $Q=(N,E,L,F)$, where: (1) $N\neq\emptyset$ denotes the set of nodes
in it; (2) $E\subseteq\mathcal{P}(N)\times\mathcal{P}(N)$ denotes the set of
hyperedges, ($\mathcal{P}$ for power set), where $\forall e=\langle
n_{s},n_{d}\rangle\in E$, there are $n_{s},n_{d}\subseteq N$ and $n_{s}\cap
n_{d}=\emptyset$; (3)
$L:E\rightarrow\\{{\mathsf{explore}},{\mathsf{value}},{\mathsf{duplciate}}\\}\times\\{A_{ij}\\}$
that associates each edge with a label to denote its type and attribute (after
rename) of the vertices it connects; (4) $F:E\rightarrow N\times N$ that maps
each exploration edge to a pair of vertices $\langle n_{s},n_{d}\rangle$ that
denotes the source and destination vertex respectively where $n_{s}\neq
n_{d}$.

Intuitively, along with the set of node and hyperedge in (Moerkotte and
Neumann, 2008), each hyperedge here is associated with a label with $L$ in
addition. $L$ marks the type of the edge, _i.e.,_ to be an exploration, plain
value condition, or a duplicated (“same-pointer”) condition; and an attribute
for the join condition. Meanwhile, although the exploration edge is
conceptually defined as directed edge, such a “direction” is actually
equivalently represented by a function $F$. Therefore, the query graph for the
conventional relational query is only extended with two functions here and
thus retains the definition of CSG and CSG-CMP pair in (Moerkotte and Neumann,
2008).

As the all plan enumeration methods considering only the topology of the
hypergraph, they can then be directly adopted here to enumerate hybrid query
plan from the extended query graph. Meanwhile, as a simplification of the
description, we also utilized a specified notation for the exploration edge
below:

Directed edge notation. Given a $\mathsf{RG}$ schema
${\mathcal{R}}^{E}=(R_{1}^{E},\ldots,R_{m}^{E})$ and an extended query graph
$Q=(N,E,L,F)$. For an attribute $A_{p}$ in ${\mathcal{R}}^{E}$, node
$n_{s},n_{d}\in N$ and $n_{s}\neq n_{d}$, we say there is an edge
$(n_{s},A_{p},n_{d})$ in $Q$, it means there exists
$e=\\{n_{s}\\}\times\\{n_{d}\\}\in E$, such that: (1)
$L(e)=\langle{\mathsf{explore}},A_{p}\rangle$; (2) $F(e)=\langle
n_{s},n_{d}\rangle$.

Informally, for a node $n$ in the query graph, we use $N(n)$ and $N_{E}(n)$ to
denote its neighbouring nodes and edges respectively; for an edge $e$, we use
$N(e)$ to denote its neighbouring vertices. As a simplification, we consider a
query graph-based representation of intermediate result based on the notation
of subgraph in (Moerkotte and Neumann, 2008).

Intermediate result. Given a query graph $Q=(N,E,L,F)$ and a subset of
vertices $N^{\prime}\subseteq N$. We use $R_{N^{\prime}}$ to denote the
intermediate join result corresponds to the sub-query graph $Q|_{N^{\prime}}$.

###  B. Logical Plan Parsing

We provide a detailed demonstration of the parsing process in Figure 12 from
${\mathsf{SQL_{\delta}}}$ query ${\mathsf{Q_{\delta}}}$ to a logical plan
$\text{Plan}_{\text{P}}$, which was omitted in Section 5:

  1. (1)

Parse the edge: $(v2)-[e2]\to(v0)$ into two subsequent exploration operators:
$D_{V}^{2}{\vec{\bowtie}^{out_{L}}}D_{o}^{2}$ and
$R_{CSG_{C0}}{\vec{\bowtie}^{D_{o}^{2}.dst_{L}}}D_{V}^{0}$, where
$CSG_{C0}=\\{D_{V}^{2},D_{o}^{2}\\}$.

  2. (2)

Parse the edge: $(v2)-[e1]\to(v1)$ into two subsequent exploration operators:
$R_{CSG_{C1}}{\vec{\bowtie}^{D_{V}^{2}.out_{L}}}D_{o}^{1}$ and
$R_{CSG_{C2}}{\vec{\bowtie}^{D_{o}^{1}.dst_{L}}}D_{V}^{1}$
where $CSG_{C1}=\\{D_{V}^{2},D_{o}^{2},D_{V}^{0}\\}$ and
$CSG_{C2}=\\{D_{V}^{2},D_{o}^{2},D_{V}^{0},D_{o}^{1}\\}$.

Figure 12. A step-by-step demonstration of the parsing process from input
${\mathsf{SQL_{\delta}}}$ query to a logical query plan

Figure 13. A step-by-step demonstration of the query graph construction
process from an input logical query plan

  3. (3)

As both vertex $v0$ and $v1$ have already been considered in the query plan,
the edge: $(v0)-[e0]\to(v1)$ will be parsed as an exploration condition:
$\psi(D_{V}^{0}.out_{L})[dst_{L}]\ni dst_{L}$ and be incorporated into the
operator:
$R_{CSG_{C1}}{\vec{\bowtie}^{D_{V}^{2}.out_{L}}}_{\psi(D_{V}^{0}.out_{L})[dst_{L}]\ni
dst_{L}}D_{o}^{1}$.

  4. (4)

Parse the join on the relation $D$ as
$R_{CSG_{C3}}\bowtie_{D_{V}^{0}.vid=uid}D$ on the top of the query plan
generated so far, were
$CSG_{C3}=\\{D_{V}^{2},D_{o}^{2},D_{V}^{0},D_{o}^{1},D_{V}^{1}\\}$.

###  C. Query Graph Construction

We provide a detailed, step-by-step demonstration in Figure 13 of the query
graph construction process from $\text{Plan}_{\text{P}}$:

  1. (0)

Each leaf node in the query plan will be constructed as a node in the query
graph: $D$, $D_{V}^{1}$, $D_{o}^{1}$, $D_{V}^{0}$ $D_{o}^{2}$ and $D_{V}^{2}$.

  2. (1)

An edge $(D_{V}^{2},out_{L},D_{o}^{2})$ will be constructed corresponding to
the exploration operator: $D_{V}^{2}{\vec{\bowtie}^{out_{L}}}D_{o}^{2}$.
Following that, an edge $(D_{o}^{2},dst_{L},D_{V}^{0})$ will be constructed
corresponding to the exploration operator:
$R_{CSG_{C0}}{\vec{\bowtie}^{D_{o}^{2}.dst_{L}}}D_{V}^{0}$.

  3. (2)

An edge $(D_{V}^{2},out_{L},D_{o}^{1})$ will be constructed corresponding to
the exploration operator:
$R_{CSG_{C1}}{\vec{\bowtie}^{D_{V}^{2}.out_{L}}}D_{o}^{1}$. Following that, an
edge $(D_{o}^{1},dst_{L},D_{V}^{1})$ will be constructed corresponding to the
exploration operator:
$R_{CSG_{C2}}{\vec{\bowtie}^{D_{o}^{1}.dst_{L}}}D_{V}^{1}$.

  4. (3)

$D_{V}^{0}$ and $D$ will be connected with an edge that denotes the join:
$D_{V}^{0}\bowtie_{vid=uid}D$.

  5. (4)

Corresponding to the condition: $\psi(D_{V}^{0}.out_{L})[dst_{L}]\ni dst_{L}$,
a node $D_{o}^{0}$ will be first inserted into the query graph and an edge
$(D_{V}^{0},out_{L},D_{o}^{0})$ will be constructed. As $\mathcal{D}_{G}^{E}$
is in the regular form, it can be looked up that $D_{o}^{0}$ is an alias of
$D_{o}$ as it is explored from the field $D_{V}^{0}[out_{L}]$. $D_{o}^{0}$ and
$D_{o}^{1}$ will be further connected by an edge denoting the “same-pointer
condition”: $D_{o}^{0}\bowtie_{dst_{L}=dst_{L}}D_{o}^{1}$.

  6. (5)

According to the “same-pointer condition”
$D_{o}^{0}\bowtie_{dst_{L}=dst_{L}}D_{o}^{1}$, we know that
$D_{o}^{0}[dst_{L}]$ and $D_{o}^{1}[dst_{L}]$ point to the same tuple.
Considering that there already exists an edge $(D_{o}^{1},dst_{L},D_{V}^{1})$,
an edge $(D_{o}^{0},dst_{L},D_{V}^{1})$ will be constructed in the query
graph.

  7. (6)

All paths in the query graph that have the patterns:

$\displaystyle(D_{V})-[out_{L}]\to(D_{o})-[dst_{L}]\to(D_{V})$
$\displaystyle(D_{V})-[in_{L}]\to(D_{i})-[src_{L}]\to(D_{V})$

will be recognized and duplicated oppositely. The rest “same pointer”
conditions will then be completed, _i.e.,_
$D_{o}^{2}[dst_{L}]=D_{i}^{0}[src_{L}]$ and
$D_{i}^{2}[src_{L}]=D_{i}^{1}[src_{L}]$.

###  D. Plan Enumeration

The “exploration” is represented as directed edge with an additional function
$F$ in the extended query graph, for it to be still treated as an ordinary
hyperedge in the plan enumeration process. Meanwhile, the “same pointer
condition” will not be considered in the plan enumeration for exploring
neighbouring nodes. That is, the edges with type “$\mathsf{duplicate}$” will
be omitted when computing $N(v)$ and $N_{E}(v)$. They will only be used to
resolve explorative condition.

However, as also mentioned in Section 5.3, there are several additional
restrictions on the enumerated CSG-CMP pair for them to be resolves as
exploration operator, like “duplicated nodes will not appear simultaneously”.
In this case, the CSG-CMP pairs exported by previous plan enumeration methods
we directly apply here can be illegal and break these restrictions. Here, we
simply add a filter to verify the CSG-CMP pairs to get the legal ones without
touching the details of the plan enumeration methods.

Input: Query graph $Q=(N,E,L,F)$, $CSG_{0},CSG_{1}\subseteq N$, and $D$.

Output: Boolean value $legal$.

// first check whether there are duplicated nodes

1for $n_{0}\in CSG_{0}$ do

2 for $n_{1}\in CSG_{1}$ do

3 if $\langle n_{0},n_{1}\rangle\in D$ or $\langle n_{1},n_{0}\rangle\in D$
then

4 return false

// then check whether these two CSGs are connected by exploration edge

5$e_{e}=null$ // to hold the exploration edge if it exists

6for $v\in CSG_{0}\cup CSG_{1}$ do

7 for $e\in N_{E}(v)$ do

8$\langle l,A\rangle=L(e)$ // to find exploration edge connects them

9if $l\neq explore$ then

10 continue

11$\langle n_{s},n_{d}\rangle=F(e)$

12if $n_{s}\in CSG_{0}$ and $n_{d}\notin CSG_{1}$ then

13 continue // inside $CSG_{0}$ or toward an outside vertex

14if $n_{s}\in CSG_{1}$ and $n_{d}\notin CSG_{0}$ then

15 continue // inside $CSG_{1}$ or toward an outside vertex

16if $e_{e}\neq null$ then

17 return false // more than one exploration edge

18$e_{e}=e$

19if $e_{e}=null$ then

// the CSG-CMP pair is not connected by exploration edge

20return true

21$\langle n_{s},n_{d}\rangle=F(e_{e})$

22if $n_{d}\in\\{CSG_{0}\\}$ and $|\\{CSG_{0}\\}|>1$ then

23 return false // toward the tuples in intermediate result

24if $n_{d}\in\\{CSG_{1}\\}$ and $|\\{CSG_{1}\\}|>1$ then

25 return false // toward the tuples in intermediate result

26return true

Algorithm 1 Legal CSG-CMP pair

Algorithm 1 shows such a filter. For an extended query graph $Q=(N,E,L,F)$, it
accepts a CSG-CMP pair and a set denotes the duplicated nodes in $Q$:
$D\subseteq N\times N$. As an example, for the query graph in Figure 6,
$D=\bigcup_{k=0,1,2}\\{\langle D_{o}^{k},D_{i}^{k}\rangle\\}$. It can then
return a boolean value to select all legal CSG-CMP pairs for operator
resolution.

The example below shows that enumerating query plan in such an enlarged
unified space allows the access on graph and relational data to be considered
in any order.

###### Example 1.

We next provide a detailed step-by-step explanation to show how the query
plans $\text{Plan}_{\text{RF}}$, $\text{Plan}_{\text{GF}}$ and
$\text{Plan}_{\text{H}}$ in Figure 6 can be enumerated.

$\text{Plan}_{\text{RF}}$:

  1. (1)

$CSG_{R0}\text{=}\\{D_{V}^{0}\\}\times CSG_{R1}\text{=}\\{D\\}$.

Resolve to operator: $D_{V}^{0}\bowtie_{vid=uid}D$.

As a plain value join operator.

  2. (2)

$CSG_{R2}\text{=}CSG_{R0}\cup CSG_{R1}\text{=}\\{D_{V}^{0},D\\}\times
CSG_{R3}\text{=}\\{D_{o}^{0}\\}$.

Resolve to operator:
$R_{CSG_{R2}}{\vec{\bowtie}^{D_{V}^{0}.out_{L}}}D_{o}^{0}$.

As there is an edge: $(D_{V}^{0},out_{L},D_{o}^{0})$ from $CSG_{R2}$ toward
$CSG_{R3}$.

  3. (3)

$CSG_{R4}\text{=}CSG_{R2}\cup
CSG_{R3}\text{=}\\{D_{V}^{0},D,D_{o}^{0}\\}\times
CSG_{R5}\text{=}\\{D_{V}^{1}\\}$.

Resolve to operator:
$R_{CSG_{R4}}{\vec{\bowtie}^{D_{o}^{0}.dst_{L}}}D_{V}^{1}$.

As there is an edge: $(D_{o}^{0},dst_{L},D_{V}^{1})$ from $CSG_{R4}$ toward
$CSG_{R5}$.

  4. (4)

$CSG_{R6}\text{=}CSG_{R4}\cup
CSG_{R5}\text{=}\\{D_{V}^{0},D,D_{o}^{0},D_{V}^{1}\\}\times
CSG_{R7}\text{=}\\{D_{i}^{1}\\}$.

Resolve to operator:
$R_{CSG_{R6}}{\vec{\bowtie}^{D_{V}^{1}.in_{L}}}_{\psi(D_{V}^{0}.in_{L})[src_{L}]\ni
src_{L}}D_{i}^{1}$.

As there is an edge: $(D_{V}^{1},in_{L},D_{i}^{1})$ from $CSG_{R6}$ toward
$CSG_{R7}$, and a condition $D_{i}^{2}[src_{L}]\text{=}D_{i}^{1}[src_{L}]$
exists and an edge $(D_{V}^{0},in_{L},D_{i}^{2})$ explores from $CSG_{R6}$ to
$D_{i}^{2}$, an explorative condition, $\psi(D_{V}^{0}.in_{L})[src_{L}]\ni
src_{L}$, can then be incorporated into such an exploration.

  5. (5)

$CSG_{R8}\text{=}CSG_{R6}\cup
CSG_{R7}\text{=}\\{D_{V}^{0},D,D_{o}^{0},D_{V}^{1},D_{i}^{1}\\}\times
CSG_{R9}\text{=}\\{D_{V}^{2}\\}$.

Resolve to operator:
$R_{CSG_{R8}}{\vec{\bowtie}^{D_{i}^{1}.src_{L}}}D_{V}^{2}$.

As there is an outward edge: $(D_{i}^{1},src_{L},D_{V}^{2})$ from $CSG_{R8}$
toward $CSG_{R9}$.

$\text{Plan}_{\text{H}}$:

  1. (1)

$CSG_{H0}\text{=}\\{D_{V}^{0}\\}\times CSG_{H1}\text{=}\\{D_{o}^{0}\\}$.

Resolve to operator: $D_{V}^{0}{\vec{\bowtie}^{out_{L}}}D_{o}^{0}$.

As there is an edge: $(D_{V}^{0},out_{L},D_{o}^{0})$ from $CSG_{H0}$ toward
$CSG_{H1}$.

  2. (2)

$CSG_{H2}\text{=}CSG_{H0}\cup CSG_{H1}\text{=}\\{D_{V}^{0},D_{o}^{0}\\}\times
CSG_{H3}\text{=}\\{D_{V}^{1}\\}$.

Resolve to operator:
$R_{CSG_{H2}}{\vec{\bowtie}^{D_{o}^{0}.dst_{L}}}D_{V}^{1}$.

As there is an edge: $(D_{o}^{0},dst_{L},D_{V}^{1})$ from $CSG_{H2}$ toward
$CSG_{H3}$.

  3. (3)

$CSG_{H4}\text{=}CSG_{H2}\cup
CSG_{H3}\text{=}\\{D_{V}^{0},D_{o}^{0},D_{V}^{1}\\}\times
CSG_{H5}\text{=}\\{D\\}$.

Resolve to operator: $R_{CSG_{H4}}\bowtie_{D_{V}^{0}.vid=uid}D$.

As a plain value join operator.

  4. (4)

$CSG_{H6}\text{=}CSG_{H4}\cup
CSG_{H5}\text{=}\\{D_{V}^{0},D_{o}^{0},D_{V}^{1},D\\}\times
CSG_{H7}\text{=}\\{D_{i}^{1}\\}$.

Resolve to operator:
$R_{CSG_{H6}}{\vec{\bowtie}^{D_{V}^{1}.in_{L}}}_{\psi(D_{V}^{0}.in_{L})[src_{L}]\ni
src_{L}}D_{i}^{1}$.

As there is an edge: $(D_{V}^{1},in_{L},D_{i}^{1})$ from $CSG_{H6}$ toward
$CSG_{H7}$, and a condition $D_{i}^{2}[src_{L}]\text{=}D_{i}^{1}[src_{L}]$
exists and an edge $(D_{V}^{0},in_{L},D_{i}^{2})$ explores from $CSG_{H6}$ to
$D_{i}^{2}$, an explorative condition, $\psi(D_{V}^{0}.in_{L})[src_{L}]\ni
src_{L}$, can then be incorporated into such an exploration.

  5. (5)

$CSG_{H8}\text{=}CSG_{H6}\cup
CSG_{H7}\text{=}\\{D_{V}^{0},D_{o}^{0},D_{V}^{1},D,D_{i}^{1}\\}\times
CSG_{H9}\text{=}\\{D_{V}^{2}\\}$

Resolve to operator:
$R_{CSG_{H8}}{\vec{\bowtie}^{D_{i}^{1}.src_{L}}}D_{V}^{2}$.

As there is an edge: $(D_{i}^{1},src_{L},D_{V}^{2})$ from $CSG_{H8}$ toward
$CSG_{H9}$.

$\text{Plan}_{\text{GF}}$:

  1. (1)

$CSG_{G0}\text{=}\\{D_{V}^{2}\\}\times CSG_{G1}\text{=}\\{D_{o}^{1}\\}$.

Resolve to operator: $D_{V}^{2}{\vec{\bowtie}^{out_{L}}}D_{o}^{1}$.

As there is an edge: $(D_{V}^{2},out_{L},D_{o}^{1})$ from $CSG_{G0}$ toward
$CSG_{G1}$.

  2. (2)

$CSG_{G2}\text{=}CSG_{G0}\cup CSG_{G1}\text{=}\\{D_{V}^{2},D_{o}^{1}\\}\times
CSG_{G3}\text{=}\\{D_{V}^{1}\\}$.

Resolve to operator:
$R_{CSG_{G2}}{\vec{\bowtie}^{D_{o}^{1}.dst_{L}}}D_{V}^{1}$.

As there is an edge: $(D_{o}^{1},dst_{L},D_{V}^{1})$ from $CSG_{G2}$ toward
$CSG_{G3}$.

  3. (3)

$CSG_{G4}\text{=}CSG_{G2}\cup
CSG_{G3}\text{=}\\{D_{V}^{2},D_{o}^{1},D_{V}^{1}\\}\times
CSG_{G5}\text{=}\\{D_{o}^{2}\\}$.

Resolve to operator:
$R_{CSG_{G4}}{\vec{\bowtie}^{D_{V}^{2}.out_{L}}}_{\psi(D_{V}^{1}.in_{L})[src_{L}]\ni
dst_{L}}D_{o}^{2}$.

As there is an edge: $(D_{V}^{2},out_{L},D_{o}^{2})$ from $CSG_{G4}$ toward
$CSG_{G5}$, and a condition $D_{i}^{0}[src_{L}]\text{=}D_{o}^{2}[dst_{L}]$
exists and an edge $(D_{V}^{1},in_{L},D_{i}^{0})$ explores from $CSG_{G4}$ to
$D_{i}^{0}$, an explorative condition, $\psi(D_{V}^{1}.in_{L})[src_{L}]\ni
dst_{L}$, can then be incorporated into such an exploration.

  4. (4)

$CSG_{G6}\text{=}CSG_{G4}\cup
CSG_{G5}\text{=}\\{D_{V}^{2},D_{o}^{1},D_{V}^{1},D_{o}^{2}\\}\times
CSG_{G7}\text{=}\\{D_{V}^{0}\\}$.

Resolve to operator:
$R_{CSG_{G6}}{\vec{\bowtie}^{D_{o}^{2}.dst_{L}}}D_{V}^{0}$.

As there is an edge: $(D_{o}^{2},dst_{L},D_{V}^{0})$ from $CSG_{G6}$ toward
$CSG_{G7}$.

  5. (5)

$CSG_{G8}\text{=}CSG_{G6}\cup
CSG_{G7}\text{=}\\{D_{V}^{2},D_{o}^{1},D_{V}^{1},D_{o}^{2},D_{V}^{0}\\}\times
CSG_{G9}\text{=}\\{D\\}$.

Resolve to operator: $R_{CSG_{G8}}\bowtie_{D_{V}^{0}.vid=uid}D$.

As a plain value join operator.

This example is only to highlight the plan enumeration process, it will be
shown below how the operators are resolved by accepting the corresponding CSG-
CMP pair as input.

###  E. Cost Estimation

The example below provides an explanation of the cost estimation.

###### Example 2.

For the query plan $\text{Plan}_{\text{RF}}$, $\text{Plan}_{\text{GF}}$ and
$\text{Plan}_{\text{H}}$ in Figure 6, we then provide a step-by-step
explanation of how their cost can be estimated with the cost model $C_{emm}$
in Section 5.3.

$\text{Plan}_{\text{RF}}$:

$\displaystyle C_{emm}(CSG_{R2})=$
$\displaystyle\tau|D_{V}^{0}|+\tau|D|+|R_{CSG_{R2}}|$ $\displaystyle
C_{emm}(CSG_{R4})=$ $\displaystyle
C_{emm}(CSG_{R2})+\tau|R_{CSG_{R2}}[D_{V}^{0}.out_{L}]|$ $\displaystyle
C_{emm}(CSG_{R6})=$ $\displaystyle
C_{emm}(CSG_{R4})+\tau|R_{CSG_{R4}}[D_{o}^{0}.dst_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{R4})+\tau|R_{CSG_{R4}}|$ $\displaystyle
C_{emm}(CSG_{R8})=$ $\displaystyle
C_{emm}(CSG_{R6})+\tau|R_{CSG_{R6}}[D_{V}^{1}.in_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{0}.in_{L}}R_{CSG_{R6}}[D_{V}^{0}.in_{L}]|}+|R_{CSG_{R8}}|$
$\displaystyle C_{emm}(\text{Plan}_{\text{RF}})=$ $\displaystyle
C_{emm}(CSG_{R8})+\tau|R_{CSG_{R8}}[D_{i}^{1}.src_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{R8})+\tau|R_{CSG_{R8}}|$ $\displaystyle=$
$\displaystyle(1+\tau)|R_{CSG_{R8}}|+\tau|R_{CSG_{R6}}[D_{V}^{1}.in_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{0}.in_{L}}R_{CSG_{R6}}[D_{V}^{0}.in_{L}]|}+\tau|R_{CSG_{R4}}|$
$\displaystyle+\tau|R_{CSG_{R2}}[D_{V}^{0}.out_{L}]|+|R_{CSG_{R2}}|+\tau|D_{V}^{0}|+\tau|D|$

$\text{Plan}_{\text{H}}$:

$\displaystyle C_{emm}(CSG_{H2})=$
$\displaystyle\tau|D_{V}^{0}|+\tau|D_{V}^{0}[out_{L}]|$ $\displaystyle
C_{emm}(CSG_{H4})=$ $\displaystyle
C_{emm}(CSG_{H2})+\tau|R_{CSG_{H2}}[D_{o}^{0}.dst_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{H2})+\tau|R_{CSG_{H2}}|$ $\displaystyle
C_{emm}(CSG_{H6})=$ $\displaystyle C_{emm}(CSG_{H4})+\tau|D|+|R_{CSG_{H6}}|$
$\displaystyle C_{emm}(CSG_{H8})=$ $\displaystyle
C_{emm}(CSG_{H6})+\tau|R_{CSG_{H6}}[D_{V}^{1}.in_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{0}.in_{L}}R_{CSG_{H6}}[D_{V}^{0}.in_{L}]|}+|R_{CSG_{H8}}|$
$\displaystyle C_{emm}(\text{Plan}_{\text{H}})=$ $\displaystyle
C_{emm}(CSG_{H8})+\tau|R_{CSG_{H8}}[D_{i}^{1}.src_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{H8})+\tau|R_{CSG_{H8}}|$ $\displaystyle=$
$\displaystyle(1+\tau)|R_{CSG_{H8}}|+\tau|R_{CSG_{H6}}[D_{V}^{1}.in_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{0}.in_{L}}R_{CSG_{H6}}[D_{V}^{0}.in_{L}]|}+|R_{CSG_{H6}}|$
$\displaystyle+\tau|R_{CSG_{H2}}|+\tau|D_{V}^{0}[out_{L}]|+\tau|D_{V}^{0}|+\tau|D|$

$\text{Plan}_{\text{GF}}$:

$\displaystyle C_{emm}(CSG_{G2})=$
$\displaystyle\tau|D_{V}^{2}|+\tau|D_{V}^{2}[out_{L}]|$ $\displaystyle
C_{emm}(CSG_{G4})=$ $\displaystyle
C_{emm}(CSG_{G2})+\tau|R_{CSG_{G2}}[D_{o}^{1}.dst_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{G2})+\tau|R_{CSG_{G2}}|$ $\displaystyle
C_{emm}(CSG_{G6})=$ $\displaystyle
C_{emm}(CSG_{G4})+\tau|R_{CSG_{G4}}[D_{V}^{2}.out_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{1}.in_{L}}R_{CSG_{G4}}[D_{V}^{1}.in_{L}]|}+|R_{CSG_{G6}}|$
$\displaystyle C_{emm}(CSG_{G8})=$ $\displaystyle
C_{emm}(CSG_{G6})+\tau|R_{CSG_{G6}}[D_{o}^{2}.dst_{L}]|$ $\displaystyle=$
$\displaystyle C_{emm}(CSG_{G6})+\tau|R_{CSG_{G6}}|$ $\displaystyle
C_{emm}(\text{Plan}_{\text{GF}})=$ $\displaystyle
C_{emm}(CSG_{G8})+\tau|D|+|R_{CSG_{G8}}|$ $\displaystyle=$
$\displaystyle|R_{CSG_{G8}}|+(1+\tau)|R_{CSG_{G6}}|+\tau|R_{CSG_{G4}}[D_{V}^{2}.out_{L}]|$
$\displaystyle+\tau{|\Pi_{D_{V}^{1}.in_{L}}R_{CSG_{G4}}[D_{V}^{1}.in_{L}]|}$
$\displaystyle+\tau|R_{CSG_{G2}}|+\tau|D|+\tau|D_{V}^{2}|+\tau|D_{V}^{2}[out_{L}]|$

As a simplification, for all relation $T$ and their field $A$, we assume
$|\Pi_{A}(T)|\approx|T|$. Meanwhile, for arbitrary relations $T$ and
$T^{\prime}$, and pointer field $p$ in $T^{\prime}$, we assume
$|T[T^{\prime}.p]|\approx|T|\frac{|T^{\prime}[p]|}{|T^{\prime}|}$, which also
implies the simple histogram method we utilized to estimate the “selectivity”
of exploration.

We then have:

$\displaystyle C_{emm}(\text{Plan}_{\text{RF}})\approx$
$\displaystyle(1+\tau)|R_{CSG_{R8}}|$
$\displaystyle+\tau|R_{CSG_{R6}}|(\frac{|D_{V}^{1}[in_{L}]|}{|D_{V}^{1}|}+\frac{|D_{V}^{0}[in_{L}]|}{|D_{V}^{0}|})+\tau|R_{CSG_{R4}}|$
$\displaystyle+|R_{CSG_{R2}}|(1+\tau\frac{|D_{V}^{0}[out_{L}]|}{|D_{V}^{0}|})+\tau|D_{V}^{0}|+\tau|D|$
$\displaystyle C_{emm}(\text{Plan}_{\text{H}})\approx$
$\displaystyle(1+\tau)|R_{CSG_{H8}}|$
$\displaystyle+|R_{CSG_{H6}}|(\tau\frac{|D_{V}^{1}[in_{L}]|}{|D_{V}^{1}|}+\tau\frac{|D_{V}^{0}[in_{L}]|}{|D_{V}^{0}|}+1)$
$\displaystyle+\tau|R_{CSG_{H2}}|+\tau|D_{V}^{0}|(1+\frac{|D_{V}^{0}[out_{L}]|}{|D_{V}^{0}|})+\tau|D|$
$\displaystyle C_{emm}(\text{Plan}_{\text{GF}})\approx$
$\displaystyle|R_{CSG_{G8}}|+(1+\tau)|R_{CSG_{G6}}|$
$\displaystyle+\tau|R_{CSG_{G4}}|(\frac{|D_{V}^{1}[in_{L}]|}{|D_{V}^{1}|}+\frac{|D_{V}^{2}[out_{L}]|}{|D_{V}^{2}|})$
$\displaystyle+\tau|R_{CSG_{G2}}|+\tau|D_{V}^{2}|(1+\frac{|D_{V}^{2}[out_{L}]|}{|D_{V}^{2}|})+\tau|D|$

To actually compute such a cost, we then specify a set of statistics, one can
verify that there exists a data set that satisfies them especially when there
are pulled down filter conditions for label checking contained in these nodes
in the query graph:

$\displaystyle|R_{CSG_{R8}}|=|R_{CSG_{H8}}|=|R_{CSG_{G8}}|=10^{4}$
$\displaystyle|R_{CSG_{R6}}|=|R_{CSG_{H6}}|=|R_{CSG_{G6}}|=2\times 10^{3}$
$\displaystyle|R_{CSG_{R4}}|=2\times 10^{5},\;|R_{CSG_{G4}}|=10^{4}$
$\displaystyle|R_{CSG_{R2}}|=|R_{CSG_{H2}}|=10^{4},\;|R_{CSG_{G2}}|=10^{3}$
$\displaystyle\frac{|D_{V}^{0}[in_{L}]|}{|D_{V}^{0}|}=\frac{|D_{V}^{0}[out_{L}]|}{|D_{V}^{0}|}=\frac{|D_{V}^{1}[in_{L}]|}{|D_{V}^{1}|}=\frac{|D_{V}^{2}[out_{L}]|}{|D_{V}^{2}|}=100$
$\displaystyle|D_{V}^{0}|=|D_{V}^{2}|=|D|=10^{3}$

Then, there are:

$C_{emm}(\text{Plan}_{\text{H}})\approx
0.34\;C_{emm}(\text{Plan}_{\text{RF}})\approx
0.27\;C_{emm}(\text{Plan}_{\text{GF}})$

That is, on this set of data with this designated query, the plan
$\text{Plan}_{\text{H}}$ has the lowest cost as it pulls the join on relation
down to the pattern matching process.

###  F. Operator Resolution

The above discussions are all about CSG and will generate a tree of them that
representing the optimized join order. According to the query optimization
workflow, a query plan will then be resolved corresponding to it. The crucial
points for the operator resolution process here to departure from its
counterpart for conventional relational operator are highlighted in Section
5.3. Below is an overall description of the entire resolution process.

Input: Query graph $Q=(N,E,L,F)$, $CSG_{0},CSG_{1}\subseteq N$.

Output: Operator $op$.

// resolve explorative join condition, as $\mathsf{ResolveExp}$ can only
consider exploration condition in only direction

1$\theta=\text{{$\mathsf{ResolveExp}$}}(CSG_{0},CSG_{1})\cup\text{{$\mathsf{ResolveExp}$}}(CSG_{1},CSG_{0})$

// resolve plain value join condition, $\mathsf{ResolveCond}$ can consider the
condition from two directions

// will not consider the edges with type $\mathsf{duplicate}$

2$\theta=\theta\cup\text{{$\mathsf{ResolveCond}$}}(CSG_{0},CSG_{1})$

// resolve operator, find whether these two CSGs are connected by an
exploration edge

3$e_{e}=null$ // to hold the exploration edge if it exists

4for $v\in CSG_{0}\cup CSG_{1}$ do

5 for $e\in N_{E}(v)$ do

6$\langle l,A\rangle=L(e)$

7if $l\neq explore$ then

8 continue

9$\langle n_{s},n_{d}\rangle=F(e)$

10if $n_{s}\in CSG_{0}$ and $n_{d}\notin CSG_{1}$ then

11 continue // inside $CSG_{0}$ or toward an outside vertex

12if $n_{s}\in CSG_{1}$ and $n_{d}\notin CSG_{0}$ then

13 continue // inside $CSG_{1}$ or toward an outside vertex

14$e_{e}=e$

15if $e_{e}=null$ then

16return $R_{CSG_{0}}\bowtie_{\theta}R_{CSG_{1}}$ // is a plain value join

17$\langle l,A\rangle=L(e_{e})$, $\langle n_{s},n_{d}\rangle=F(e_{e})$ // is
an exploration

18if $n_{s}\in CSG_{0}$ then

19 return $R_{CSG_{0}}{\vec{\bowtie}^{A}}_{\theta}R_{CSG_{1}}$

20return $R_{CSG_{1}}{\vec{\bowtie}^{A}}_{\theta}R_{CSG_{0}}$

Algorithm 2 $\mathsf{ResolveOp}$

$\mathsf{ResolveOp}$ in Algorithm 2 describes the overall operator resolution
process, where the aggression is omitted. By accepting a CSG-CMP pair as
input, explorative conditions and plain value join conditions will be first
resolved, by calling $\mathsf{ResolveExp}$ and $\mathsf{ResolveCond}$
respectively. After that, an operator will be generated according to the edges
connect the two CSGs and be integrated with the resolved conditions. That is,
if the two input CSGs are connected by an exploration edge, an exploration
operator will then be resolved. Otherwise, a plain-value join operator will be
resolved. Meanwhile, it should be noticed that according to the query graph
construction process and the CSG-CMP pairs filter atop of the plan enumeration
method, any two CSGs that are considered for operator resolution here can only
be connected by a single exploration edge or several edges for plain join
conditions.

We then show how the explorative conditions can be resolved according to the
input CSG-CMP pair through $\mathsf{ResolveExp}$ in Algorithm 3. Corresponding
to the description in Section 5.3, outward edges from one CSG will be first
explored to find the nodes not contained in both CSGs. For these explored
nodes, it will be checked whether there are edges connecting them to the other
CSG. If so, those edges will be considered as explorative join conditions. The
$\mathsf{ResolveCond}$ resolves plain join conditions along the same line as
its relational counterpart and will not be further explained here.

With the above operator resolution process, a logical query plan can then be
rewritten from the optimized CSG tree accordingly.

Input: Query graph $Q=(N,E,L,F)$, $CSG_{0},CSG_{1}\subseteq N$.

Output: Explorative condition set $\theta^{I}$.

1$\theta^{I}=\\{\\}$

2for $n_{0}\in CSG_{0}$ do

3 for $e\in N_{E}(n_{0})$ do

4$\langle l,A\rangle=L(e)$

5if $l\neq{\mathsf{explore}}$ then

6 continue // is not an exploration edge

7$\langle n_{s},n_{d}\rangle=F(e)$

8if $n_{d}\in CSG_{0}\cup CSG_{1}$ then

9 continue // has already been considered

// to find the edges connect $n_{d}$ and nodes in $CSG_{1}$

10for $e_{c}\in N_{E}(n_{d})$ do

11$\langle l_{c},A_{c}\rangle=L(e_{c})$

12if $l_{c}={\mathsf{explore}}$ then

13 continue

14if $N(e_{c})\subseteq CSG_{1}\cup\\{n_{d}\\}$ then

// $e_{c}$ can be resolved as explorative join condition

15$\theta^{I}=\theta^{I}\cup\\{\psi(A)[A_{c}]\ni A_{c}\\}$

16return $\theta^{I}$

Algorithm 3 $\mathsf{ResolveExp}$

###  G. Query Execution

Introducing the exploration operator into the query plan allows the access on
graph and relational data to be executed seamlessly without switching to
another execution engine to avoid performance degradation, instead of merely
satisfying a taste of elegance.

A typical example is demonstrated in Figure 6 but was not clearly explained in
Section 5.3 due to the limitation of space, which will be explained with a
step-by-step example here in detail.

###### Example 3.

Considering the three stages of the pipelined execution for
$\text{Plan}_{\text{H}}$ in Figure 6, that access across the relational and
graph data without breaking the pipelined execution process.

  1. (1)

In $\text{stage}_{\text{1}}$, an exploration operator
$R_{CSG_{H2}}{\vec{\bowtie}^{D_{o}^{0}.dst_{L}}}D_{V}^{1}$ is executed. Field
$D_{o}^{0}.dst_{L}$ is held in the pipeline intermediate result $R_{CSG_{H2}}$
which points to relation $D_{V}^{1}$. During the exploration process, all
tuples $t_{H2}\in R_{CSG_{H2}}$ will be explored to iterate over all tuples
$t_{V}^{1}\in\psi(t_{H2}[D_{o}^{0}.dst_{L}])\subseteq D_{V}^{1}$ to grab field
$t_{V}^{1}[in_{L}]$ into the next stage of the pipelined intermediate result
till it is filled.

  2. (2)

In $\text{stage}_{\text{2}}$, an ordinary join operator
$R_{CSG_{H4}}\bowtie_{D_{V}^{0}.vid=D.uid}D$ is executed. Field
$D_{V}^{0}.vid$ is held in the pipeline intermediate result $R_{CSG_{H4}}$.
All tuples $t_{H4}\in R_{CSG_{H4}}$ will then be iterated, to join on all
tuples $t_{R}\in D$ _s.t._ $t_{H4}[D_{V}^{0}.vid]=t_{R}[uid]$.

  3. (3)

In $\text{stage}_{\text{3}}$, an intersective exploration operator is
executed,
$R_{CSG_{H6}}{\vec{\bowtie}^{D_{V}^{1}.in_{L}}}_{\psi(D_{V}^{0}.in_{L})[src_{L}]\ni
src_{L}}D_{i}^{1}$, to continue the pattern matching process. Field
$D_{V}^{0}.in_{L}$ and $D_{V}^{1}.in_{L}$ are held in the pipeline
intermediate result $R_{CSG_{H6}}$. All tuples $t_{H6}\in R_{CSG_{H6}}$ will
be iterated, to intersect all tuples
$t_{i}^{2}\in\psi(t_{H6}[D_{V}^{0}.in_{L}])\subseteq D_{i}^{2}$ and
$t_{i}^{1}\in\psi(t_{H6}[D_{V}^{1}.in_{L}])\subseteq D_{i}^{1}$, _s.t._
$t_{i}^{1}[src_{L}]=t_{i}^{2}[src_{L}]$.

In the external level, it can be seen that $\text{stage}_{\text{1}}$ to
$\text{stage}_{\text{3}}$ explore the graph data, relational data and back to
the graph data subsequently without breaking the pipelined execution.

Figure 14. A step-by-step demonstration of the conversion process from
relations to $\mathsf{RG}$ model

###  H. Graph Representation in RG Model

The example below provides a detailed explanation to illustrate how graph-
structured data can be represented in the $\mathsf{RG}$ model. Different from
the description in Section 4.1 for encoding graph-structured data, the example
here offers a (conceptional) conversion process from a relational
representation of the graph data, to emphasize the extensions that the
$\mathsf{RG}$ model introduces into the relational model.

###### Example 4.

Taking $G$ in Figure 1 as an example, Figure 14 provides a step-by-step
explanation to store the graph $G$ in the $\mathsf{RG}$ model from a
relational representation of it. As a simplification, we do not consider the
property on both vertices and edges here.

  1. (0)

The relational representation of $G$ consists of three relations:
$\mathsf{D_{V}(vid,label)}$ to hold all vertices in $G$;
$\mathsf{D_{in}(dst,eid,label,src)}$ to hold all edges in $G$;
$\mathsf{D_{out}(src,eid,label,dst)}$, as a duplication of $\mathsf{D_{in}}$,
or a virtual view of it.

  2. (1)

Add pointer field $out_{L}$ (resp. $in_{L}$) into $D_{V}$ to connect to all
outward (resp. input) edges for each vertex in it, which makes it become
$\mathsf{D_{V}(vid,label,out_{L},in_{L})}$. Field $src$ in $D_{in}$ and $dst$
in $D_{out}$ can then be removed, for them to become
$\mathsf{D_{in}(eid,label,dst)}$ and $\mathsf{D_{out}(src,eid,label)}$
respectively. It thence reduces the duplication between $D_{in}$ and
$D_{out}$.

  3. (2)

Replace the field $src$ in $D_{in}$ (resp. $dst$ in $D_{out}$) as $src_{L}$
(resp. $dst_{L}$), that is, for each tuple $t\in D_{in}$ (resp. $t\in
D_{out}$), replace the value of its field $t[src]\in\mathbb{V}$ (resp.
$t[dst]\in\mathbb{V}$) with pointer $t[src_{L}]\in\mathbb{P}$ (resp.
$t[dst_{L}]\in\mathbb{P}$) towards the same vertex tuple. We can then get
$\mathsf{D_{in}(eid,label,dst_{L})}$ and
$\mathsf{D_{out}(src_{L},eid,label)}$.

  4. (3)

Fragment the extended relation $D_{in}$ and $D_{out}$ according to the
pointers in $out_{L}$ and $in_{L}$ in $D_{V}$, as mentioned in Section 4.1.

One can verify that the $\mathsf{RG}$ representation obtained in the above
process is equivalent to the one resulted in Example 2.

It should be noticed that the extended relations $D_{\mathsf{V}}$,
$D_{\mathsf{out}}$, $D_{\mathsf{in}}$ and the dereference function $\psi$ in
$\mathcal{D}_{G}^{E}$ have actually already been obtained at
$\text{stage}_{\text{2}}$. The following $\text{stage}_{\text{3}}$ is only to
complete the fragmentation to support an efficient exploration through the
pointer. It is also noteworthy that the fragmentation performed in
$\text{stage}_{\text{3}}$ is actually at the logical level, without specifying
the memory layout or the physical designs.

(a) $\mathsf{DBLP}$ (b) $\mathsf{IMDB}$ (c) $\mathsf{YAGO}$

Figure 15. Heterogeneous fragment storage estimation

(a) $\mathsf{DBLP}$ (b) $\mathsf{IMDB}$ (c) $\mathsf{YAGO}$

Figure 16. Incremental data movement estimation

Meanwhile, it can also be clearly verified here that the $\mathcal{D}_{G}^{E}$
is in the regular form. That is, all pointers in field $out_{L}$ (resp.
$in_{L}$) of $D_{V}$ reference to the tuples in $D_{out}$ (resp. $D_{in}$);
the pointers in both fields $src_{L}$ (resp. $dst_{L}$) of $D_{in}$ (resp.
$D_{out}$) all point to tuple in $D_{V}$. Therefore, given a pointer
$p\in\mathbb{P}$, the relation that holds $\psi(p)$ can be looked-up according
to the underlying field of $p$. A node can then be introduced into the query
graph as an alias of that relation to correspond to the explorative condition
as in Appendix C.

###  I. Evaluation on Memory Management

We evaluated the proposed heterogeneous fragment management strategy, on its
storage cost and maintenance cost.

Exp-6: Storage cost. As described in Section 4, the extended relations need to
be fragmented to efficiently support the exploration of a set of tuples.
However, such a process will inevitably introduce additional costs, including
the storage for the additional pointer fields and the internal fragmentation
inside a block. We evaluated the cost introduced by the heterogeneous fragment
management strategy, denoted as $\mathsf{hetero}$, with the following four
kinds of baseline: (1) $\mathsf{relational}$, stores graph data in vertex
relation $D_{V}(vid,label)$ and edge relation $D_{E}(eid,src,label,dst)$; (2)
$\mathsf{relational\text{-}index}$, further considers two indexes on $src$ and
$dst$ field on the edge relation $D_{E}$ respectively; (3)
$\mathsf{pure\text{-}seg}$, stores graph data in the $\mathsf{RG}$ model and
treats all fragments as segments, even the very large ones, and will not
divide them into blocks; (4) $\mathsf{pure\text{-}block}$, stores graph data
in the $\mathsf{RG}$ model and allocates at least one block for each fragment.
We set the block size as $\mathsf{64KB}$ and varied the predefined block-
segment threshold for heterogeneous fragment management mentioned in Section
4.2, to evaluate the cost introduced in such a process.

Evaluated with real-life data, we demonstrated in Figure 15 that storing graph
data in the $\mathsf{RG}$ model with the $\mathsf{pure\text{-}seg}$ setting
took 51.5%, 49.9% and 46.1% additional space on $\mathsf{DBLP}$,
$\mathsf{IMDB}$ and $\mathsf{YAGO}$ respectively compared to the
$\mathsf{relational}$ baseline. However, when taking the storage for the
indexes data into account, _i.e.,_ comparing $\mathsf{pure\text{-}seg}$ to
$\mathsf{relational\text{-}index}$, the additional space required on them
would be reduced to 9.08%, 5.01% and 6.52% respectively. It should be noticed
that the indexes on edge relation took a large portion of the storage since we
did not considered heavy property on both vertex and edge in the graph data.
Considering the two additional indexes is equivalent to consider the columns
$src$ and $dst$ in the edge relation twice which can largely increase the
required space. Therefore, it can be seen that the space utilized for storing
graph data in the $\mathsf{RG}$ model is basically equivalent to storing the
same set of data in relations and then add indexes on them.

We then vary the predefined block-segment threshold to evaluate the extra
storage cost that the internal fragmentation in the heterogeneous memory
management strategy can bring. As shown in Figures 15(a) to 15(c) , when the
threshold is set to $\mathsf{8}$ KB, _i.e.,_ the fragments smaller than
$\mathsf{8}$ KB will all be managed as segments, $\mathsf{hetero}$ took 24.5%,
11.5% and 21.7% additional space compared to $\mathsf{pure\text{-}seg}$ on
these three data graphs respectively. Meanwhile, the heterogeneous management
also significantly reduced (¡ 1/100) the space required for the
$\mathsf{pure\text{-}block}$ strategy (not drawn).

Exp-7: Maintenance cost. We then evaluated the maintenance cost and the
reduction of data movement amount achieved by the heterogeneous fragment
management strategy. For each data graph $G$, we generated a $\Delta G$ on it
and compared the data movement amount required to accept such an update by the
heterogeneous fragment management strategy, denoted as $\mathsf{hetero}$, with
two kinds of baselines: (1) in $\mathsf{new\text{-}data}$, we simply
calculated the size of new inserted edges; (2) in $\mathsf{pure\text{-}seg}$,
we calculated the data movement amount required when all fragments are managed
as segments, where all introduced edges would uniformly require their
underlying segments to be reallocated. We also estimated the ratio of extra
data movement required by these two strategies, _i.e.,_ compared
$\mathsf{hetero}$ and $\mathsf{pure\text{-}seg}$ to
$\mathsf{new\text{-}data}$, denoted as $\mathsf{hetero\text{-}extra}$ and
$\mathsf{pure\text{-}seg\text{-}extra}$ respectively.

Figure 16 shows the data movement amount required for segment reallocation
when different amounts of new edges were inserted into the data graph that had
been stored in the $\mathsf{RG}$ model. Owing to their topological
characteristics, it can be seen that the data movement amount in
$\mathsf{pure\text{-}seg}$ baseline were not extraordinarily larger than the
$\mathsf{new\text{-}data}$ on both $\mathsf{DBLP}$ and $\mathsf{YAGO}$. That
is, on these two data graphs, the introduced edges were all added into the
relatively small fragments and thus does not introduce much extra data
movement. However, the situation is completely different on $\mathsf{IMDB}$,
as the introduced edges can easily connect to vertices with a large degree,
the required data movement to reallocate the underlying segment thence becomes
unacceptable even with only a very few edges inserted. Meanwhile, on all data
graphs, the ratio of extra data movement required in both fragment management
strategises were reduced as the number of inserted edges increases. This is
due to the size of the tuples inserted into the segments is becoming
comparable to the data that these segments originally held.

The experimental result shows that the heterogeneous memory management
strategy can significantly reduce the extra data movement enforced by
introducing a small amount of edges. With the block size set to
$\mathsf{64KB}$ and the predefined block-segment threshold set to
$\mathsf{8KB}$, such a strategy can reduce the extra data movement in
$\mathsf{pure\text{-}seg\text{-}extra}$ by 1.71x, 9.49x and 1.54x on these
three data graphs respectively when 1‰ new edges are inserted into them.
Combining with the storage cost estimated in Exp-6, it can be seen that such a
heterogeneous strategy fairly achieved a trade-off between these two
strategies. We defer an in-depth study to apply more advanced dynamic memory
management strategies (Wilson et al., 1995) to future work to further reduce
the extra data movement here.

###  J. Notation Collection

We collect the frequent used notations in Table 2, ordered by the location of
their first appearance.

| Notation | Conception
---|---|---
Section 2 |  $\mathbb{V}$ |  domain of plain values
$P[\bar{A}](G)$ |  graph pattern query
$\bowtie_{\delta}$ |  join on semantic connection
${\mathsf{RA_{\delta}}}$ |  proposed relational algebra dialect
${\mathsf{SQL_{\delta}}}$ |  proposed $\mathsf{SQL}$ dialect
Section 4.1 |  $\mathbb{P}$ |  domain of pointers
${\mathcal{R}}^{E}$ |  $\mathsf{RG}$ schema
$\mathcal{D}^{E}$ |  extended database
$\phi$ |  injective partial reference function
$\psi$ |  dereference function
${\mathcal{R}}^{E}_{G}$ |  $\mathsf{RG}$ schema of graph $G$
$\mathcal{D}_{G}^{E}$ |  extended relation of graph $G$
$D_{\mathsf{V}}$ |  extended relation of vertices
$D_{\mathsf{out}}$ |  extended relation of outgoing edges
$D_{\mathsf{in}}$ |  extended relation of incoming edges
$F^{v}_{\mathsf{out}}$ |  fragment of $D_{\mathsf{out}}$ of all outgoing edges from $v$
$F^{v}_{\mathsf{in}}$ |  fragment of $D_{\mathsf{in}}$ of all incoming edges toward $v$
Section 5.1 |  $\theta^{I}$ |  notation of explorative condition
$\psi(A)[B]\ni C$ |  form of an explorative condition
$S_{1}\vec{\bowtie}^{A}_{\theta}S_{2}$ |  the (logical) exploration operator
$S_{1}\>{\bowtie}_{\theta^{I}}S_{2}$ |  the (logical) join with explorative condition
$S_{1}\>\vec{\bowtie}^{A}_{\theta^{I}}S_{2}$ |  the (logical) intersective exploration
Section 5.3 |  $(S_{1},A,S_{2})$ |  form of an exploration edge
$|S|$ |  cardinality estimated for relation $S$
$|S[A]|$ |  cardinality estimated for data linked by field $A$ in $S$
$C(v_{i})$ |  candidate set generated for pattern vertex $v_{i}$
$D^{C}_{v_{i}}$ |  separated relation to store $C(v_{i})$
Table 2. Summary of notations Level | Relational Model | Relational Genetic Model | Graph Model
---|---|---|---
structural | operational | structural | operational | structural | operational
External |  relational views |  $\mathsf{SQL}$ etc. |  relational views \+ graph views |  ${\mathsf{SQL_{\delta}}}$ |  graph views |  graph query languages
Logical |  base relations |  logical operators |  extended relations |  logical operators \+ exploration |  base graphs |  logical graph operators
Physical |  physical designs |  physical operators |  physical designs \+ pointers |  physical operators \+ exploration |  physical designs for graph |  physical graph operators
Table 3. A comparison of different data models under the perspective of the
three level architecture

###  K. Query Language Comparison

Again, instead of providing a fully-featured and well-standardised query
language for the community to follow, ${\mathsf{SQL_{\delta}}}$ is proposed
here mainly as a demo language to verify the concept of hybrid queries across
graph and relational data, and also to make our discussions on query
evaluation more concentrated. It should also be noted again that such a
language is defined on the external-level of the $\mathsf{RG}$ model as shown
in Figure 2 and Table 3, where the introduced logical-level pointers are
hidden to avoid introducing unacceptable complexity.

However, by saying that ${\mathsf{SQL_{\delta}}}$ is a demo language, we do
not mean that it is overly simplified and overlooks the key features of
various graph query languages, or is in an unusable shape. In fact, a large
portion of those features provided by various graph query languages are
equivalently achieved in ${\mathsf{SQL_{\delta}}}$ by combing few key features
from both the graph-side and relational-side query languages. The most
significant limitation on the expressiveness of ${\mathsf{SQL_{\delta}}}$
appears in the lack of support for the recursive feature, which is far beyond
the scope that can be discussed here but can have some alternative temporary
solution and will be systemically studied in future work.

Below, we compare the expressiveness and the usability of
${\mathsf{SQL_{\delta}}}$ with some graph query languages:

Expressiveness. Following the same categorisation of query features and
semantics in (Angles et al., 2017), we first compare the expressiveness of
${\mathsf{SQL_{\delta}}}$ with other graph query languages. We listed the
comparison on pattern matching queries and navigational queries in Table 4 and
Table 5 respectively. Meanwhile, although they are not collected in the same
table, considering the connection between the RDF model and the relational
model, it can be seen that the other graph algebras built atop of the
relational model (Zhao and Yu, 2017) can, at most, achieve an equivalent
expressiveness as SPARQL.

Comparing to the various graph query languages, the most significant
limitations of ${\mathsf{SQL_{\delta}}}$ appear on the navigational queries,
since it can only describe the path with fixed-length patterns which might
even hard to be called a real “navigational” query. The navigational queries
in those graph query languages are mainly described by path with different
kinds of regular expressions, which can be, and can only be, equivalently
achieved in $\mathsf{SQL}$ with a recursive extension (Sakr et al., 2021).
Although a consideration of the recursive features is far beyond the scope
that can be discussed here, previous works (Jindal et al., 2015) also provide
an alternative way to support recursive exploration, _i.e.,_ repeatedly
running a script until it reaches a fixed point. However, such an approach is
only a temporary solution and is far from considering all the optimization
methods available for recursive relational queries (Bancilhon et al., 1985),
we thus defer a systemic study on this to further work.

In conclusion, as a demo language to prove the concept of hybrid query across
graph and relational data, ${\mathsf{SQL_{\delta}}}$ can fairly express the
core concepts of the graph query languages especially on pattern queries.
Meanwhile, the limitations on navigational queries in
${\mathsf{SQL_{\delta}}}$ can have some temporary solutions as in (Jindal et
al., 2015), and a systematic study on this can be achieved by incorporating
more classical works on recursive relational queries (Bancilhon et al., 1985),
which is deferred to future work.

Usability. We further analysis the usability of such a demo language, more
specifically, on its composability, ease of pattern specification, and
simplicity of its query interface.

Composability. The composability is to say that the output of a query can be
used as the input of another query, which is overlooked by the graph query
languages in the early stage (W3C Recommendation, 2008; van Rest et al.,
2016). The recent query languages (Angles et al., 2018), and recent versions
of some evolving query languages (Francis et al., 2018), achieve such a
property in different ways by exporting the result of a query as a graph
(Angles et al., 2018) or passing “table-graphs” (Francis et al., 2018). As a
dialect of $\mathsf{SQL}$, ${\mathsf{SQL_{\delta}}}$ then naturally retains
its capability of query composition, that is, it can naturally export the
result of the query on the graph-side data as relations for it to be regarded
as the input of another query.

Pattern specification. There are majorly three styles to specify the pattern
to be matched on data graph in previous graph query languages, namely, the
“SQL-like” style (W3C Recommendation, 2008); the “functional” style (Tin,
2017); and the “ASCII-art” style (39075, 2023; 9075-16, 2022; Angles et al.,
2018; Deutsch et al., 2022; Francis et al., 2023, 2018; van Rest et al.,
2016). Among them, the “ASCII-art” style is undoubtedly the easiest-to-use and
the most widely-recognized one in the community of graph query language, as it
is utilized in a major portion of the query languages from both academia and
industry, which is thus followed in ${\mathsf{SQL_{\delta}}}$.

Query interface. An important lesson learnt from the “great battle” between
the relational and the CODASYL model (Bachman et al., 1969) is that the
complicated structures is almost impossible for the practitioners to
understand (Stonebraker and Hellerstein, 2005). Therefore, in $\mathsf{RG}$
model, as shown in Figure 2, the similar pointer structures are introduced,
but they only appear on the logical level and are hidden from the external
view. That is, for the practitioners who are trying to query on the data by
writing declarative queries, they can only view on the certain relations and
certain graphs, without seeing the extended relations with complicated pointer
structures behind them on logical level.

Language | Supported patterns | Semantics
---|---|---
SPARQL (W3C Recommendation, 2008) | all complex graph patterns | homomorphism-based, bags
Cypher (Francis et al., 2018) | all complex graph patterns | no-repeated-edges, bags
Gremlin (Tin, 2017) |  all complex graph patterns without explicit optional | homomorphism-based, bags
${\mathsf{SQL_{\delta}}}$ | all complex graph patterns | homomorphism-based, bags
Table 4. A comparison of semantics for pattern matching Language | Path expressions | Semantics | Choice of output
---|---|---|---
SPARQL |  more than RPQs |  arbitrary paths, sets | boolean / nodes
Cypher |  fragment of RPQs |  no repeated edges, bags |  boolean / nodes / paths / graphs
Gremlin |  more than RPQs |  arbitrary paths, bags | nodes / paths
${\mathsf{SQL_{\delta}}}$ |  fixed-length path queries |  fixed-length paths, bags | boolean / nodes
Table 5. A comparison of semantics for navigational queries

By doing so, those logical level pointers can be utilized to support a more
efficient exploration without exposing themselves to the external view and can
thus keep the query interface simple. An illustration of the $\mathsf{RG}$
model according to the three level architecture of data model (Date, 2000;
ste, 1975; Codd, 1990) is demonstrated in Table 3. It can be seen that at the
external level, $\mathsf{RG}$ is a combination of the graph and relational
data, while ${\mathsf{SQL_{\delta}}}$ is a demonstration of a unified query
language to access across them.

However, such a distinction between the graph and relational data would be
eliminated at the logical level, where both sides of data are represented
uniformly with extended relations as shown in Section 4.1, which thus provides
a unified plan space for the access on graph and relational data to be
considered in any order without involving cross-model access (gim, 2021;
Hassan et al., 2018b; Vyawahare et al., 2018). The practitioners then only
need to concentrate on how to express their query without considering it can
be evaluated efficiently, as the optimizer behind provides a unified plan
space to select the optimal one from them (see Section 5.3).

Conclusively, as a demo language, ${\mathsf{SQL_{\delta}}}$ shows that it is
possible to provide a query across graph and relational data, which:

  * $\circ$

has the composability to uniformly allow both the query result from both graph
and relational data as the input of the other query;

  * $\circ$

allows the pattern to be match on the data graph to be specified with a widely
accepted “ASCII-art” style, while supporting most of the key features in the
various graph query languages;

  * $\circ$

has a unified query interface without exposing the complicated pointer
structures at the external level, with a capability for automatic optimization
to liberate the programmers from considering the detailed execution procedure;

By showing those core features, ${\mathsf{SQL_{\delta}}}$ proves its potential
to be considered as a core language, and to be further extended into a fully-
featured, well-standardized practical query language.