gStore：基于图的SPARQL查询引擎优化
需积分: 9 117 浏览量
更新于2024-07-24
收藏 2.31MB PDF 举报
gStore是一个基于图的SPARQL查询引擎，专为高效处理RDF（Resource Description Framework）数据集中的SPARQL查询而设计。RDF是一种标准模型，用于描述结构化数据，特别适合于语义网和Web本体。论文《gStore: A Graph-Based SPARQL Query Engine》由Lei Zou、M. Tamer Özsu、Lei Chen、Xuchuan Shen、Ruizhe Huang和Dongyan Zhao共同撰写，并在The VLDB Journal上发表，DOI为10.1007/s00778-013-0337-7，收录在2013年的REGULAR PAPER部分。
gStore的核心思想是将RDF数据作为大型图来存储，同时将SPARQL查询表示为查询图。这种转换使得查询解答问题转化为子图匹配问题。查询处理的关键在于开发一种有效的索引结构，结合精心设计的剪枝规则和高效的搜索算法。这些技术旨在解决动态RDF数据集上带有通配符和聚合操作的复杂查询，保证了查询的效率和可扩展性。
与2011年VLDB Conference上展示的论文“gStore: Answering SPARQL Queries via Subgraph Matching”的扩展版本相比，该论文提供了更深入的技术细节和优化策略。论文的贡献包括：
1. **图存储模型**：采用图结构存储RDF三元组，便于查询时利用图形性质进行操作，如路径查找和相似性匹配。
2. **查询图表示**：SPARQL查询被转换为查询图，其中节点代表实体，边代表关系，这有助于直观理解查询意图并支持灵活的查询表达。
3. **索引设计**：为了加速查询处理，gStore设计了一种能有效支持子图匹配的索引，可能包括倒排索引、邻接矩阵或其他形式的图形索引，用于快速定位相关数据。
4. **剪枝规则**：通过预处理和策略，减少不必要的计算，提高查询执行的效率，防止无效的匹配尝试。
5. **搜索算法**：采用高效算法，如深度优先搜索或广度优先搜索，优化了子图匹配过程，确保在大规模数据集上的性能。
6. **动态适应**：gStore能够处理动态变化的RDF数据，通过实时更新索引和查询处理策略，保持查询性能的稳定。
7. **扩展性**：论文强调了gStore系统的可扩展性，即使面对不断增长的数据和复杂的查询，也能保持良好的性能。
gStore通过图形方法提供了一个强大且可扩展的解决方案，为RDF数据的高效查询处理设定了新的标准。其核心技术和实践经验对于那些处理大规模语义数据的系统设计者来说，具有重要的参考价值。
Graph-based SPARQL query engine
Table 1 Frequently used notations
Notation Description
G A RDF graph (Definition 1)
Q A SPARQL query graph (Definition 2)
v Avertexv in a SPARQL query graph (Definition 3)
u A vertex in RDF graph G (Definition 3)
eSig(e) An edge Signature (Definition 5)
vSig(u) A vertex signature (Definition 6)
RS The answer set of the SPARQL query matches
CL The candidate set of the SPARQL query matches
G
∗
A data signature graph (Definition 7)
Q
∗
A query signature graph
A(u) A transaction of vertex u (Definition 16)
O A node in T-index (Definition 16)
O.L The corresponding vertex list of node O
MS(O) The corresponding aggregate set of node O
3. E ={
−−−→
u
1
, u
2
} is a collection of directed edges that con-
nect the corresponding subjects and objects.
4. L
E
is a collection of edge labels. Given an edge e ∈ E,
its edge label is its corresponding property.
An edge
−−−→
u
1
, u
2
is an attribute property edge if u
2
∈ V
l
;
otherwise, it is a link edge.
Figure 1b shows an example of an RDF graph. The vertices
that are denoted by boxes are entity or class vertices, and
the others are literal vertices. A SPARQL query Q is also a
collection of triples. Some triples in Q have parameters.In
Q
2
(in Sect. 1), “?m” and “?bd” are parameters, and “?bd”
has a wildcard filter: FILTER(regx(str(?bd),“1976”)). Figure
2 shows the query graph that corresponds to Q
2
.
Definition 2 A query graph is a five-tuple Q =V
Q
, L
Q
V
,
E
Q
, L
Q
E
, FL, where
1. V
Q
= V
Q
c
∪ V
Q
e
∪ V
Q
l
∪ V
Q
p
is a collection of vertices
that correspond to all subjects and objects in a SPARQL
query, where V
Q
p
is a collection of parameter vertices,
and V
Q
c
and V
Q
e
and V
Q
l
are collections of class vertices,
entity vertices, and literal vertices in the query graph Q,
respectively.
2. L
Q
V
is a collection of vertex labels in Q. The label of
avertexv ∈ V
Q
p
is φ, that of a vertex v ∈ V
Q
l
is its
literal value and that of a vertex v ∈ V
Q
c
∪ V
Q
e
is its
corresponding URI.
3. E
Q
is a collection of edges that correspond to properties
in a SPARQL query. L
Q
E
is the edge labels in E
Q
.An
edge label can be a property or an edge parameter.
4. FL are constraint filters, such as a wildcard constraint.
Fig. 4 Three components in aggregate queries
Note that, in this paper, we do not consider SPARQL
queries that involve type reasoning/inferencing. Thus, the
match of a query is defined as follows.
Definition 3 Consider an RDF graph G and a query graph
Q that has n vertices {v
1
,...,v
n
}.Asetofn distinct vertices
{u
1
,...,u
n
} in G is said to be a match of Q, if and only if
the following conditions hold:
1. If v
i
is a literal vertex, v
i
and u
i
have the same literal
value;
2. If v
i
is an entity or class vertex, v
i
and u
i
have the same
URI;
3. If v
i
is a parameter vertex, u
i
should satisfy the filter con-
straint over parameter vertex v
i
if any; otherwise, there
is no constraint over u
i
;
4. If there is an edge from v
i
to v
j
in Q, there is also an
edge from u
i
to u
j
in G. If the edge label in Q is p
(i.e., property), the edge from u
i
to u
j
in G has the same
label. If the edge label in Q is a parameter, the edge
label should satisfy the corresponding filter constraint;
otherwise, there is no constraint over the edge label from
u
i
to u
j
in G.
Given Q
2
’s query graph in Fig. 2, vertices (005,006,
020,023,024) in RDF graph G of Fig. 1bformamatchof
Q
2
. Answering a SPARQL query is equivalent to finding all
matches of its corresponding query graph in RDF graph.
Definition 4 An aggregate SPARQL query Q consists of
three components:
1. Query pattern P
Q
is a set of triple statements that form
one query graph.
2. Group-by dimensions and measure dimensions are pre-
defined object variables in query pattern P
Q
.
3. (Optional) HAVING condition specifies the condition(s)
that each result group must satisfy.
Figure 4 demonstrates these three components. This
example shows the case where all group-by dimensions cor-
respond to attribute property edges (e.g., “?g”,“?t” and “?y”
in Fig. 4). This is not necessary, and in Sect. 9.3, we discuss
more general cases.
123
剩余25页未读，继续阅读
2022-10-30 上传
328 浏览量
207 浏览量
285 浏览量
2023-02-01 上传
2020-11-29 上传
136 浏览量
458 浏览量
