网络编程逻辑抽象

近年来，无线通信技术的渗透和微型嵌入式计算设备的增加加速了泛在环境的发展。现在，泛在网络开发的一个基本障碍是缺乏编程抽象。本文围绕这一前沿领域，研究网络编程逻辑抽象。主要结果有： 1.研究了定义网络全局性质的递归查询的分布式计算。一阶逻辑及不动点逻辑可以抽象地描述网络全局性质，本文阐明它们的计算可以充分且有效地分布在网络上，并且具有合理的复杂度上限。本文证明在有限度的同步网络上，一阶逻辑查询的分布式计算具有对数的节点内计算复杂度和消息长度、线性的分布式计算复杂度以及多项式的单节点消息复杂度上界。不动点查询的分布式计算具有类似的复杂度，只是它具有多项式的分布式计算复杂度。 2. 研究了定义网络节点的本地行为的网络声明式语言。本文规定了递归的规则语言Netlog的语法。Netlog被用来声明式地描述网络环境下的分布式计算，特别是通讯协议和P2P系统等。Netlog语言以Datalog语言为基础，囊括了尽可能完备的网络应用所需要的原语，包括通讯原语、聚合函数、时效声明、间歇性触发、数据更新以及非确定性选择操作。本文定义了Netlog语言的分布式不动点语义，不仅定义了节点内的计算，而且明确的纳入了节点间的通信，解决了声明式网络语义不确定的问题。同时，本文定义了良好的Netlog程序和强良好的Netlog程序，并证明当良好的程序在同步系统上计算，或者强良好的程序在异步系统上计算，它们在三种复杂度衡量标准，即分布式计算复杂度、单节点消息复杂度和节点单回合计算复杂度下都具有多项式的上限。另外，还证明了强良好的程序的计算结果不受网络有限个数的消息丢失的影响。 Netquest小组开发了Netquest系统以支持Netlog语言并实现其分布式不动点语义。Netquest系统依赖于网络节点上的嵌入式DBMS，这不仅简化了系统的开发，也增强了它在多机种的网络上的可移植性，并且支持数据密集型的应用。此外，Netlog编译器还具备优化模块，可以进一步减轻开发者的负担。一些用Netlog程序编写的经典的分布式算法和网络应用程序已经在网络模拟平台和包含多种计算设备的平台上进行了实验。 3. 进一步考虑了以上两种层面的网络编程逻辑抽象语言的纵向编译。本文阐述了如何将在全局层面表达网络性质的一阶逻辑及不动点查询翻译为在本地层面描述节点行为的Netlog程序。本文设计了普适性的算法，将集中式的Datalog否定程序翻译为分布式的Netlog程序；再加上将一阶逻辑及不动点逻辑翻译为Datalog否定语言的经典结果，从而完成了纵向编译。 4.定义了以上两种网络编程逻辑抽象语言的片段，包括局部的一阶逻辑及不动点查询、节俭的以及强节俭的Netlog程序。它们在表达能力和分布式计算复杂度之间有良好的折中。它们尽可能地保留了分布式计算的局部特性，在定义网络功能上具有丰富的表达能力，并且具有更加紧致的复杂度上限，即具有常数的或者二次的消息复杂度、线性的或者二次的分布式计算复杂度和常数的节点单回合计算复杂度。

语义Web中描述逻辑本体的可伸缩推理和非一致处理

随着Web信息的与日俱增，使用机器处理这种信息成为一种必然的趋势。语义Web应运而生，成为当前研究的热点之一。它以本体为核心，为不同领域提供共享的词汇，以便机器处理Web信息。表达本体的标准语言OWL以描述逻辑为基础。OWL本体的推理可伸缩性差，难以适应规模较大的本体应用，因此推理可伸缩性问题是一个重要的实际问题。此外，OWL本体是一个逻辑系统，在生成、维护和集成等过程中，都很容易出现非一致现象，导致标准的推理机制不能正常运作。因此本体非一致问题是另一个重要的实际问题。针对上述两个实际问题，本文分别在实现可伸缩推理、修复非一致本体、以及进行非一致容忍推理三个方面提出了解决办法。 [可伸缩推理方面] 本文提出了一种本体断言公理集的划分方法，使本体推理能够在独立的划分子集中进行，以此提高本体推理的可伸缩性。 [本体修复方面] 本文提出了一种计算具有最小删除代价的本体子集的方法；通过删除这种本体子集，可以恢复本体的一致性。该方法将计算上述本体子集的问题归约为在命题逻辑程序中计算某种最优模型的问题，以调用现有的可满足性问题求解器来解决。 [非一致容忍推理方面] 本文将命题逻辑中字典序推理方法应用到描述逻辑中，以提供针对非一致本体的查询机制。本文还提出了一种在描述逻辑本体中进行字典序推理的方法。该方法将字典序结论的判定问题归约为命题可满足性判定问题，以调用现有的可满足性问题求解器来解决。