模糊描述逻辑f-DLR-Lite∩的合取查询回答

分析了描述逻辑合取查询回答的研究现状及存在的不足,在描述逻辑DL-Lite和模糊集理论的基础上,提出了一种可表示和处理n元关系,并允许在包含公理左侧出现概念合取的新的模糊描述逻辑f-DLR-Lite∩,并给出其语法和语义及知识库的形式.提出了一种兼容查询阈值和用户指定权重的模糊查询语言,给出了利用这种语言在f-DLR-Lite∩知识库上进行合取查询的具体步骤和算法,并进行了算法时间复杂度分析,讨论了该合取查询过程的一阶逻辑可归约性.f-DLR-Lite∩弥补了经典描述逻辑在知识表示和推理上的不足,扩展后的查询语言对用户查询意图的表达更加精确合理.

含有合取查询的时态描述逻辑ALC-LTL模型检测

时态描述逻辑ALC-LTL在命题线性时态逻辑LTL中引入了描述逻辑ALC的刻画能力,可以对语义Web环境下动态系统的时序特征进行刻画。该文在ALC-LTL中进一步引入合取查询,增强ALC-LTL公式的描述能力,并在此基础上给出了含有合取查询的时态描述逻辑模型检测算法。模型检测算法由3个步骤组成:首先,根据时态规范中涉及的合取查询从描述逻辑的角度在系统状态中进行推理和检索,求出满足合取查询的所有实例;其次,将这些实例映射为命题并带入时态规范中,将含有合取查询的ALC-LTL模型检测问题转换为命题LTL的模型检测问题;最后调用LTL的模型检测算法完成规范验证。该工作从描述逻辑的角度对传统的命题线性时态逻辑的模型检测问题进行了扩展,适合于在语义Web环境下对语义Web等动态系统的时态性质进行刻画和验证。

非稠密数据域的不等式合取查询

1988年Klug给出了第一个稠密域上的不等式合取查询包含问题的算法,但该方法不适用于非稠密域.本文解决非稠密域上的不等式合取查询的包含问题.

不等式合取查询包含问题的研究

查询包含问题是数据库查询处理和优化中的基本问题,集语义下的合取查询包含问题是NP-complete问题,但在实际的数据库系统中,查询通常是在包语义下求值的。近十年来包语义下的合取查询包含问题已经成为一个公共问题,这个问题是否是可判定的还不清楚。本文主要研究包语义下的不等式合取查询包含问题,在包语义下的一类特殊数据库上的不等式合取查询包含问题是不可判定的。

数据库语义合取查询研究

针对异质、异构数据库的语义集成中,对海量元组进行语义查询时因效率问题而无法使用丰富的语义表达能力的问题,提出一种兼顾速度和语义表达能力的算法,将语义查询和本体都进行图形化表示,并实现子图的语义匹配,将匹配的结果转化成数据库查询语句。与将语义查询直接重写为SQL的算法相比,该算法能支持更丰富的语义。

模糊描述逻辑知识库查询蕴涵的判定方法

大规模领域本体的快速发展对语义Web领域的数据访问提出了更高的要求,而基本的本体推理服务已不能满足数据密集型应用中处理复杂查询(主要是合取查询)的迫切需要.为此,大量的研究工作集中在本体和描述逻辑知识库合取查询算法的设计实现上,并开发出了很多知识库存储和查询的实用工具.近来模糊本体和模糊描述逻辑的研究,特别是它们在处理语义Web中模糊信息方面,得到了广泛关注.文中重点研究了模糊#0这一族极富表达能力的描述逻辑知识库的合取查询问题,提出了相应的基于推演表的算法,证明了算法对于f-#0123的真子逻辑的可靠性、完备性和可终止性.证明了算法对于f-#0123是可靠的,并分析了导致算法不可终止的原因.对于该问题的数据复杂度,证明了当查询中不存在传递角色时其严格的CONP上限.对于联合复杂度,证明了算法关于知识库和查询大小的CO3NEXPTIME时间复杂度上限.

不一致数据上查询结果的一致性估计

主键约束是描述关系数据一致性的常用方法,基于主键约束的数据一致性修复返回一个极大子集,子集中不同数据的主键不同.对于合取查询Q,一致性合取查询返回一个答案集合,答案集合是Q在数据集合I的每一个修复下查询结果的交集.文中将Q在I中的查询结果满足一致性的个数占总的结果个数的比例定义为查询结果的一致性程度.若Q不可一阶表达且不能在多项式时间内得到其一致性解,则当Q答案个数超过30时,使用抽样的方法给答案集合一致性程度的一个(ε,δ)-估计.由于布尔合取查询的一致性判定问题是coNP-完全问题,因此在估计过程中,使用攻击图,通过攻击图对布尔查询q进行改写近似判断q近似一致性回答.实验表明了估计算法和近似判定算法具有较高的效率和准确率.

面向语义的精简化多关系频繁模式发现方法

多关系频繁模式发现能够直接从复杂结构化数据中发现涉及多个关系的复杂频繁模式,避免了传统方法的局限。有别于主流基于归纳逻辑程序设计技术的方法,提出了基于合取查询包含关系的面向语义的精简化多关系频繁模式发现方法,具有理论与技术基础的新颖性,解决了两种语义冗余问题。实验表明,该方法在可理解性、功能、效率以及可扩展性方面具有优势。

一种新的DL-Lite不一致容忍语义

在本体工程中,处于演变过程中的本体常出现不一致性问题,这将导致基于本体的推理失效.为解决推理失效的问题,提出了一种新的处理DL-Lite本体实例断言中冲突的不一致容忍语义,讨论了新的不一致容忍语义与已有的不一致容忍语义的关系,给出了在新定义的不一致容忍语义下的修复算法并做了新语义下推理任务的复杂度分析.

知识库和演绎数据库的最新进展

一、引言知识库和演绎数据库是近几年数据库界研究的热门课题,其研究正方兴未艾。八十年代中期,LDL 语言和 DATALOG 语言的推出标志着一个研究热潮的到来。从1990年召开的几个国际会议可以看出,这股潮流还在持续高涨。VLDB’90(笫十六届超大型数据库国际会议)上有三个关于演绎数据库的报告专题和一个关于知识库的报告专题。PODS’90(第九届 ACM 数据库系统原理研讨会)的十一个报告专题中竟有六个是直接与知识库和演绎数据库有关的。从会议录用的论文数来看,VLDB’90共60篇中有10篇;