知识库中的空值探讨

分析了空值环境下的三种类型的查询策略,以及Datalog查询求值的Semi-Naive算法,给出了一个从子目标关系空值特性导出头关系空值特性的一种方法,使改进后的Semi-Naive算法能在带空值的EDB数据库中对Datalog查询进行正确求值.     

面向对象数据库的推理查询语言*

本文基于复旦大学开发的一个面向对象数据库系统FOOD，提出一种推理查询语言O—Datalog．该语言能方便地表达对面向对象数据的各种查询和推理要求；它可以转换成类Datalog形式，能运用各种高效计值算法，比其它一些基于非Horn子句逻辑的语言更易于实现．O—Datalog在形式上是一种Datalog的扩充，本文着重介绍其语法和语义．     

含有空值关系数据库的查询处理

本文在深刻理解空值语义的基础上，给出一种处理占位型空值的方法，空值环境下关系数据库的查询策略，定义了含三种查询操作的关系代数最小完备集中的关系代数运算，并对查询计算的有效性和完备性进行了分析。     

面向对象数据库的推理查询实现*

上文介绍了面向对象数据库系统FOOD的推理查询语言O—Datalog，本文继续讨论对O—Datalog程序的几种变换，并证明这些变换是语义等价的，从而证明了对于一个O—Datalog程序，可以为它构造一个相应的Datalog程序。并能利用该Datalog程序对原程序进行计值．最后本文还给出了对O—Datalog程序计值的算法．     

关系数据库不可用空值的查询与处理

现有的基于关系数据模型的商业数据库采用空值对缺失信息进行建模与处理,然而,单一的空值解释无法体现空值本身的丰富语义。事实上,在相关研究中空值通常被解释为‘值未知’,‘值不可用’以及‘值不存在’等。文中主要研究不可用空值的查询与处理。通过仔细地观察和深刻地理解,分别在传统关系数据库查询和模糊数据库查询中讨论不同语义背景和查询条件下不可用空值的处理和分类。此外,还针对涉及不可用空值的传统关系数据库查询提出选择运算和差运算算法,这些算法使文中的研究更具实用性。     

空值环境下关系数据库查询处理方法

本文给出了一种处理占位型空值的简化方法，解决了空值环境下关系数据库的查询问题，针对不同的空值语义语义特点和查询中的作用，定义了三种不同的操作。ＤＥＦＩＮＩＴＥ，ＥＸＩＳＴ，ＭＡＹＢＥ。同时，给出了含有这三种操作的选择运算、集合差、一般连接运算的新定义。     

基于部分求值和热踪编译的Twig查询优化方法

XML树模式查询又称为Twig查询,是XML查询处理中最核心的操作。在Twig查询算法的研究中,TreeMatch算法由于极大程度上减少了中间结果的产生,被认为是最好的Twig查询算法之一。然而,在TreeMatch算法的核心操作getNext中,存在不少仅依赖Twig模式的计算。当getNext调用次数很多时,这种冗余的重复计算会影响TreeMatch算法的性能。为了进一步改进该算法,提出了一种基于部分求值和热踪编译的Twig查询优化方法,该方法以Twig模式作为不变量进行部分求值,把查询请求翻译成一种Twig查询机指令序列,避免了查询过程中对Twig模式的重复计算;并且针对这种查询机指令序列的解释过程,利用热踪编译技术进行了优化。对比实验说明基于部分求值和热踪编译的优化方法能够将Twig查询效率提高到20%到60%。     

基于多核CPU的无锁并行Semi-naive算法

Datalog系统被广泛应用于很多领域，如图数据库、网络和静态程序分析等。在处理海量数据时，基于串行的Datalog求解策略无法充分发挥现有多核处理器的计算性能。针对上述问题，提出一种基于多核CPU的无锁并行Semi-naive算法(Parallel Semi-naive, PSN)用于支持Datalog的高效求解。PSN使用B⁺树索引进行数据划分，将数据分配给不同的线程执行计算，每个分区产生的中间结果元组互不相同，有利于实现计算时无锁的并行。同时提出一种双层哈希表结构来索引中间结果以提高查重的效率，每个线程只在特定的区域执行相关的计算，无需使用锁来防止写冲突。PSN使用任务队列-线程池为空闲线程分配任务，来实现多线程的负载均衡。在KONECT(Koblenz Network Collection)及斯坦福SNAP(Stanford Network Analysis Platform)的公开数据集上的实验结果表明，PSN算法可以优化Datalog规则的查询性能。     

空值环境下含不确定及可能信息关系数据库的查询

本文以（１）中的扩展关系模型为基础在两种元组极的不完全信息－不确定及可能信息中引入属性级的不完全信息空值，使两种不同性质的不完全信息同时出现在同一关系中，为了能够查询到不同种类及不同确定程度的信息，文中制定了这种扩展关系模型上关系的查询策略，定义了能够体现这种策略的最小关系代数运算。     

基于空值环境下扩展关系模型的查询处理研究

由于空值的出现，使数据库更新操作更趋势复杂。为适应更新要求，建立了扩展关系模型。本文正是基于这种模型进行对查询处理的讨论，给出了相应的查询策略及实现过程。     

