统一的SPARQL查询分析语言设计与理论研究

作     者：宋昕 

作者单位：天津大学 

学位级别：硕士

导师姓名：陈世展;陈列伟

授予年度：2019年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：图分析 图查询 SPARQL RDF 

摘      要：在解决复杂的大规模图处理任务时,需要频繁交替使用图查询与图分析,然而目前在理论上图查询与图分析尚未统一,造成查询与分析结果的可靠性无法保证,进而导致查询与分析的优化方法有限。所以如何统一图查询与图分析,设计包含图查询与图分析的统一理论框架对于高效解决大规模图处理任务十分重要。本文基于SPARQL图查询语言,建立统一的图查询与图分析理论基础,包括其语法及语义,并研究讨论其基础理论性质,即表达性与复杂性问题。本文引入丰富的图分析算法,构造出分析子句,提出SPARQL分析查询语言。针对不同复杂程度的图处理问题,该语言具有两种表现形式,分别称为单层SPARQL分析查询语言和嵌套SPARQL分析查询语言,其中嵌套SPARQL分析查询语言还具有内外层嵌套与同级嵌套两种嵌套形式。本文基于原始SPARQL语义,构造了单层SPARQL分析查询语言和嵌套SPARQL分析查询语言的语义,并证明了两种嵌套形式的正确性。本文证明了SPARQL分析查询语言与SPARQL四种查询形式之间的表达性问题等,并归纳分析了SPARQL分析查询语言的复杂度问题。最后通过对比实验,验证了SPARQL分析查询语言简洁性与易用性。本文提出的SPARQL分析查询语言,支持带权RDF图上的图查询与图分析,给工业实际中的图查询与图分析提供理论基础,其表达性与复杂性等研究结果,保证了面对大规模图处理任务时结果的可靠性,为图查询与图分析优化提供了理论保障,为统一图查询语言与图分析算法提供了新的思路。