SINA: Semantic interpretation of user queries for question answering on interlinked data

The architectural choices underlying Linked Data have led to a compendium of data sources which contain both duplicated and fragmented information on a large number of domains. One way to enable non-experts users to access this data compendium is to provide keyword search frameworks that can capitalize on the inherent characteristics of Linked Data. Developing such systems is challenging for three main reasons. First, resources across different datasets or even within the same dataset can be homonyms. Second, different datasets employ heterogeneous schemas and each one may only contain a part of the answer for a certain user query. Finally, constructing a federated formal query from keywords across different datasets requires exploiting links between the different datasets on both the schema and instance levels. We present Sina, a scalable keyword search system that can answer user queries by transforming user-supplied keywords or natural-languages queries into conjunctive SPARQL queries over a set of interlinked data sources. Sina uses a hidden Markov model to determine the most suitable resources for a user-supplied query from different datasets. Moreover, our framework is able to construct federated queries by using the disambiguated resources and leveraging the link structure underlying the datasets to query. We evaluate Sina over three different datasets. We can answer 25 queries from the QALD-1 correctly. Moreover, we perform as well as the best question answering system from the QALD-3 competition by answering 32 questions correctly while also being able to answer queries on distributed sources. We study the runtime of SINA in its mono-core and parallel implementations and draw preliminary conclusions on the scalability of keyword search on Linked Data.     

nSPARQL: A navigational language for RDF

Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In this paper, we propose the query language nSPARQL that uses nested regular expressions to navigate RDF data. We study some of the fundamental properties of nSPARQL and nested regular expressions concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly traversing the input graph. We also show that nesting is necessary in nSPARQL to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators. Regarding complexity of evaluation, we prove that given an RDF graph G and a nested regular expression E, this problem can be solved in time O(|G||E|).     

HMSST+:基于分布式内存数据库的HMSST算法优化

为了解决HMSST(HashMapSelectivityStrategyTree)算法在集中式环境下受限于有限内存的问题,提出了一种新的分布式SPARQL查询优化算法HMSST+。该算法基于Redis提出了一种分布式存储方案,通过平行扩展存储节点和分布式调度,使得海量RDF数据的查询得以在分布集群的内存中实现。采用LUBM1000所大学的测试数据集对查询策略进行了实验,结果表明提出的方法与HMSST算法相比具有更好的扩展能力,与现有的分布式查询方案相比也具有更好的查询效率。     

混合语义约简和选择估值优化SPARQL

本文在定义SPARQL查询优化问题基础上,利用本体中概念间的语义关系提出语义约简优化方案.并通过与选择估值策略的有机结合,给出RS-Opti优化算法及其实现.测试表明:RS-Opti优于单独使用语义约简和选择估值两种优化策略;与其它查询引擎测试对比表明:该优化方案在查询的元组模式个数较多和语义较复杂时效果明显.     

基于扩展ASP的RDF流处理系统

对传感器产生的语义数据流执行复杂推理的能力, 最近已成为语义网社区中的重要研究领域, 而目前大多数RDF流处理系统是以SPARQL (W3C标准RDF查询语言)为基础实现的, 但这些引擎在捕获复杂的用户需求和处理复杂的推理任务方面存在局限性. 针对此问题, 本文结合并扩展了回答集编程(Answer Set Programing, ASP)技术用于对RDF流进行连续的处理. 为了验证本方法的有效性, 首先以智能家居本体为实验对象, 并分析传感器设备间的共有特性及复杂事件以构建本体库; 然后基于本体库产生实例对象, 并通过中间件产生RDF数据流; 接下来通过扩展ASP, 充分利用其表达和推理能力以减少推理时间, 并设计了RDF 流的窗口划分策略等, 然后根据用户的请求, 选择性地进行静态知识库加载等; 最后通过实验与Sparkwave和Laser进行对比, 证明了该方法在延迟和内存上的性能优势.     

RDF partitioning for scalable SPARQL query processing

The volume of RDF data increases dramatically within recent years, while cloud computing platforms like Hadoop are supposed to be a good choice for processing queries over huge data sets for their wonderful scalability. Previous work on evaluating SPARQL queries with Hadoop mainly focus on reducing the number of joins through careful split of HDFS files and algorithms for generating Map/Reduce jobs. However, the way of partitioning RDF data could also affect system performance. Specifically, a good partitioning solution would greatly reduce or even totally avoid cross-node joins, and significantly cut down the cost in query evaluation. Based on HadoopDB, this work processes SPARQL queries in a hybrid architecture, where Map/Reduce takes charge of the computing tasks, and RDF query engines like RDF-3X store the data and execute join operations. According to the analysis of query workloads, this work proposes a novel algorithm for automatically partitioning RDF data and an approximate solution to physically place the partitions in order to reduce data redundancy. It also discusses how to make a good trade-off between query evaluation efficiency and data redundancy. All of these proposed approaches have been evaluated by extensive experiments over large RDF data sets.     

基于属性相关性的SPARQL查询优化方法

目前主流的RDF存储系统都是基于关系数据库的,其查询引擎都是将SPARQL转换为SQL,然后由数据库的查询引擎来执行查询.但是,目前的数据库查询优化器对于连接查询的选择度估计都是基于属性独立假设的,这往往导致估计错误而选择了效率低的执行计划,所以属性相关性信息对于SPARQL查询优化器能否找到效率高的执行计划是非常重要的.针对SPARQL转换为SQL后,因连接操作没有优化导致查询效率不高的问题,提出了利用本体信息自动计算属性相关性的方法,从而调整连接操作的选择度估计值,调整连接顺序,提高SPARQL查询中基本图模式的连接查询效率.     

An empirical study of representing adjectives over knowledge bases: Approach,lexicon and application

Adjectives are common in natural language, and their usage and semantics have been studied broadly. In recent years, with the rapid growth of knowledge bases (KBs), many knowledge-based question answering (KBQA) systems are developed to answer users’ natural language questions over KBs. A fundamental task of such systems is to transform natural language questions into structural queries, e.g., SPARQL queries. Thus, such systems require knowledge about how natural language expressions are represented in KBs, including adjectives. In this paper, we specifically address the problem of representing adjectives over KBs. We propose a novel approach, called Adj2SP, to represent adjectives as SPARQL query patterns. Adj2SP contains a statistic-based approach and a neural network-based approach, both of them can effectively reduce the search space for adjective representations and overcome the lexical gap between input adjectives and their target representations. Two adjective representation datasets are built for evaluation, with adjectives used in QALD and Yahoo! Answers, as well as their representations over DBpedia. Experimental results show that Adj2SP can generate representations of high quality and significantly outperform several alternative approaches in F1-score. Furthermore, we publish Lark, a lexicon for adjective representations over KBs. Current KBQA systems show an improvement of over 24% in F1-score by integrating Adj2SP.