论文部分内容阅读
资源描述框架(Resource Description Framework，RDF)是W3C组织提出的描述万维网上资源的通用模型，该模型已广泛应用于诸多领域，如语义网络中的资源描述、元数据描述、搜索引擎语义处理等。随着语义网络中数据量的激增，在RDF数据集中高效查询数据已成为一个亟待解决的问题。传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数，加快查询模式重写过程，但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题。此外，大数据背景下基于视图机制的RDF模式匹配方法在候选视图检索、初始化视图集构造等方面也面临新的挑战。针对上述问题，论文工作展开基于视图的RDF模式匹配研究。 论文主要工作如下: (1)为了减小查询模式重写代价，提高RDF模式匹配过程效率，引入可排序视图概念，简化包含映射的发现过程，同时保证模式间的匹配代价与输入数据的规模线性相关。 (2)定义RDF模式匹配算法框架，设计包含映射发现算法contain（contain+），简化等长度模式间包含映射发现过程;提出基于倒排表检索候选可排序视图的方法，并实现RDF模式重写算法rewrite，有效解决中小规模数据集上的RDF模式匹配问题。 (3)分析大数据背景下RDF模式匹配问题的困难所在，基于Map Reduce计算模型实现检索候选可排序视图算法findSortedViews，提出rewrite+算法解决大规模数据集上的模式匹配问题;从冗余视图裁剪、查询模式集合覆盖等方面对RDF模式重写的优化进行定性分析;结合可排序性质及自定义“打分机制”，在Twitter Storm平台上部署InitViewSet算法，优化视图集初始化构造过程。 理论分析及实验证明，基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性。