图数据库与子图匹配
什么是图数据库？
图数据库是将现实物理世界映射到信息世界的工具，着重刻画物理世界中的实体（含实体属性）以及实体关系。与传统关系型数据库（RDBMS）相比，图数据库使用节点和节点之间的边来表示实体（含实体属性）和实体之间的关系，最大的区别在于图数据库是Schema-Less的，而关系型数据库是Schema-First的。这给图数据库带来了查询优化的策略、数据划分和分布式处理、事务的并发处理等方面的挑战，同时也给用户带来了理解底层数据、书写高效查询、与现有工具链衔接等方面的挑战。
图数据库的类型和标准
图数据库主要分为属性图和RDF图两种模型，分别对应不同的数据模型和查询语言。属性图使用节点和边上的属性表来表示数据，并定义节点之间的拓扑关系；RDF图使用三元组（subject，predicate，Object）来表示数据，并使用SPARQL作为标准的查询语言。
子图匹配查询及其优化方法
子图匹配是指在一个数据图中寻找与查询图结构相同且节点和边标签一致的子图。子图匹配问题是NP-Complete的，因此实践中存在大量算法来优化子图匹配的判定和列举问题。子图匹配算法主要分为两类：基于回溯搜索的算法和基于多路连接的算法。
- 基于回溯搜索的算法：典型算法包括Ullmann算法和VF2算法。Ullmann算法通过构建匹配矩阵来系统地搜索匹配，并通过邻域连接剪枝来优化搜索过程；VF2算法通过状态转换来搜索匹配，并通过候选对集来优化搜索过程。
- 基于多路连接的算法：典型算法包括Binary Join和Worst-Case Optimal Join。Binary Join通过二路连接来逐步构建匹配结果，而Worst-Case Optimal Join则通过最优连接顺序来最小化中间结果的大小。
我们的工作
我们主要关注RDF图数据库的查询优化，并提出了以下工作：
- gStore：利用关系数据库技术存储RDF数据，并使用基于图结构的索引策略、点为中心Join方法（Worst-Case Optimal Join）和基于代价的Join顺序选择策略来优化SPARQL查询。
- 分布式gStore：通过局部部分匹配和最终结果组装来处理分布式RDF图上的SPARQL查询，并优化了原子操作Set Intersection来提高查询性能。
- 硬件加速：利用GPU架构来加速子图匹配算法，并通过“Join Twice”策略和Exclusive Prefix Sum等技术来实现高效的并行Join操作。
总结
图数据库是一种重要的数据存储和管理技术，子图匹配是图数据库中的一个关键查询。通过使用合适的算法和技术，可以有效地优化子图匹配查询的性能，从而提高图数据库的查询效率和用户体验。