一类递归查询问题的快速求解算法

提出一个求解一类扩充递归Ｄａｔａｌｏｇ逻辑程序的算法,论证其正确性,并讨论了算法的复杂性。该算法结合了自底向上和自顶向下的逻辑程序求解算法的优点,但比魔集算法简单,易于实现。利用宁可以解决工程数据管理中常遇到的产品零部件装配关系的递归查询问题。     

What you always wanted to know about Datalog (and never dared toask)

Datalog, a database query language based on the logic programming paradigm, is described. The syntax and semantics of Datalog and its use for querying a relational database are presented. Optimization methods for achieving efficient evaluations of Datalog queries are classified, and the most relevant methods are presented. Various improvements of Datalog currently under study are discussed, and what is still needed in order to extend Datalog's applicability to the solution of real-life problems is indicated     

Decidable containment of recursive queries

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.     

知识库系统KBASE＋的数据模型,语言及实现

本文讨论具有面向对象特征的知识库系统ＫＢＡＳＥ＋的数据模型，语言及实现，ＫＢＡＳＥ＋的数据模型可以方便地支持对象标识，类层次，多继承等面向对象概念。描述性查询语言ＫＢＬ是扩充的ＤＡＴＡＬＯＧ。本文重构了ＫＢＬ语义理论框架，提出了解决属性继承和实例继承的方案，说明了ＫＢＬ程序可以转换成语义等价的ＤＡＴＡＬＯＧ程序。     

具有面向对象特征的知识库系统

本文讨论了具有面向对象特征的知识库系统KBASE~ 的数据模型、语言及实现。KBASE~ 的数据模型可以方便地支持对象标识、类层次、多继承等面向对象概念。描述性查询语言KBL是DATALOG针对于非一范式关系模型的扩充。本文重构了KBL的语义理论框架,提出了通过计算相关类的下确界来解决属性继承中的冲突问题,通过在KBL程序中添加规则来实现实例继承的方案,本文说明了KBL程序可以转换成语义等价的DATALOG程序,描述了这种转换的基本思想,探索了知识库和面向对象数据库有机结合的可行途径。     

演绎数据库中语义查询的动态优化算法

演绎数据库的语义查询优化是利用数据库中的完整性约束，将用户提交的查询转换为与原查询等价且执行效率更高的查询规则。该文提出的动态语义优化算法在查询计算过程中动态约去存在的空展开式，使得查询时间开销的节省可用所除去的空展开式规模大小衡量，较适用于含有大量空展开式的演绎数据库。     

How expressive is stratified aggregation?

We present results on the expressive power of various deductive database languages extended with stratified aggregation. We show that (1) Datalog extended with stratified aggregation cannot express a query to count the number of paths between every pair of nodes in an acyclic graph, (2) Datalog extended with stratified aggregation and arithmetic on integers (the + operator) can express allcomputable queries on ordered domains, and (3) Datalog extended with stratified aggregation and generic function symbols can express allcomputable queries (on ordered or unordered domains). Note that without stratified aggregation, the above extensions of Datalog cannot express all computable queries. We show that replacing stratified aggregation by stratified negation preserves expressiveness. We identify subclasses of the above languages that are complete (can express all, and only the, computable queries).     

Nonrecursive incremental evaluation of Datalog queries

We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process incremental query evaluation using conjunctive queries. After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called Cartesian-closed increment property, and to the case of unbounded-set insertions where the sets are binary Cartesian products. Finally, we show that the class of conjunctive queries with the Cartesian-closed increment property is decidable.Parts of the results in this paper appeared as extended abstracts in theProceedings of the 1992 International Conference on Database Theory (LNCS 646, Springer-Verlag), and in theProceedings of the 1993 International Workshop on Database Programming Languages (Workshops in Computing, Springer-Verlag).Guozhu Dong gratefully acknowledges support of the Australian Research Council through research grants, and the Centre for Intelligen Decision Systems.Work by Jianwen Su was supported in part by NSF Grants IRI-9109520 and IRI-9117094.     

Materialisation and data partitioning algorithms for distributed RDF systems

Many RDF systems support reasoning with Datalog rules via materialisation, where all conclusions of RDF data and the rules are precomputed and explicitly stored in a preprocessing step. As the amount of RDF data used in applications keeps increasing, processing large datasets often requires distributing the data in a cluster of shared-nothing servers. While numerous distributed query answering techniques are known, distributed materialisation is less well understood. In this paper, we present several techniques that facilitate scalable materialisation in distributed RDF systems. First, we present a new distributed materialisation algorithm that aims to minimise communication and synchronisation in the cluster. Second, we present two new algorithms for partitioning RDF data, both of which aim to produce tightly connected partitions, but without loading complete datasets into memory. We evaluate our materialisation algorithm against two state-of-the-art distributed Datalog systems and show that our technique offers competitive performance, particularly when the rules are complex. Moreover, we analyse in depth the effects of data partitioning on reasoning performance and show that our techniques offer performance comparable or superior to the state of the art min-cut partitioning, but computing the partitions requires considerably less time and memory.