论文部分内容阅读
资源描述框架(Resource Description Framework，RDF)是描述Web资源的标准数据模型。由于Web数据的半结构化特性，RDF查询语言应该提供对半结构化数据的查询机制。W3C新近提出的SPARQL语言(草案)中的非强制匹配就是这种查询机制，本文着重研究SPARQL中非强制匹配的查询处理技术。在分析SPARQL中非强制匹配的语法和语义、总结现有非强制匹配查询处理方法及其不能处理多重和嵌套非强制匹配的缺陷的基础上，本文提出一种实现非强制匹配查询的处理算法，该算法不仅支持简单非强制匹配，而且支持多重非强制匹配和嵌套非强制匹配，以及复杂的多重嵌套非强制匹配，并且从理论上分析该算法的时间复杂度。在算法设计与理论分析的基础上，本文设计实现了支持非强制匹配查询的原型系统ROMQS，用于用户提交SPARQL查询和所要查询的RDF图、执行查询、浏览查询结果。为进行实验验证，本文设计了大量不同规模的包含不完全、不规则信息的RDF图，并针对这些RDF图设计了一组SPARQL非强制匹配查询；通过将这些查询在ROMQS中的执行结果与理论上的正确结果相比较，验证了非强制匹配查询处理算法的有效性；基于大量的实验数据，分析了非强制匹配查询处理算法的时间复杂度；将ROMQS与其他RDF查询系统进行比较，验证了ROMQS具有能够处理多重和嵌套非强制匹配的功能优势。