Semantics preserving SPARQL-to-SQL translation

Most existing RDF stores, which serve as metadata repositories on the Semantic Web, use an RDBMS as a backend to manage RDF data. This motivates us to study the problem of translating SPARQL queries into equivalent SQL queries, which further can be optimized and evaluated by the relational query engine and their results can be returned as SPARQL query solutions. The main contributions of our research are: (i) We formalize a relational algebra based semantics of SPARQL, which bridges the gap between SPARQL and SQL query languages, and prove that our semantics is equivalent to the mapping-based semantics of SPARQL; (ii) Based on this semantics, we propose the first provably semantics preserving SPARQL-to-SQL translation for SPARQL triple patterns, basic graph patterns, optional graph patterns, alternative graph patterns, and value constraints; (iii) Our translation algorithm is generic and can be directly applied to existing RDBMS-based RDF stores; and (iv) We outline a number of simplifications for the SPARQL-to-SQL translation to generate simpler and more efficient SQL queries and extend our defined semantics and translation to support the bag semantics of a SPARQL query solution. The experimental study showed that our proposed generic translation can serve as a good alternative to existing schema dependent translations in terms of efficient query evaluation and/or ensured query result correctness.     

Ultrawrap: SPARQL execution on relational data

The Semantic Web’s promise of web-wide data integration requires the inclusion of legacy relational databases,¹ i.e. the execution of SPARQL queries on RDF representation of the legacy relational data. We explore a hypothesis: existing commercial relational databases already subsume the algorithms and optimizations needed to support effective SPARQL execution on existing relationally stored data. The experiment is embodied in a system, Ultrawrap, that encodes a logical representation of the database as an RDF graph using SQL views and a simple syntactic translation of SPARQL queries to SQL queries on those views. Thus, in the course of executing a SPARQL query, the SQL optimizer uses the SQL views that represent a mapping of relational data to RDF, and optimizes its execution. In contrast, related research is predicated on incorporating optimizing transforms as part of the SPARQL to SQL translation, and/or executing some of the queries outside the underlying SQL environment.Ultrawrap is evaluated using two existing benchmark suites that derive their RDF data from relational data through a Relational Database to RDF (RDB2RDF) Direct Mapping and repeated for each of the three major relational database management systems. Empirical analysis reveals two existing relational query optimizations that, if applied to the SQL produced from a simple syntactic translations of SPARQL queries (with bound predicate arguments) to SQL, consistently yield query execution time that is comparable to that of SQL queries written directly for the relational representation of the data. The analysis further reveals the two optimizations are not uniquely required to achieve a successful wrapper system. The evidence suggests effective wrappers will be those that are designed to complement the optimizer of the target database.     

基于自适应模式的SPARQL查询与优化

传统的RDF存储系统直接将三元组存放到含有3列的关系数据库表中.具体查询时,需扫描整张三元组表,并通过连接操作产生最后的结果.虽然存储直观、实现方便,但是由于每个子查询都需要在整个三元组表上进行,查询效率较低.同时,当实例属性比较多时,大量的连接操作也对查询效率造成影响.为了克服这些缺点,在RDF自适应模式存储系统FlexTable系统上,搭建一个SPARQL查询引擎,将SPARQL查询语句映射到SQL语句,同时根据数据字典信息,对转化后的SQL语句进行优化,提高了查询效率.     

改进RML路由算法及其在基于MAS的P2P系统框架中的应用

P2P计算模型很可能会成为下一个Internet技术的新亮点,基于这种模型的分布式计算已经成为当前研究的热点。目前大部分的研究项目旨在解决P2P的安全、可靠性及路由等问题。文章提出了一种改进的RML路由算法,并介绍了该算法在基于Multi-AgentSystem的P2P系统框架中的应用。     

HMSST:一种高效的SPARQL查询优化算法

