目前RDF图的导航查询均基于正则表达式,但由于正则表达式受限的表达能力,使得相应的导航查询只能提供RDF图上较弱的导航查询能力,无法表达诸如同代查询(same-generations queries)这样实际中的经典查询问题。同时RDF图的导航查询通常具有较高的计算复杂度,如何提高RDF图的导航查询能力的同时控制计算复杂度的提升,成为亟待解决的研究问题。本文提出RDF图的上下文无关导航查询,利用上下文无关文法相比正则表达式更强的表达能力,在不增加计算复杂度的前提下,增强了RDF图的导航查询能力。本文形式化定义了上下文无关路径查询的语法和语义,给出查询实现算法和计算复杂度,证明了上下文无关路径查询相比正则路径查询拥有更强的导航查询能力。之后将RDF图的上下文无关路径查询进行了实现,选取经典RDF图数据,以实际导航查询需求为例进行了实验。实验结果表明,上下文无关路径查询能从RDF图中返回正则路径查询无法得到的查询结果,且查询时间在预期范围内。本文进一步将上下文无关路径查询加入RDF图的标准查询SPARQL中,提出了上下文无关SPARQL(context-free SPARQL,简称cfSPARQL),给出了cfSPARQL的语法和语义,并分析了它的导航表达能力和计算复杂度;cfSPARQL在不增加计算复杂度的前提下,扩展了标准SPARQL使其具有更强的导航查询能力。综上所述,本文提出的基于上下文无关文法的导航查询,提高了RDF图导航查询能力的同时维持了原有的计算复杂度,使得SPARQL突破正则路径查询的限制,拓宽了应用范围。上下文无关导航查询增强的导航查询能力,能够用于图的相似性建模,本体对齐和自然语言处理中的上位词提取等研究领域。