（计算机软件与理论专业论文）无线网络的声明性方法研究.pdf

摘要 摘要 近年来，无线通讯技术迅速发展，无线应用已遍布人类社会各个角落。无 线a dh o c 网络是无线通讯领域的研究热点之一。无线a dn o c 网络具有组网快 捷、灵活、且不受有线网络约束等优点，在军事、交通、个人通讯等方面应用 广泛。基于无线通讯技术的新应用入雨后春笋般出现。 声明性网络是一种应用演绎数据库技术描述并解决网络问题的方法。它将 网络封装成数据库的一部分，使用逻辑声明性语言描述网络组织等问题，使用 数据库技术处理声明性语言程序。然而，目前正在研究的声明性网络使用的语 言都是d a t a l o g 的子集，它的不动点语义是基于单调增的，这与a dh o c 网络上 数据的动态变化是相矛盾的。为了解决这一问题，本文在8 0 年代数据库领域的 演绎性语言基础上，提出了一个新的描述语言n e t l o g ，它使用描述性方式表达 协议，非常适合a dh o a 网络环境下的分布式查询处理。 无线a dh o c 网络路由组织以及无线传感器网络的数据组织与处理是无线网 络的重要应用。本文使用声明性方法对这些领域作了系统的研究。本文在声明 性网络方面的工作与贡献如下： 首先，针对于其它声明性语言的单调性语义与网络数据动态变化的矛盾， 提出了非单调的声明性语言n e t l o g ，并对n e t l o g 的描述能力以及不动点语义 方面的问题进行了分析与证明。主要研究工作包括： 1 ) 定义了n e t l o g 的语法定义和语义解释。通过对否定与删除符号的语法 定义与语义解释，使得n e t l o g 可以描述网络数据的动态变化。 2 ) 证明了n e t l o g 的描述能力与f o + p f p 一致。 3 ) 给出了n e t l o g 语言部分不动点存在的充分条件。 其次，本文对无线a dh o c 网络的路由组织进行了研究。自适应性是a dh o c 路由组织的一个重要的研究方向，由于声明性网络不同于传统的网络协议：不 同的声明性网络协议可以协同合作；本文提出了自适应的基于组件的组合路由 协议。主要工作包括： 1 ) 在模拟平台上实现了使用声明性网络方法描述的传统a dh o c 路由协议 d s d v 、d s r 、o l 豫、a o d v 等。 2 ) 提出并在模拟平台上实现了基于组件的组合路由协议。将声明性a dh o c 协议看作由多个模块构成，通过对模块的替换可以完成不同协议的替 换；并且通过对粗糙集理论的信息表的处理实现了多个声明性协议间 的自适应。 3 ) 在模拟平台上实现了一个简单的a dt t o c 网络的文件p 2 p 系统。 最后，本文对无线传感器网络的数据管理与路由组织进行了研究。主要工 摘要 作包括： 1 ) 在模拟平台上实现了无线传感器网络的树形，骨干网以及聚簇等数据 组织网络。 2 ) 在模拟平台上实现了分布式的带链接代价的最小生成树协议。 3 ) 在模拟平台上实现了分布式的带链接代价的近似最小s t e i n e r 树协议。 4 ) 在模拟平台上实现了简单的数据查询与融合协议。 关键词：声明性网络声明性语言分布式查询处理器无线自组织网络路 由协议自适应自组织粗糙集理论信息表无线传感器网络 a b s t r a c t a bs t r a c t r e c e n t l yt h e r eh a sb e e na l le x p l o s i v eg r o w t hb o t hi nt h en u m b e ro fm o b i l e c o m p u t i n gd e v i c e sa n dw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e s w i r e l e s sa dh o c n e t w o r ki sb e c o m i n gm o r ea n dm o r ew i d e l yu s e di nt h ea s p e c t so fm i l i t a r y , t r a f f i c ， p e r s o n a lc o m m u n i c a t i o na n d s oo n i ti so n ei n d i s p e n s a b l ep a r to ft h eh u m a ns o c i e t y b e c a u s eo ft h ed y n a m i cc h a r a c t e r i s t i e so ft h ew i r e l e s sa dh o cn e t w o r k s ，t h eq u e r y p r o c e s s i n gt e c h n o l o g i e si n t r a d i t i o n a ld i s t r i b u t e dd a t a b a s ea r en o tu s e f u li nt h e e n v i r o n m e n t t h eu s eo fq u e r yl a n g u a g e sw a sp r o p o s e dt oe x p r e s sn e t w o r kc o m m u n i c a t i o n a l g o r i t h m ss u c ha sr o u t i n gp r o t o c o l sa n d d e c l a r a t i v eo v e r l a y s t h i sa p p r o a c h ，k n o w n a sd e c l a r a t i v en e t w o r k i n g , i se x t r e m e l yp r o m i s i n gt oe a s et h ed e v e l o p m e n ta n dt h e d e p l o y m e n to fn e t w o r k i n gp r o t o c o l sa n de n s u r ee f f i c i e n tc o m m u n i c a t i o ni n t h e n e t w o r k t h ed e c l a r a t i v ep r o g r a m sc a na l s ob eo p t i m i z e du s i n gd a t a b a s et e c h n i q u e s h o w e v e r , t h ed e c l a r a t i v el a n g u a g e si nu s ea r ea nm o n o t o n i ci ns e m a n t i c s w h i c hc a n n o tu s et os p e c i f yt h ed y n a m i cd a t ap r o c e s si nn e t w o r k i no r d e rt os o l v et h ep r o b l e m ， w ep r e s e n tan e wd e c l a r a t i v el a n g u a g ed e r i v e df r o mt h ed e d u c t i v el a n g u a g eo fl a s t 8 0 s ，w h i c hi sf i tf o rt h es p e c i f i c a t i o n so fm o b i l ea dh o en e t w o r k sp r o t o c o l sa n d d i s t r i b u t e dq u e r yp r o c e s s t h en e t w o r ko r g a n i z a t i o ni nw i r e l e s sa dh o en e t w o r k sa n dd a t aq u e r yp r o c e s s i nw i r e l e s ss e n s o rn e t w o r k sb o t ha r ei m p o r t a n ta p p l i c a t i o n so fw i r e l e s sn e t w o r k s i n t h i sp a p e r , w er e s e a r c ht h ed e c l a r a t i v en e t w o r k i n gi nt h e s ef i e l d s t h em a i n c o n t r i b u t i o n so fo u rw o r ki n c l u d et h ef o l l o w i n ga s p e c t s ： f i r s t ，w ep r e s e n tan e w d e c l a r a t i v el a n g u a g e ，n e t l o g , w h i c hi sn o n - m o n o t o n i c i ns e m a n t i c s ，a n dw ep r o v e di t se x p r e s s i o n sa n dt h ee x i s t e n c eo fp a r t i a lf i x p o i n t d e c l a r a t i v ep r o g r a m s t h em a i nw o r k si n c l u d e ： 1 ) w ed e f i n et h es y n t a xa n ds e m a n t i c so f 各l e t l o g t h r o u g ht h ed e f i n i t i o no f n e g a t i o no p e r a t o ra n dc o n s u m p t i o no p e r a t i o n ，n e t l o gc a ns p e c i f yt h e d y n a m i cd a t ap r o c e s so f w i r e l e s sn e t w o r k s 2 ) w ep r o v e dt h a tt h ee x p r e s s i o no fn e t l o gi se q u a lt of o + p f p 3 ) w eg i v eas u f f i c i e n tc o n d i t i o no ft h ee x i s t e n c eo fp a r t i a lf i x p o i n t o f d e c l a r a t i v ep r o g r a m s e c o n d ，w er e s e a r c ht h en e t w o r ko r g a n i z a t i o no fw i r e l e s sa dh o cn e t w o r k s i i a b s 仃a c t a d a p t a t i o ni sa ni m p o r t a n tr e s e a r c ha p p l i c a t i o no fr o u t i n gp r o t o c o l s t h ed e c l a r a t i v e p r o t o c o l sa l ed i f f e r e n tw i t ht h et r a d i t i o no n e sw h oc a n n o tc o m m u n i c a r ee a c ho t h e r w e p r e s e n ta na d a p t i v ec o m p o s i t i o np r o t o c o lb a s e d o nc o m p o n e n t ，i nw h i c hw eu s e i n f o r m a t i o nt a b l eo fr o u g hs e tt h e o r yt os o l v et h ea d a p t a t i o no fd i f f e r e n tp r o t o c o l s t h em a i nw o r k si n c l u d e ： 1 ) w e r e a l i z e dt h et r a d i t i o n a lr o u t i n gp r o t o c o l si nm o b i l ea dh o cn e t w o r k si n s i m u l a t i o np l a t f o r m ，s u c ha sd s d v , d s r ，o l s r ，a o d v 2 ) w ep r e s e n tt h ea d a p t i v ec o m p o s i t i o np r o t o c o lb a s e d o nc o m p o n e n tw h i c h i sc o m p o s e db yd e c l a r a t i v em o d u l e s w ec a ns w i t c ho n ep r o t o c o lt oa n t h e r b yr e p l a c i n gm o d u l e s ，a n dw ec a n s e l e c tap r o p e rp r o t o c o lb yo p e r a t i n gt h e i n f o r m a t i o nt a b l e 3 ) w er e a l i z e ds i m p l ep 2 pi n f o r m a t i o ns y s t e mo fm a n e t i ns i m u l a t i o n p l a t f o r m l a s t ，w er e s e a r c ht h eq u e r yp r o c e s so fw i r e l e s ss e n s o rn e t w o r k s t h em a i n w o r k si n c l u d e ： 1 ) w e r e a l i z e dt h en e t w o r ko r g a n i z a t i o no fw s n e ti ns i m u l a t i o np l a t f o r m ， s u c ha st r e e ，b a c k b o n ea n dd u s t e r 2 ) w er e a l i z e dt h ed i s t r i b u t e dm i n i m a ls p a n n i n gt r e ep r o t o c o lo fw e i g h t e d w s n e ti ns i m u l a t i o np l a t f o r m 3 ) w e r e a l i z e dt h ed i s t r i b u t e da p p r o x i m a t i v em i n i m a ls t e i n e rt r e ep r o t o c o lo f w e i g h t e dw s n e t i ns i m u l a t i o np l a t f o r m 4 ) w er e a l i z e dt h es i m p l ed a t aq u e r ya n dd a t aa g g r e g a t i o np r o t o c o l so f w s n e ti ns i m u l a t i o np l a t f o r m k e yw o r d s ：d e c l a r a t i v en e t w o r k i n g ，d e c l a r a t i v el a n g u a g e ，d i s t r i b u t e dq u e r y e n g i n e ，w i r e l e s sa dh o cn e t w o r k ，r o u t i n gp r o t o c o l ，a d a p t a t i o n ， s e l f - o r g a n i z a t i o n ，r o u g hs e tt h e o r y , i n f o r m a t i o nt a b l e ，w i r e l e s ss e n s o r n e t w o r k i i 中国科学技术大学学位论文原创性声明。 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： 、勿交获 签字同期：堡! ! ：竺! 致 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 曰么开口保密( 年) 作者签名： 、移交拭 签字r 期：丝坦：竺：丝 翩躲也 签字r 期：丝! 望二士：2 刍厶 第1 章绪论 1 1 研究背景介绍 第1 章绪论 无线a dh o e 网络( w i r e l e s sa dh o cn e t w o r kw a n e t ) 是近年来发展较快 的一种无线网络，又称自组织网络( s e l f o r g a n i z a t i o n ) 或者多跳网络 ( m u l t i - h o pn e t w o r k ) 。无线a dh o c 网络是一种逻辑意义上的组网方式，是在 不依赖基础网络设施的前提下，由一定范围内的移动终端动态的建立可以互联 的网络。网络中不存在网关，网桥等任何基础通讯设施。两个在通讯节点范围 外的节点进行通信时，需要其它中间节点的消息转发( 多跳) 。 a dh o c 网络具有下述主要特点： 1 无中心：a dh o c 网络是一个对等式网络，结点可以随时加入或离开网 络。 2 自组织：网络的布设或展开无需依赖于任何预设的网络设施。 3 多跳路由：当结点要与其覆盖范围之外的结点进行通信时，需要中间 结点的多跳转发。 4 动态拓扑： a dh o c 网络，节点位置可以改变。节点可以随时加入或离 开网络，从而使网络拓扑结构动态变化。 无线传感器网络( w i r e l e s ss e n s o rn e t w o r kw s n e t ) 是微电子技术、a dh o c 无线网络、分布式计算等信息技术发展和融合的产物。它利用低成本、低能耗、 可计算的无线传感器网络节点收集、处理用户感兴趣的监测对象的数据，并在 此基础上形成满足用户需求的高层应用。由于在军事、环境监测、医疗、农业、 采矿等领域有广阔的应用前景，引起了世界各国学术界和工业界的广泛重视， 成为近年来信息科学的一个研究热点。 人工智能与数据库技术结合的一个研究方向是可演绎系统。知识的最基本 操作就是演绎，具有演绎功能的系统称为可演绎系统。使得数据库系统具有演 绎功能的研究一直是数据库研究领域的重要研究方向和问题。 1 2 声明性语言与n e t o u e s t 系统 描述性查询语言已在网络环境下获得应用。现有的几种传感器网络，如 t i n y d b ( s a m u e l2 0 0 5 ) 和c o u g a r ( a l a n2 0 0 3 ) ，展示了在无线网络中使用s q l 进 行查询是可行的。这些系统提供了基于能量有效的数据分发及查询处理策略。 第1 章绪论 在给定已知网络全局知识和网络约束节点的计算能力的情况下，能集中式地计 算出子查询在网络上最优配置，基于传感器数据的空间和时序特征，可以使用 声明性方法来消除不可靠数据。描述性策略也适用于网络层应用。递归查询语 言最初是用于表达网络通讯，如路由协议和描述性重叠类。对描述性查询语言 的进一步研究，提出了一些d a t a l o g 的执行技术。分布式查询语言提供了表达 网络问题的新思路，如节点发现，路由发现，q o s 路经维护，拓扑发现( 包括物 理拓扑发现) 等。 目前正在研究的声明性网络使用的语言都是d a t a l o g 的子集，其不动点语 义是基于单调增的，这与a dh o c 网络上数据的动态变化是相矛盾的。为了解决 这一问题，本文在8 0 年代数据库领域的演绎性语言基础上，提出了一种新描述 语言n e t l o g ，它使用描述性方式表达协议，非常适合a dh o c 网络环境下的分 布式查询处理。使用这种语言描述的协议装载在每个节点本地数据库的 “p r o t o c o ls t o r e ”中， 因此不需要对混合路由器作任何修改，就可以从本地 数据库修改路由协议。 本文提出的n e t q u e s t 系统将网络处理阶逻辑和表达描述性网络协议的 能力综合在一起。它把网络隐藏起来，每个节点将整个网络看成一个“数据库”， 通过描述性的查询和“数据库 进行交互。 因此，网络节点之间的通讯由查 询和数据组成。每个节点都由一个本地数据库，混合路由器，分布式查询引擎 ( 处理所有的查询，包括来自本地的和来自网络其他节点的) 组成。以往的系 统将查询分散到不同网络节点上，但是这些节点并不处理查询，而是将数据传 回发出数据的查询节点( 后文以查询节点表述) 处理。本文提出的系统没有任何 集中式控制，它把查询和处理都完全分散到网络中不同节点上执行。这种方式 用统一模式处理传统的网络层和应用层，从而模糊了它们之间的区别。 1 3 无线a dh o c 网络 a dh o c 网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) 。在a dh o c 网 络中，结点具有报文转发能力，结点问的通信可能要经过多个中间结点的转发， 即经过多跳( m u l t i h o p ) ，这是a dh o c 网络与其他移动网络的最根本区别。结点 通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行。 因此它地被称为多跳无线网( m u l t i h o pw i r e l e s sn e t w o ”r k ) 、自组织网络 ( s e l f o r g a n i z e dn e t w o r k ) 或无固定设施的网络( i n f r a s t r u c t u r e l e s s n e t w o r k ) 。 1 4 无线传感器网络 2 第1 章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，简称w s n e t ) 与移动自组织 网络最为相似，但差异很大：w s n e t 节点不移动或很少移动，而m a n e t 节点移 动性强；w s n e t 的数据包更小，因而数据传输开销更大；w s n e t 节点的计算、存 储、通信能力更有限；w s n e t 节点因能量耗尽而易失效；w s n e t 节点通信高能耗， 数据计算低能耗，而这种差异在m a n e t 中并不重要：w s n e t 一般独立成网，主 要用于监测功能，是以数据为中心的网络，m a n e t 则能为分布式应用提供互联、 计算能力；w s n e t 节点可达上千，远大于m a n e t 的几十个节点；w s n e t 网络流量 具有m a n y - t o - o n e 和o n e - t o - m a n y 的特点；w s n e t 节点合作完成监测任务，与 应用高度相关，数据相关性较大；w s n e t 节点一般没有统一编址( 在某些应用中 可对节点编址) 。 1 5 研究内容与论文组织 本文对声明性网络进行了系统的研究。首先，针对于其它声明性语言的单 调性语义与网络数据动态变化的矛盾，提出了非单调的声明性语言n e t l o g ，并 对n e t l o g 的描述能力以及不动点语义方面的问题给出了证明。主要研究工作包 括： 4 ) 定义了n e t l o g 的语法定义和语义解释。通过对否定与删除符号的语法 定义与语义解释，使得n e t l o g 可以描述网络数据的动态变化。 5 ) 证明了n e t l o g 的描述能力与f o + p f p 一致。 6 ) 给出了n e t l o g 语言部分不动点存在的充分条件。 其次，本文对无线a dh o c 网络的路由组织进行了研究。自适应性是a dh o c 路由组织的一个重要的研究方向，由于声明性网络不同于传统的网络协议：不 同的声明性网络协议可以协同合作；本文提出了自适应的基于组件的组合路由 协议。主要工作包括： 4 ) 在模拟平台上实现了使用声明性网络方法描述的传统a dh o c 路由协议 d s d v 、d s r 、o l s r 、a o d v 等。 5 ) 提出并在模拟平台上实现了基于组件的组合路由协议。将声明性a dh o c 协议看作由多个模块构成，通过对模块的替换可以完成不同协议的替 - 换；并且通过对粗糙集理论的信息表的处理实现了多个声明性协议间 的自适应。 6 ) 实现了一个简单的a dh o c 网络的文件p 2 p 系统。 最后，本文对无线传感器网络的数据管理与路由组织进行了研究。主要工 作包括： 5 ) 在模拟平台上实现了无线传感器网络的树形、骨干网以及聚簇等数据 组织网络。 3 第1 章绪论 6 ) 在模拟平台上实现了分布式的带链接代价的最小生成树协议。 7 ) 在模拟平台上实现了分布式的带链接代价的近似最小s t e i n e r 树协议。 8 ) 在模拟平台上实现了简单的数据查询与融合协议。 本文的主要内容分为五章，其中第二章引入n e t l o g 的语法与语义；第三章 介绍n e t q u e s t 系统结构与功能；第四章介绍无线a dh o c 网络路由组织，传统 的a dh o c 路由协议的声明性方法实现，自适应基于组件的组合路由协议和a d h o cp 2 p 文件共享系统；第五章介绍无线传感器网络，分布式的最小生成树协 议，骨干网协议，最小s t e i n e r 树协议以及数据查询与融合协议。 最后一章对全文进行总结，并对未来的研究工作进行展望。 4 第2 章逻辑程序设计语言n e t l o g 介绍 第2 章逻辑程序设计语言n e t l o g 介绍 2 1d a t aio g 语言介绍 可演绎系统是结合了人工智能与数据库技术的一个研究方向。演绎是对知 识的最基本操作之一，具有演绎功能的系统称为可演绎系统( 李磊1 9 9 3 ) 。使 数据库系统具有演绎功能一直是数据库研究领域的一个重要研究方向。一阶谓 词逻辑比较成功地应用于定理证明和逻辑程序设计语言。近年来人们一直致力 于基于逻辑的数据模型研究，所谓d d b m s ( d e d u c t i v ed a t a b a s em a n a g e m e n t s y s t e m ) 是以基于逻辑的数据模型为基础的d b m s ，是继r d b m s 、o d b m s 以后的数 据库的重要发展方向之一，其主要目的在于扩大数据库的查询功能( 特别是递归 查询功能) ，提高数据库的推理能力。基于逻辑的数据模型的研究与应用具有极 其重要的实际意义。 d a t a l o g 是一种基于逻辑的数据模型，可以看作是适用于数据库的p r o l o g 的特殊版本，但它有别于p r o l o g 。d a t a l o g 只允许变量和常量作为谓词的自变 元，而不允许函数符号作为自变元，它是一种受限的基于逻辑的数据模型。 d a t a l o g 程序设计语言由规则和事实组成，d a t a l o g 程序的运行就是通过应用规 则于已存在的事实，进行演绎逻辑推理，由原来的事实演绎出新的事实。所谓 规则就是描述事实之间逻辑关系的描述说明。事实( f a c t ) 和关系数据库中的 记录关系十分相似，数据库的记录关系可以理解为事实的集合。我们可以把 d a t a l o g 程序看作由一系列的事实和规则组成的数据库。 下面我们介绍一下d a t a l o g 的一阶逻辑基础的一些基本概念： 项( i t e m ) ：常量和变量都是项，t e r m = c o n s tuv a r ； 谓词( p r e d i c a t e ) ：谓词是一个从域d n 到集合 t r u e ，f a l s e 的映射； 原子( a t o m ) ：若p 是一个n 元谓词，序列( t l ，t 2 ，t n ) 中的每一个 t i ( o i n ) 是项，则p ( t l ，t 2 ，t n ) 就称为一个原子； 体( b o d y ) ：一个体就是原子的有限序列； 规则( r u l e ) ：一条规则由头和体组成，它表示为h e a d ：一b o d y 其中头是 一个原子，并且在头部中出现的所有变量都必须在b o d y 中出现； 程序( p r o g r a m ) ：一个程序就是有限条规则的集合。 在数据库研究中我们把d a t a l o g 的谓词分划为两个不相交的子集：内涵谓词 ( i p r e d ) 平口夕h 延谓词( e p r e d ) 。 内涵谓词( i p r e d ) ：是指d a t a l o g 程序中在头部出现的谓词。对于在d a t a l o g 程序p 中出现的内涵谓词的集合记为i d b ( p ) 5 第2 章逻辑程序设计语言n e t l o g 介绍 外延谓词( e p r e d ) ：是指d a t a l o g 程序中仅在体中出现的谓词。对于在 d a t a l o g 程序p 中出现的外延谓词的集合记为e d b ( p ) 模式( s c h e m a ) ：是指d a t m o g 程序中出现的谓词。对于在d a t a l o g 程序p 中出现的谓词的集合记为s c h ( p ) ，s c h ( p ) = i d b ( p ) ue d b ( p ) d a t a l o g 程序的运行是d a t a l o g 解释器通过规则的匹配查找符合条件的规 则，调用它完成对事实集合的添加。规则之间的调用是通过联合操作完成的， d a t a l o g 能够自动地完成模式匹配。d a t a l o g 语言是逻辑程序设计和数据库研究 中的一个重要语言，d a t a l o g 能够表示复杂的数据库查询功能( j e f f r e y1 9 8 9 ) 。 2 1 1d a t a i o g 对关系模型的支持 基于d a t a l o g 的逻辑数据库是由事实和规则组成的数据库，d a t a l o g 逻辑 数据模型与关系模型有着内在的关联。用d a t a l o g 的谓词符号表示逻辑数据库 的关系，可定义两种形式的关系：外延数据库e d b 关系和内涵数据库i d b 关系。 e d b 关系是存储在数据库中的事实，其内容是给定的，而i d b 关系则是由规则 和事实推导出来，可根据需要定义各种导出关系。从逻辑数据库模型的观点来 看，数据库是谓词实例的集合( 即事实) ；查询和i d b 关系都可以用逻辑程序中 的规则表示。所有关系模型中的关系都是e d b 关系，关系模型创建视图的能力 类似于d a t a l o g 中定义i d b 关系的能力，但其功能比以逻辑规则作为定义机制 的d a t a l o g 数据模型略为逊色。 如规则p a t h ( x ，z ) ：一e d g e ( x ，y ) ，e d g e ( y ，z ) ：表示如果存在x 到 y 的边和y 到z 的边，则存在一条x 到z 的路径。其中e d g e 是e d b 关系，p a t h 是i d b 关系，利用数据库中的事实可导出新的关系p a t h 。利用规则可表示各种 关系操作( 蔡菁2 0 0 2 ) ： 1 ) 选择操作。如规则p ( x ，y ) ：一r ( x ，y ) ，y 1 0 0 ；表示进行选 择操作p ( x ，y ) = o 叭加( r ) 。p ，r 在规则中表示谓词，在关系表 达式中代表关系，下同。 2 ) 投影操作。如规则p ( x ) ：一r ( x ，y ) ：表示进行投影操作p ( x ) = 1 7 ，( r ) 3 ) 连接操作。如规则p ( x ，y ) ：一r ( x ，z ) ，s ( z ，y ) ：表示进行连 n 接操作p ( x ，y ) = 1 7 “( r ( x ，z ) o o s ( z ，y ) ) 。 4 ) 并操作。如规则p ( x ，y ) ：一r ( x ，y ) ：和p ( x ，y ) ：一s ( x ，y ) ： 的头都是p ( x ，y ) ，表示进行并操作p ( x ，y ) = r ( x ，y ) us ( x ， y ) 。 6 第2 章逻辑程序设计语言n e t l o g 介绍 p 2 广 硒 r t魁 f i g 2 1 ( 蔡菁2 0 0 2 ) 非递归依赖图 运用d a t a l o g 逻辑数据模型可以完成各种关系查询。对于图2 1 所示的依 赖关系可以用下列两条d a t a l o g 规则来表示。 p ，( v ) ：- r 。( a ，u ) ，r 。( u ，v ) ：( 1 ) p ：( y ) ：一p 。( x ) ，r 。( x ，y ) ： ( 2 ) 因图2 1 所示的是一个无回路的有向图，因此这组规则为非递归规则。对 于非递归规则，可根据依赖图的顺序，自底向上计算各i d b 关系的值。首先将 d a t a l o g 规则变换成相应的关系操作，再进行计算。规则( 1 ) 和( 2 ) 对应的 d a t a l o g 操作如下。 p 。( v ) = 兀，( 0 。( r ，( w ，u ) ) r 。( u ，v ) ) ( 3 ) p 。( y ) ：丌，( p ，( x ) o o r 。( x ，y ) ) 根据e d b 关系r 。，r 。，r 3 ，按照关系操作( 3 ) 和( 4 ) ，可先后求得i d b 关系 p 。和p ：。递归问题则要复杂很多，一般的关系数据模型是不支持递归操作的， 当遇到递归查询时，用户只能自己编制相应的应用程序去解决，而d a t a l o g 逻 辑数据模型可以较轻松地解决递归问题。 2 1 2d a t a i o g 的递归应用 d a t a l o g 规则可表示复杂的语义关系，下面以一个家族数据库为例，介绍 - d a t a l o g 的递归应用( 蔡菁2 0 0 2 ) ： y ) ：一p a r e n t ( x ，z ) ，p a r e n t ( y ，z ) ，x c y ； z ) ：一p a r e n t ( x ，x p ) ，p a r e n t ( z ，z p ) ，s i b l i n g ( x p ，z p ) ， z ) ：一p a r e n t ( x ，x p ) ，p a r e n t ( z ，z p ) ，c o u s i n ( x p ，z p ) ， 7 仪 仅 g d n n n e 1 1 。， 1 - t t l s z s z a 玷 叫 叫订 s c x c x r 、，、， 1 2 3 4 第2 章逻辑程序设计语言n e t l o g 介绍 5 ) r e l a t e d ( x ，y ) ：一p a r e n t ( x ，z i ) ，p a r e n t ( y ，z 2 ) ，r e l a t e d ( z l ， z 2 ) ： 其中p a r e n t 是一个e d b 关系，p a r e n t ( c ，p ) 表示p 是c 的双亲之。通过 上面一组规则定义了i d b 关系s i b li n g ，c o u s i n 和r e l a t e d ，规则1 ) 的意思是 “对于所有的x 和y ，如果存在z ，使得z 是x 和y 的双亲，且x 和y 不是同一 人，则x 和y 是兄弟姐妹 ，即s i b l i n g 表示同胞关系；规则2 ) 和3 ) 说的是“对 于所有的x 和z ，如果他们的双亲之一是同胞或堂表亲，则x 和z 是堂表亲”， 这意味着具有堂表亲关系的人有相同的祖先；规则4 ) 意味着同胞也是亲戚关系， 而规则5 ) 意味着具有亲戚关系的人，他们的后代也具有亲戚关系。 逻辑程序中谓词之间的相互依赖关系可用一有向依赖图来表示，以普通谓 词作结点，从各子目标画条到规则头的有向边，如规则1 ) 引出了一条从p a r e n t 到s i b l i n g 的弧( 注意无需对内部谓词，如，建立结点) ，规则3 ) 引出了一条 从p a r e n t 到c o u s i n 的弧，及一条从c o u s i n 到c o u s i n 的弧，家族亲戚关系的 依赖图见图2 2 所示，图中包含r e l a t e d 和c o u s i n 的两个单结点环，是一递 归依赖图，因此上面用d a t a l o g 逻辑数据模型表现的是一递归关系的家族数据 库。 p a m a l f i g 2 2 ( 蔡菁2 0 0 2 ) 非递归依赖图 从数据库的观点来看，不仅需要知道逻辑数据库的语义，还应有相应的算 法去获取其语义，即给出基于逻辑的数据模型的计算。因为递归关系操作中没 有一个允许算法应用的线性顺序，即每当在依赖图中有一个环出现时，试图求 解的某一条规则必然有一个子目标的表达式还没有求出来，因此递归规则的计 算比非递归规则的计算要复杂许多。 2 2n e t l o g 语言介绍 在单纯的d a t a l o g 里没有定义否定( n e g a t i o n ) 记号的意义，也就是说 d a t a l o g 不具有描述否定事实的能力。但是在实际的应用数据库系统中不可避 8 第2 章逻辑程序设计语言n e t l o g 介绍 免地要讨论到否定事件或者是不存在的表记录。知识库语言方面的许多研究都 是关于d a t a l o g 的功能扩充的，目的在于扩充d a t a l o g ，增强其表达能力，例 如：d a t a l o g ，d a t a l o g 1 。其中d a t a l 0 9 1 允许体中出现否定词；d a t a l 0 9 1 允许头和体中都出现否定词，但是二者语义不同。 本文提出的逻辑语言n e t l o g ，相对于d a t a l o g 逻辑程序设计语言，增加否 定( n e g a t i o n ) 操作符和删除( c o n s u m p t i o n ) 操作符( j e a n1 9 8 7 ) 的定义。 下面我们介绍n e t l o g 的一些基本概念： 项( i t e m ) ：常量和变量都是项，t e r m = c o n s tuv a r ： 谓词( p r e d i c a t e ) ：谓词就是一个从域d 。到集合 t r u e ，f a l s e 的映射； 原子( a t o m ) ：若p 是一个n 元谓词，序列( t l ，t 2 ，t n ) 中的每一个 t i ( 0 4 i n ) 是项，则p ( t l ，t 2 ，t n ) 就称为一个原子； 文字( l i t e r a l ) ：文字就是一个正原子p ( t l ，t 2 ，t n ) 或者是一个 否定原子- ip ( t l ，t 2 ，t n ) 或者是一个删除原子! p ( t l ，t 2 ，t n ) ； 头( h e a d ) ：一个头就是一个正原子或者为空。 体( b o d y ) ：一个体就是文字的有限序列； 规则( r u l e ) ：一条规则由头和体组成，它表示为h e a d ：一b o d y 其中头部 中出现的所有变量都必须在体中出现； 程序( p r o g r a m ) ：一个程序就是有限条规则的集合。 在数据库的研究中我们把n e t l o g 的谓词分划为两个不相交的子集：内涵谓 词( i p r e d ) 和外延谓词( e p r e d ) 。 内涵谓词( i p r e d ) ：是指n e t l o g 程序中在头部出现的谓词。对于在n e t l o g 程序p 中出现的内涵谓词的集合记为i d b ( p ) 外延谓词( e p r e d ) ：是指n e t l o g 程序中仅在体中出现的谓词。对于在n e t l o g 程序p 中出现的外延谓词的集合记为e d b ( p ) 模式( s c h e m a ) ：是指n e t l o g 程序中出现的谓词。对于在n e t l o g 程序p 中 出现的谓词的集合记为s c h ( p ) ，s c h ( p ) = i d b ( p ) u e d b ( p ) 2 2 1n e t l o g 操作语义 在n e t l o g 引入否定的研究中通常是在封闭世界假定(