在缩小海量数据查询范围的前提下,结合哈希映射和选择策略树提出了一种SPARQL优化算法——HMSST(HashMapSelectivityStrategyTree),实现了SPARQL的查询优化。并针对LUBM 1000所大学的测试数据集对查询策略进行了实验,实验结果表明:提出的HMSST算法以及存储策略相比现有的查询方案,具有更小的存储代价以及更高的查询能力,在大数据集下可以高效地工作,并且该优化方案在查询的元组模式个数较多和语义较复杂时效果更加明显。     

Constitute: The world’s constitutions to read,search, and compare

Constitutional design and redesign is constant. Over the last 200 years, countries have replaced their constitutions an average of every 19 years and some have amended them almost yearly. A basic problem in the drafting of these documents is the search and analysis of model text deployed in other jurisdictions. Traditionally, this process has been ad hoc and the results suboptimal. As a result, drafters generally lack systematic information about the institutional options and choices available to them. In order to address this informational need, the investigators developed a web application, Constitute [online at http://www.constituteproject.org], with the use of semantic technologies. Constitute provides searchable access to the world’s constitutions using the conceptualization, texts, and data developed by the Comparative Constitutions Project. An OWL ontology represents 330 “topics”–e.g. right to health–with which the investigators have tagged relevant provisions of nearly all constitutions in force as of September of 2013. The tagged texts were then converted to an RDF representation using R2RML mappings and Capsenta’s Ultrawrap. The portal implements semantic search features to allow constitutional drafters to read, search, and compare the world’s constitutions. The goal of the project is to improve the efficiency and systemization of constitutional design and, thus, to support the independence and self-reliance of constitutional drafters.     

SPARQL查询引擎设计

论文以通用的不依赖于具体RDF平台的SPARQL查询引擎的设计与实现作为研究对象。并从SPARQL语法解析器、引擎系统的优化设计等方面进行了深入的探讨,提出了合理的设计策略和实现方法。     

基于RDF图结构切分的高效子图匹配方法

针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架（RDF）图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。     

A survey of RDF data management systems

RDF is increasingly being used to encode data for the semantic web and data exchange. There have been a large number of works that address RDF data management following different approaches. In this paper we provide an overview of these works. This review considers centralized solutions (what are referred to as warehousing approaches), distributed solutions, and the techniques that have been developed for querying linked data. In each category, further classifications are provided that would assist readers in understanding the identifying characteristics of different approaches.     

Querying for provenance, trust, uncertainty and other meta knowledge in RDF

The Semantic Web is based on accessing and reusing RDF data from many different-sources, which one may assign different levels of authority and credibility. Existing Semantic Web query languages, like SPARQL, have targeted the retrieval, combination and re-use of facts, but have so far ignored all aspects of meta knowledge, such as origins, authorship, recency or certainty of data.In this paper, we present an original, generic, formalized and implemented approach for managing many dimensions of meta knowledge, like source, authorship, certainty and others. The approach re-uses existing RDF modeling possibilities in order to represent meta knowledge. Then, it extends SPARQL query processing in such a way that given a SPARQL query for data, one may request meta knowledge without modifying the query proper. Thus, our approach achieves highly flexible and automatically coordinated querying for data and meta knowledge, while completely separating the two areas of concern.     

KGDB:统一模型和语言的知识图谱数据库管理系统

知识图谱是人工智能的重要基石,其目前主要有RDF图和属性图两种数据模型,在这两种数据模型之上有数种查询语言.RDF图上的查询语言为SPARQL,属性图上的查询语言主要为Cypher.10年来,各个社区开发了分别针对RDF图和属性图的不同数据管理方法,不统一的数据模型和查询语言限制了知识图谱的更广泛应用.KGDB(kno...     

KGDB: Knowledge Graph Database System with Unified Model and Query Language

Knowledge graph is an important cornerstone of artificial intelligence, which currently has two main data models: RDF graphs and property graphs. There are several query languages on these two data models, including SPARQL on RDF graphs and Cypher on property graphs. Over the last decade, various communities have developed different data management methods for RDF graphs and property graphs. Inconsistent data models and query languages hinder the wider application of knowledge graphs. In this paper, we propose a knowledge graphy database (KGDB) system with unified data model and query language. (1) We work out a unified storage scheme based on the relational model that supports the efficient storage of RDF graphs and property graphs, catering to the smooth storage and query of knowledge graph data. (2) The characteristic set-based clustering is used in KGDB for the storage of typeless entities. (3) It realizes the interoperability of SPARQL and Cypher by enabling them to operate on the same knowledge graph. Extensive experiments on real-world datasets and synthetic datasets reveal that KGDB is more efficient than existing knowledge graph database management systems in storage management and query efficiency. KGDB saves 30% of the storage space on average compared with gStore and Neo4j. In addition, KDGB is two orders of magnitude faster than gStore and Neo4j in the query of the real-world datasets, seen from experiments on the query of basic graph pattern matching.     

On the primitivity of operators in SPARQL

The paper studies the primitivity of the basic operators UNION, AND, OPTIONAL, FILTER, and SELECT, as they are used in the SPARQL query language. The question of whether one operator can be expressed in terms of the other operators is answered in detail. It turns out that only AND is non-primitive. These results are shown to be insensitive to the choice of semantics for filter conditions (three-valued or two-valued). It is also shown that these two semantics can simulate each other.     

A Kalman filter-based R2R control system with parallel stochastic disturbance models for semiconductor manufacturing processes

A Kalman filter-based run-to-run control system has been proposed for minimum variance control of semiconductor manufacturing process. In the proposed control system, both gain- and bias-varying process models combined with different stochastic disturbance models were considered and identified in parallel. The best-fit model is selected and used for the R2R controller design. Sub-models of the ARIMA(1,1,1) process were considered for stochastic modeling of the bias and gain variation, and the Kalman filters are used to find the optimum model parameter estimation. The control performance was analyzed for each case of the disturbance model to investigate the expected benefit from the control system in comparison with the EWMA filter-based controller.     

J2EE项目中数据访问策略的选择

本文介绍了目前J2EE项目数据访问策略的选择，其中重点描述了O／R映射这种数据访问策略的特点及其适用的最佳条件，它可以帮助我们在项目的开发阶段通过清晰的映射方案构造出高效率的DAO层，为项目的成功打下良好的基础，特别是对于项目的式样变更以及后期维护．这种数据访问策略提供了最大程度上的灵活性。     

欠驱动两关节平面机械手的控制

欠驱动平面机械手是带有非完整约束的高度非线性系统,对其进行有效的控制仍然是个难点热点问题。针对最具代表性的两关节情形,给出了欠驱动两关节平面机械手的动力学方程,据此分析了该系统的可积性、线性化、稳定性、可控性和可反馈镇定性。根据控制目标的不同,将控制任务分为镇定到流形、镇定到单个平衡点和跟踪时变信号3种。针对这3种控制任务,分别回顾了各种已有的控制方式,仔细分析了它们的优点和有待改进的地方。最后探索了欠驱动平面机械手的研究中需要解决的几个关键问题,指出未来的可能研究方向。     

"龙腾R2"微处理器精确中断优化实现

介绍了"龙腾R2"微处理器精确中断的实现方法,详细讨论了备份缓冲区精确中断优化方法和中断指令缓冲区中断响应机制.在"龙腾R2"微处理器上的实验结果表明,采用备份缓冲区和中断指令缓冲区的精确中断方法在不影响微处理器速度的情况下,中断响应速度是原来的3.5倍,中断返回速度是原来的2.6倍.     

基于SAPR／3系统的ABAP语言OpenSQL应用

简要介绍了SAPR／3系统以及ABAP语言,从系统的架构出发,对相关模块进行具体解释。并用实际的程序例子说明ABAP语言中OPENSQL子集在此系统的应用特点。