基于三元组重新排序的有效离散人工蜂群SPARQL查询路径优化
An Effective Discrete Artificial Bee Colony Based SPARQL Query Path Optimization by Reordering Triples
-
摘要: 1、目的（Objective）：查询的响应时间可能会花费很多时间，具体取决于数据库的大小。SPARQL查询的响应时间可能与查询的三重顺序直接相关。通过找到最佳查询顺序，可以大大减少响应时间。对于n个三元组，有n个！可能的查询顺序，因此找到最佳查询顺序是一个挑战。为了减少从数据库查询时的时间成本，应该快速定义最佳三重顺序。
也就是说，某些形状经过优化后可以变成某些形状吗？
2、方法（Method）：人工蜂群算法用于在sparql查询中找到优化的三阶。为了使算法适应该问题，已更新了算法步骤，以便可以在离散空间中搜索。
由于查询顺序更改时产生的响应，因此将优化阶段产生的每个查询的响应与原始查询响应进行比较。
为了防止重试相同的查询，已创建一个数据库，该数据库保留了所生成的查询和响应时间。生成新的查询序列时，首先查看数据库，如果没有，则将其发送到查询数据库。
由于目的是获得一个查询秘密，该秘密产生的时间少于默认查询布局的时间，因此如果达到了向数据库发送查询后已经经过的时间，但尚未产生新查询的答案，则在优化阶段会中断查询周期。
3、结果（Result&Findings）：所提出的方法已经在12种不同类型和大小的查询上进行了测试。将结果与其他7种方法进行了比较。基于人工蜂群算法的查询优化方法优化的SPARQL查询取决于它们的查询类型，即使在大型查询中也可以在合理的时间执行优化，它在12个查询中的9个中取得了卓越的性能。
据调查，形状的三元组的位置对于优化很重要。优化结束后，原始查询形式将受到保护。已经发现优化查询中可能存在某种模式。
4、结论（Conclusions）：基于人工蜂群的方法应用了4种不同的查询类型：链，星，循环和链星。该方法在所有循环查询中均取得了优异的结果。但是，6个三重链，6个三重星和12个三重星查询的性能还不错，但也不是最好的。可以看出，所提出的方法无论查询类型和查询大小如何都可以成功。
研究的范围可以扩展到在不同的查询引擎中运行不同大小的查询。Abstract: Semantic Web has emerged to make web content machine-readable, and with the rapid increase in the number of web pages, its importance has increased. Resource description framework (RDF) is a special data graph format where Semantic Web data are stored and it can be queried by SPARQL query language. The challenge is to find the optimal query order that results in the shortest period of time. In this paper, the discrete Artificial Bee Colony (dABCSPARQL) algorithm is proposed, based on a novel heuristic approach, namely reordering SPARQL queries. The processing time of queries with different shapes and sizes is minimized using the dABCSPARQL algorithm. The performance of the proposed method is evaluated on chain, star, cyclic, and chain-star queries of different sizes from the Lehigh University Benchmark (LUBM) dataset. The results obtained by the proposed method are compared with those of ARQ (a SPARQL processor for Jena) query engine, the Ant System, the Elitist Ant System, and MAX-MIN Ant System algorithms. The experiments demonstrate that the proposed method significantly reduces the processing time, and in most queries, the reduction rate is higher compared with other optimization methods.
下载: