基于图结构特征采样数据摘要的联邦知识图谱查询

Federated Knowledge Graph Query Based on Graph Structure Feature Sampling Data Summary

联邦SPARQL查询是通过构建查询计划来指导查询执行,数据摘要索引文件捕获了RDF数据集的结构和语义信息,对查询计划生成过程中子查询基数评估至关重要。现有的数据摘要生成方法需要远程遍历每个数据源的完整数据,该过程成本消耗较高,且在大部分环境中联邦查询无法完成对大数据集的统计工作。为在减少数据摘要索引文件生成时间和内存开销的同时捕获尽可能真实的计数信息,考虑主语和谓语的分布偏差,提出利用样图生成原始图近似数据摘要的方法。使用对RDF图出度特征加权的采样方法获取原始图的典型样图,通过改进的映射函数将样图中的信息映射到原始图上,从而生成原始图的近似数据摘要。实验结果表明,该方法相比于基线方法至少节省了70%的数据摘要索引文件生成时间,并且仅采样0.5%的原始图生成的近似数据摘要即可在查询正确率上与基线方法保持高度一致。

The federated system processes SPARQL queries by constructing an effective query plan to guide query execution.The data summary index file captures the structure and semantic information of Resource Description Framework(RDF)datasets,essential for the cardinality evaluation of subqueries during query plan generation.Existing data summary generation methods need to traverse the complete data of each source remotely,which consumes a high cost.In most environments,the federated query cannot complete the statistics of large datasets.This study proposes a method for generating the approximate data summary of the original graph based on the sample graph to solve this defect.The aim is to capture the actual count information as much as possible while reducing the generation time and memory overhead of the data summary index file.Specifically,this method first uses the sampling method of weighting the degree feature of the RDF graph to obtain the typical sample of the original graph.Next,the improved mapping function reflects the information in the sample graph to the original graph to generate the approximate data summary of the original graph.During this process,the distribution deviation of the subject and predicate is considered in this method.The experimental results show that the proposed method saves at least 70%of the generation time of the data summary index file compared with the Baseline method.In addition,the approximate data summary generated only from0.5%of the original graph is highly consistent with the Baseline method in query accuracy.