（计算机软件与理论专业论文）演绎对象数据库中几个关键问题的研究与实现.pdf

摘要 演绎数据库与面向对象数据库是对关系数据库技术的两大扩展。演 绎数据库既扩展了关系数据库的查询能力，又保持了关系数据库的数学 基础。面向对象数据库能够提供丰富的数据建模能力。两者具有很大的 互补性，所以演绎数据库和面向对象数据库的结合必然会成为数据库领 域的一个研究热点。演绎对象数据库不只是两个相关方向研究成果的简 单合并，它还牵涉到面向对象数据模型、面向对象数据库的理论基础、 基于逻辑的查询语言、结构化对象( 或称复杂对象) 处理、数据库系统体 系结构及开发等问题。 本文是在本课题组已开发的演绎对象数据库系统s d d o o d 之上进行 改进和扩充，在s d d o o d 的数据模型的基础上增加了复杂数据类型 集合；在查询表达式中支持主动表达式和集合表达式；进一步探寻演绎 数据库和面向对象数据库的结合途径。本文的主要工作为： 1 介绍了包含集合和继承的语法及语义，从语义的角度阐明了数据 库的约束条件。 2 给出了演绎对象数据库g d d o o d 的系统结构图，然后对系统结构 图中涉及到的每一个模块的功能进行了详细的解释。 3 区分了完整集和部分集的概念，实现了集合这一数据类型。讨论 并实现了部分集在规则中的应用：规则体中部分集用来列举集合中的元 素，而规则头中部分集用来聚集属于集合的所有元素。通过对方法表达 式中的部分集和属性表达式中的部分集的不同的转换方法和存储方法实 现了含有部分集规则的推理。实现了完整集的并、交、差以及划分操作。 集合的实现减少了数据库的存储冗余，也方便了用户描述复杂对象。 4 对查询进行了详细地分类。对模式定义和实例属性的查询采用匹 配方式，对于方法的查询的实现有自底向上和自顶向下两种，重点介绍 了如何将演绎对象数据库语言( d o o l ) 转换为演绎数据库语言( d d l ) 然后 用d d l 中的最小不动点算法求解的过程和算法。复杂查询要划分为几部 分简单查询来实现。 g d d o o d 系统是在w i n d o w s x p 环境下，采用l e x & y a c c 对d o o l 语言进行 分析，利用s o ls e r v e r2 0 0 0 作为外延数据库，使用v c + + 6 0 作为编程语 言实现的一个系统。它是一个集成的图形用户接口( g u i ) 。通过这个窗 口，用户可以进行创建类和它的对象以及查询、更新数据库中已经存在 的信息等操作。 实验表明，s d d 0 0 d 系统支持面向对象数据库的核心概念，如：类、 类层次、对象、属性、规则、继承和封装等；具有演绎数据库的推理功 能：本文提出并实现了集合的存储和表示以及包含部分集的规则推理， 实验结果显示出这种方法对提高系统的查询能力是有效的。 关键词：演绎对象数据库；继承；部分集；集合；查询 中图分类号：t p 3 1 1 t h er e s e a r c ha n di m p l e m e n t a t i o no fs e v e r a lk e yp r o b l e m s i nd e d u c t i v eo b j e c t o r i e n t e dd a t a b a s e f a nx i a ( d a t a b a s et h e o r ya n dt c h n o l o g y ) d i r e c t e db yp r o f t a os h i q u n a b s t r a c t d e d u c t i v ed a t a b a s ea n do b j e c td a t a b a s ef d o o d ) a r et w oe x t e n s i o n so f r e l a t i o nd a t a b a s e ( r d b ) t e c h n o l o g y t h ed e d u c t i v ed a t a b a s et e c h n o l o g yn o t o n l ye x t e n d st h eq u e r ya b i l i t yo fr d b ，b u ta l s ok e e p st h em a t h e m a t i c a l b a s i so fr d b t h eo b j e c t o r i e n t e dd a t a b a s ec a np r o v i d ea b u n d a n td a t a m o d e l s t h e s et w ot e c h n o l o g i e sh a v ec o m p l e m e n t a r i t y , s ot h ec o m b i n a t i o n o f d e d u c t i v ed a t a b a s ea n do b j e c t o r i e n t e dd a t a b a s ei ss u r e l yt ob eaf o c u so f d a t a b a s ed o m a i n i tw o n tb ej u s tas i m p l em e r g i n go ft h e s et w or e l e v a n t r e s e a r c hd i r e c t i o n s ，i ta l s oi n v o l v e sb a s i co b j e c t o r i e n t e dd a t am o d e l ，b a s i s o fo b j e c t o r i e n t e dd a t a b a s e t h e o r y , a n dl o g i c - b a s e dq u e r yl a n g u a g e ， p r o c e s s o fs t r u c t u r e d o b j e c t ( c o m p l e xo b j e c t c ) ，a n d a r c h i t e c t u r ea n d d e v e l o p m e n to fad a t a b a s e t h i st h e s i si m p r o v e sa n de x p a n d st h e e x i s t i n gs d d o o d ，a p p e n d i n ga k i n do f c o m p l i c a t e dd a t at y p e ：s e to nt h eb a s eo fd a t am o d e lo fs d d o o d ； i ta l s os u p p o r ta c t i v ee x p r e s s i o na n ds e te x p r e s s i o n ；e x p l o i tf u r t h e ra p p r o a c h f o rt h ec o m b i n a t i o no fd e d u c t i v ed a t a b a s ea n do b j e c t o r i e n t e dd a t a b a s e t h e m a i nw o r ko ft h i st h e s i si ss h i n t o a r i z e da sf o l l o w s ： 1 t h es y n t a xa n ds e m a n t i co ft h ed o o lw i t hs e ta n di n h e r i t a n c ea r e i n t r o d u c e da n dt h ec o n s t r a i n tc o n d i t i o n sa r ei l l u s t r a t e df r o mt h e p o i n to f v i e wo fs e m a n t i c 2 t h es y s t e ma r c h i t e c t u r ei sp r o v i d e da n dt h ef u n c t i o no fe v e r ym o d u l e r e l a t e dt ot h ea r c h i t e c t u r ei se x p l a i n e di nd e t a i l 3 t h ec o n c e p t so fc o m p l e t es e ta n dp a t i a ls e ta r ed i s t i n g u i s h e d ，a n d r e a l i z et h es e td a t at y p e t h eu s eo fp a r t i a ls e t si nr u l e si sd i s c u s s e d ：t h e p a r t i a ls e ti nr u l eb o d ye n u m e r a t ee l e m e n t si nas e tw h i l et h ep a r t i a ls e ti n r u l eh e a dg r o u pt h ee l e m e n td e d u c e df r o mt h er u l eb o d y t h ei n f e r e n c eo f r u l e si n c l u d i n gp a r t i a ls e t si si m p l e m e n t e dt h r o u g hu s i n gd i f f e r e n tt r a n s f o r m a p p r o a c hf o rm e t h o de x p r e s s i o na n da t t r i b u t ee x p r e s s i o n t h eo p a e r a t i o no f u i n i o n ，j o i n ，d i f f e r e n t i a t e a n dp a r t i t i o no fc o m p l e t es e ti sa c h i e v e d t h e r e a l i z a t i o no fs e td e c r e a s e dt h es t o r a g er e d u n d a n c ya n di ti sc o n v e n i e n tt o d e s c r i b ec o m p l e xo b j e c tf o ru s e r s 4 ad e t a i l e dc l a s s i f i c a t i o ni sm a d ef o rq u e r i e s t h eq u e r i e sf o rs c h e m a d e f i n i t i o na n da t t r i b u t e so fo b j c e c t sa r ec a r r i e do u tu s i n gt h em a t c h i n g a p p r o a c h t h e r ea r et w ow a y sf o rm e t h o d sq u e r i e s ：t o p d o w na n db o t t o m u p t h ep r o c e s sa n da r i t h m a t i co ft r a n s l a t i n gd o o lt od d la n d u s i n g m i n i m u mf i x e dp o i n ta l g o r i t h mi nd l li sm a i n l yi l l u s t r a t e d ac o m p l i c a t e c d q u e r yi sd i v i d e di n t of o u rp a r t s ，e a c ho fw h i c hi sc o m p o s e do fa t t r i b u t e e x p r e s s i o n s ，m e t h o de x p r e s s i o n s ，m a t h e m a t i ce x p r e s s i o no rt h en e g a t i v e e x p r e s s i o n s s d d o o ds y s t e mi sa ni n t e g r a t e dw i n d o wc i r c u m s t a n c eu n d e rw i n d o w s x p , a d o p t i n gl e x & y a c ct oa n a l y s i sd o o l ，u s i n gs q ls e r v e r2 0 0 0a s e x t e n td a t a b a s ea n du s i n g v c + + 6 0a st h e p r o g r a m m i n gl a n g u a g e t h e w i n d o wi sag r a p h i cu s e ri n t e r f a c ei nw h i c hu e rc a nc r e a t ec l a s s e s ，o b j e c t c s a n dq u e r ya n du p d a t et h ei n f o r m a t i o ns t o r e di nt h ed a t a b a s e t h ee x p e r i m e n ts h o w s ，t h es d d o o dn o to n l ym a i n t a no b j e c t o r i e n t e d c o n c e p t ss u c ha sc l a s s ，c l a s sh i e r a r c h y , o b j e c t ，a t t r i b u t e ，r u l e ，i n h e r i t a n c ea n d e n c a p s u l a t i o n ，b u ta l s oh a v et h ei n f e r r i n gc a p a b i l i t y t h et h e s i sp r o p o s e sa n d r e a l i z e st h ed e n o t a t i o na n dt h es t o r a g ea p p o r a c ho fs e ta n dt h ei n f e r e n c eo f r u l e sc o n t a i n i n gp a r t i a ls e t sa n da c t i v ee x p r e s s i o n i ti s p r o v e dt h a tt h e i m p r o v e dl a n g u a g ei sm o r ed e c l a r a t i v ea n di se f f e c t i v et oe n h a n c et h eq u e r y a b i l i t y k e y w o r d s ：d e d u c t i v eo b j e c t o r i e n t e dd a t a b a s e ；i n h e r i t a n c e ；p a r t i a ls e t ；s e t ； q u e r y 第一章引言 第一章引言 1 1 论文的研究背景 自从二十世纪7 0 年代以来，关系数据库以其概念简单、结构清晰，易于用户 理解和使用的特性蓬勃发展起来，并在实际的商用数据库产品中得到了广泛应用。 关系数据模型具有严格的数学基础和简洁性，当前对其查询优化技术和存储技术的 研究也是很有成效的。关系数据库对于长期的数据存储、数据检索和受限的数据共 享来讲是足够的。但是，在计算机辅助设计、软件工程、办公自动化、图像和图形 处理、人工智能和许多其它领域的应用中，关系数据库还有很多限制，在文献 2 】 中有详细说明；其查询语言不是完全独立语言，经常需要嵌入到一个程序语言中； 在查询语言和应用语言的数据结构之间的差异，通常称作“阻抗不匹配问题”：无 法定义新类型等。从二十世纪8 0 年代中期开始，研究者们提出了不同的扩展关系 数据库系统的方案 】。这些方案中的每一种都有不同的目标，但是大多数努力都是 为了提供一个更丰富的数据模型和通过一个集成语言来表示数据、视图、约束、查 询和应用，以解决“阻抗不匹配问题”。 从当前的发展看，对象数据模型占据着很重要的地位，它具有丰富的数据建模 能力。另一个著名的数据库是演绎数据库，它扩展了关系数据库的查询能力，并保 持了关系数据库的数学基础。现有的发展趋势表明：现代数据库应能管理数据、对 象和知识，然而关系数据库只能管理数据，面向对象数据库不能管理知识，演绎数 据库不能管理对象，所以这就需要一个更为全面的数据库技术。 1 2 演绎对象数据库 1 2 1 演绎数据库 演绎对象数据库( d e d u c t i v ed a t a b a s e ，简称d d b ) 的研究7 0 年代由美国的 j m i n k e r 和法国的h g a l l a i r e 、j m n i c o l a s 等人发起的，到了8 0 年代，d d b 的研 究，特别在查询优化方法方面的研究【1 呈现出新的生机。 演绎数据库就是人工智能中的知识及其推理机制在传统数据库中的引入，因此 与传统数据库相比较，其优势体现在语义表达能力的增强和功能的扩充。演绎数据 库用关系模型( 描述事实) 和d a t a l o g 模型( 描述规则) 来描述现实世界，除了传 统数据库系统的操纵功能外，还具有知识操纵功能，包括知识的增、删、改、推理 和完整性维护等。n ) g 传统数据库可看作是演绎数据库的一个子集，从数据库的作 用( 描述和操纵现实世界) 来看，演绎数据库是在传统数据库基础上一次质的飞跃， 演绎对象数据库中几个关键问题的研究与实现 是向更高层次的迈进。演绎数据库不但能处理大量的数据而且兼备逻辑推理能力， 通过推理可获得比存储的数据多得多的信息，可以节省空间。演绎数据库使用统一 的逻辑语言定义数据、规则和提出查询，具有非常良好的用户界面。逻辑语言具有 非过程性的特征，并且是计算完全的，是最理想的查询语言。此外，一致性的约束 规则亦是用逻辑语言来定义的，可以为优化查询之用【8 l 。 演绎数据库具有坚实的理论基础，许多有意义的工作都是基于其上的，如：否 定、查询优化、一致性约束维护和约束问题求解等。可是演绎数据库更大的缺点是 并不能改善数据库的数据建模能力，如在演绎数据库中无法将数据及应用在其上的 规则封装起来，也无法描述数据类型间的转换关系等。而这正是面向对象的数据库 所具有的功能。 1 2 2 面向对象数据库 目前，从实现的角度来看，面向对象思想和数据库技术的有机结合业已完成， 一些面向对象数据库( o o d b ) 的商业性系统已投放市场( 0 2 ，o r i o n ) 。o o d b 的主要 目标是扩大数据库技术应用面( 如工程或c a d 数据库) ，并同时提高程序员的生产 率。这项工作取得成功的例证是：越来越多的数据库系统宣称具有面向对象的特征， 尽管许多关系系统生产厂商还在大力否认o o d b 研究。 关系模型所提供的数据结构对许多应用来说过于简单。对o o d b 系统，虽然 还没有一个广泛接受的标准数据模型，但实现的系统一般都是基于更丰富的数据结 构，并且面向对象方法改善了数据建模设施。首先，对象的概念统一了关于数据的 认识，给应用的设计带来了便利。此外，o o d b 中使用的模型具有以下优点： ( 1 ) 对象标识( o i d ) 允许描述数据共享和递归构造，并且还是对数据行为和数据进 化进行建模所不可缺少的。 ( 2 ) 类的概念自然地导致类层次及继承的思想，因而使得代码共享和重用，为系 统的可扩充性和递增开发带来了更大的灵活性。 ( 3 ) 许多数据模型包含了复杂对象，这在许多应用，尤其是工程应用中是很必要 的。 语义丰富的数据模型方便了应用的设计。此外，现有的应用建模方法大多是基 于对象的( e r 方法) ，因此，如果数据库模型是基于对象的，那么它和方法学的数 据模型间的差距就会缩短。面向对象方法的另外的主要优点是，通过动态便联和增 量编译极大地简化应用程序员的工作，这些和继承所带来的好处合在一起是面向对 象语言的传统优点。 第一章引音 从负面来说，o o d b 系统缺乏关系系统那样的形式化基础，这在一定程度上限 制了有效设计和优化工具的构造。最后。尽管大多数o o d b 也提供查询语言，但没 有演绎能力，并且在大多数情况下，甚至没有真正意义上利用面向对象的优点。演 绎的面向对象数据库的研究背景就是保留优点，克服纯粹o o d b 系统的缺点。 1 2 3 演绎的面向对象数据库 演绎数据库( d e d u c t i v e o b j e c t o r i e n t e dd a t a b a s e ，简称d o o d ) 系统是的查询语 言是以一阶逻辑为基础的，因此，它的查询语言说明性强，而且在查询优化方面具 有很大的优越性。面向对象的数据库系统在结构和行为的表示上功能很强，适应于 关系数据库所不能胜任的一些应用领域。而o o d b s 和d d b s 都有欠缺，o o d b 缺 乏形式定义、查询语言的说明性不强，d d b s 没有丰富的数据模型以及建立在该模 型之上的封装、继承、重载等机制。可以看出，演绎数据库和面向对象的数据库有 很大的互补性，基于这种互补性，演绎数据库技术和面向对象数据库技术结合在一 起形成数据库领域内一个新的研究方向演绎对象数据库。 d o o d 不只是两个相关方向研究成果的简单合并，它还牵涉到基础的面向对象 数据模型、面向对象数掘库的理论基础、基于逻辑的查询语言、结构化对象( 或称复 杂对象) 处理、数据库系统体系结构及开发等问题。这些问题的研究和解决可望促成 面向澍象、逻辑理论及复杂对象等领域相关概念、思想的统一和融合，可望逐步明 确和统一新一代数据库系统的数据模型、查询语言、体系结构的认识，从而开辟数 据库研究的新局面。如何有机地将演绎数据库和面向对象的数据库结合起来仍然是 一个有挑战性的任务i l 。 从研究途径来看，演绎数据库的研究实际上是从两个方面进行的：从一阶子句 逻辑向演绎数据库的演进和从关系数据库出发扩充演绎能力形成演绎数据库。演绎 对象数据库实际上也可以走同样的发展路线。然而演绎对象数据库的研究并没象演 绎数据库那样成功，这多少归因于对象数据库理论的不完善及其复杂性。困难具体 体现在两个方面： ( 1 ) 面向对象数据库没有像关系数据库那样完善的理论基础，演绎对象数据库无 法唯一确定适合于扩展演绎能力的面向对象的数据库系统。 ( 2 ) 我们也无法找到一种适合得逻辑系统能够更好地体现对象特征。对象的复杂 性自然要求高阶逻辑系统，然而高阶逻辑系统得不完备性使得从逻辑系统扩充方法 并不象演绎数据库那样容易。 演绎对象数据库中几个关键问题的研究与实现 1 3 演绎对象数据库的实现方法 目前对演绎对象数据库的研究采取两种途径：将形式化的证明系统嵌入到对象 数据库系统中和将对象概念融入到逻辑系统中。大多数的研究采用后一种形式。 实现d o o d 的数据模型方法可归为三种：( 1 ) 面向对象语言与逻辑语言并用。 通常采取用面向对象的语言，如c + + 、s m a l l t a l k 等定义对象结构，用逻辑语言说 明对象的方法。这是一种快而有效的途径，如c o r a l l + + 。( 2 ) 扩充逻辑程序设计 系统( 如p r o l o g ) ，引入方法、类型及持久对象的概念。这能使用户同时具有面向对 象与演绎的概念，但实现起来效率较低。( 3 ) 面向对象的逻辑，是把丽向对象的特点 与逻辑语言充分结合，它可以是一种新的非标准的逻辑语言，也可以是传统逻辑语 言的扩充。这是对象与逻辑结合最紧密的一种方法，如f l o g i c 。 一个具体的演绎对象数据库系统的实现方法分为以下四种 7 i uj q 4 】：( 1 ) 扩充关系 数据库，由于目前市场上广泛使用关系数据库，所以从关系数据库平稳过渡到 d o o d 是一种自然的方法。然而，在完善的关系理论的基础上进行扩充，结果未必 理想。( 2 ) 扩充演绎数据库，目前大部分演绎数据库系统都是基于d a t a l o g 的，其优 点是实现了递归查询求值和许多查询优化技术。从技术观点看来，主要的困难在于 如何能在引入面向对象特征的同时保持良好的系统性能。( 3 ) 扩展o o d b 系统。 o o d b 的优点是以在数据库语言中引入过程性语言为代价而取得的。如果再向说明 性语言方面进化，可能在o o d b 界看来会失去对数据的直接控制。如何在o o d b 中加进演绎能力及相应的优化技术还不够清楚，o o d b 缺乏形式化基础使得这项工 作不太好做。( 4 1 从头设计，从头构建d o o d 的难度比较大，但如果做得好，则是 最有效的。 实现一个演绎对象数据库系统时，应该遵循如下三条原则( 1 ) 支持演绎推理。 系统必须提供演绎推理规则，它能够对存储的数据进行推理。演绎范例的标准特性， 如：变量匹配、递归谓词定义等在规则语言中是有效的。( 2 ) 支持面向对象。系统 必须提供个包含结构和行为方面的应用模式的面向对象的模型。o o 模型的基本 特性如：对象标识、类、继承、封装、重载。( 3 ) d b m s 功能的支持。系统必须提 供一个d b m s 系统需要的核心功能。在系统中应该实现a c i d 和数据独立性。 1 4 国内外研究动态 关于演绎对象数据库的研究可追溯到二十世纪8 0 年代后期，它与面向对象的 研究是紧密相关的，可以说二者是并行发展的。目前对演绎对象数据库的研究呈现 第一章引言 多样性，各种方案也大致刻画了面向对象的主要特征。在国际上，自1 9 8 9 年开始， 每两年召开一次“演绎和面向对象的数据库”的国际会议，吸引了众多数据库研究 和开发人员。在此期间，国内外已经出现了不少原型系统和有影响力的理论模型， 如：r o c k & r o l l ，d a t a l o g + + ，c h i m e r a ，r o l ，r o l 2 ，d o d m 及s d d o o d 等。 ( 1 ) r o c k & r o l l 1 5 - 1 6 1 演绎对象数据库系统的实现大致基于三种语言模型：语言的扩充、语言的结合 和语言重建。对于基于语言结合方案的系统，是把一种演绎数据库语言和一种强制 性语言在面向对象或面向类型的基础上结合起来，最终形成的系统不论在构建数据 还是在编写程序时，都支持一系列的面向对象的机制。根据不同的任务，系统决定 使用两种语言中的种。r o c k & r o l l 就是基于语言结合的，同一个类中它的方 法的实现既可以是面向推理的规则也可以是面向过程的程序。 ( 2 ) d a t a l o g + + 1 7 1 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 + + 编写的程序转换成后台演绎数据库系统理解 的逻辑程序。 ( 3 ) c h i m e r a 1 8 1 c h i m e r a 系统由c h i m e r am o d e l ( c m ) 矛l lc h i m e r al a n g u a g e ( c l ) 组成。c m 提供 面向对象的建模能力，c l 提供数据定义、说明性查询、数据库操作的过程原语、 各种各样的规则和约束。c l 支持被动规则，这些规则用来说明性地定义类- 实例关 系、对象的属性值，也可以实现视图和约束。规则头是原子公式，而规则体式原子 公式的合取。关于否定或集合，规则必须是分层的，这样才能保证在计算最小不动 点时找到最小模型。c l 也支持一定的与数据库相关的命令性原语，所以包含一定 程度的过程性语法。c l 中的过程性表达式由数据库语句原语，如：更新、查询、 操作调用。c l 也支持主动规则，主动规则的规则体中是一系列的数据库行为。 ( 4 ) r o l 1 9 - 2 5 & r o l 2 f 2 6 - 2 8 1 r o l 系统提供一个统一的说明性语言定义、操纵和查询数据库。它支持面向 对象的特征，如：对象标识，复杂对象，类，类层次和有重载、阻塞的多继承。它 也支持结构化值，如：集合、算符对象。r o l 不仅是可以作为一个纯粹的面向对象 的演绎数掘库语言也可以作为一个纯粹的面向值的演绎数据库语言，它把传统的演 演绎对象数据库中几个关键问题的研究与实现 绎数据库语言d a t a l o g 作为一个特例来对待。r o l 实现了面向对象的结构特征， r o l 2 是在r o l 的基础上扩展了面向对象中的行为特征，如：基于规则的方法及其 封装。如果说r o l 的实现是让演绎数据库语言具有面向对象的特征，那么r o l 2 是让面向对象的数据库具有演绎的能力。 ( 5 ) f l o o r s f l o o r s 是复旦大学研制开发的，其基础是具有客户服务器体系结构的面向对 象数据库系统f o o d 和基于客户服务器结构的演绎数据库系统k b a s e p 。其实现 的演绎对象数据库系统f l o o r s 是建立在基于多数据源的面向对象数据库平台 m o d i p 上，对象的更新与维护基本由m o d i p 完成，f l o o r i s 除包含对象数据库 原有的功能，还能够利用f l o o r 语言定义内涵对象、演绎方法等，并能提供多种 形式的查询语言。 ( 6 ) d o d m 2 9 1 d o d m 是上海交通大学开发的。d o d m 显式地区分类和型的概念，通过型间 的偏相似关系体现丰富的继承语义。在一般的对象设计模型中，继承是通过类问的 序关系米描述，然而如果在引入非单调性时，语义解释就变得复杂了，该模型引入 型问的偏序关系可刻画更一般的继承关系，使得单调继承和非单调继承、单继承和 多继承统一于型问的偏相似关系上。 仃1s d d o o d 3 0 , 3 3 1 s d d 0 0 d 是山西大学研究的。一个演绎对象数据库实验系统。在系统中首先定 义了一种演绎对象数据库语言s d d o o l 【3 1 , 3 4 ；随后提出了一种得到派生类的方法 1 3 2 】，即利用规则产生子类，并给出了具体的实现算法。后来又提出了在系统中解决 非单调的结构和行为规则的各种继承方法1 3 5 , 3 6 1 。 综上所述，在过去的二十年中，研究者们提出了许多演绎对象数据库语言及数据 模型，也实现了很多演绎对象数据库系统的原型。在这些系统中继承、封装仍然是 非常有争议的两个问题，尤其是方法的封装。由于传统d d b 的查询语言是基于h o r n 子句的，因此没有与过程语言中方法相对应的概念，也没有对多态的支持。因而在 d d b 基础上所提出的面向对象演绎查询语言，很多都忽略了方法及方法继承。m k i f e r 等提出的f l o g i c l 3 3 】使用了非基i d 项( n o g r o u n d l d t e n n ) 作为方法定义的标志。在 f - l o g i c 中，一个子类可以是超类的一个实例，类可以作为对象来使用，这种概念 上的重叠，就混淆了一个类定义的方法是作为其类上的方法还是此类中单个对象的方 法之间的区别，在对象利类之间定义方法也有一些限制，例如，关系模型中像连接 第一章引言 这样的操作也无直观的定义。i q l l 3 8 n i l o g ”1 提出了对象标识符创建的概念，但也 仅讨论了数据继承，没有清晰的方法概念，在文献 4 0 j 中，a b i t e b o u l 提出了方法是满 足某种类型限制的函数，并通过示例讨论了方法继承和重载，但并未给出理论保证。 另一方面，h i l o g l 4 1 】讨论了具有一阶语义的高阶语法，虽然没有直接讨论o o 特征， 但已有了定义方法的机制，并且参数化多态可以容易地实现。不过，h i l o g 没有说 明如何实现继承。封装的问题一直没有一个合适地解决，在r o l 2 系统的数据模型中 提到了封装，但是在其实现部分仍然忽视了它。在演绎对象数据库中，最能体现演 绎数据库和面向对象数据库结合的地方是方法的实现部分，方法的实现是由规则推 理完成的。对于一个具体的规则的执行，首先需要识别规则体和规则头中面向对象 表示的原子公式，然后才能完成推理。在对演绎对象数据库查询中有很大一部分是 对方法的查询，也就是对内涵属性的查询，那么方法的实现方案、采用的查询优化 技术直接影响了查询的执行的效率，所以这是本文的研究内容之一。其实复杂对象 的演绎技术也一直是演绎对象数据库领域的研究热点之一【4 2 】， f - l o g i c l 4 3 1 、c o l 4 4 】 与r e l a t i o n l o g1 4 5 1 中都对复杂对象，主要以集合为例的演绎技术作了讨论，f - l o g i c 对 集合定义得较为完善但很复杂， r e l a t i o n l o g 则对集合演绎技术进行了探讨， 但它 们的缺点是都未涉及具体实现。本文给出了集合这一复杂对象的具体的应用和实现； 使用部分集合完整集来表示部分信息和完整信息，出现在规则体和规则头中的部分 集所起的作用不同，相应的实现也不同。把集合看成一种特殊的类，实现其中的一 些基本的方法，如交、并、差以。 1 5 本文的工作 本文的工作可以总结如下： 1 介绍了包含集合和继承的语法及语义，从语义的角度阐明了数据库的约束条 件。 2 给出了演绎对象数据库s d d o o d 的系统结构图，然后对系统图中涉及到的 每一个模块的功能进行了详细的解释。 3 讨论并实现了部分集在规则中的应用：规则体中部分集列举集合中的元素，而 规则头中部分集的聚集属于集合的所有元素。通过对方法表达式中的部分集和属性 表达式中的部分集的不同的转换方法和存储方法实现了含有部分集的规则的推理。 实现了完整集的并、交、差以及集合的划分。集合的实现减少了数据库的存储冗余， 也方便了用户描述复杂对象。 演绎对象数据库中几个关键问题的研究与实现 4 对查询进行详细的分类：简单查询和复杂查询，在查询表达式中至多出现一 个属性表达式、方法表达式、或主动表达式的查询是简单查询；同时出现了多个属 性表达式、方法表达式或主动表达式的查询是复杂表达式。对模式和实例属性的查 询主要采用匹配的方法，对于方法的查询的实现有自底向上和白项向下两种。复杂 查询要划分为几部分简单查询来实现。 第二章演绎对象数据库语言d o o l 第二章演绎对象数据库语言d o o l 2 1 语言的语法描述 在d o o l 中区分属于永久值类中的值和属于用户定义的对象标识符( o i d s ) 类的 对象，有两个特殊的值类v o i d 和n o n e 。n o n e 用来表示在子类中阻塞了对父类的某 一属性或方法的继承。类v o i d 只有一个值n j l 空值，表示一个方法的返回值是空值。 象c + + 和j a v a 一样，d o o l 中定义了一个特殊的变量t h i s ，用来指定当前的对象。 整篇论文中，以大写字母开头的字符串表示变量。 2 1 1 语法定义中的相关记号 首先给出下面的符号定义及其意义 ( 1 ) 值类类名的集合b = i n t e g e r , s t r i n g , v o i d ，n o n e ，c h a r , f l o a t ； ( 2 ) o i d 类名的集合c ； ( 3 ) 集合类s ； ( 4 ) 属性标签的集合a ； ( 5 1 方法名的集合m ： ( 6 ) 值的集合d ，包含正数集合，字符串的集合s t r ，字符的集合c h 以及实数 的集合f ，和集合 n i l ，； ( 7 ) 对象的集合d ； ( 8 ) 集合对象的集合，集合对象包括完整集集合对象和部分集集合对象； ( 9 ) 变量的集合k 包含变量t h i s 。 21 2 语法定义中的基本术语 为了定义数据库我们引入了如下概念 定义2 j 类( c l a s s 】 类包含如下三种：( 1 ) b 中的元素是值类；( 2 ) c 中的元素是o i d 类：( 3 ) 集合类， 可表示为f 值类或o i d 类) 。 定义2 2 项( t e r m ) ( 1 ) 一个项是一个值( v a l u e ) 或者是一个对象( o b j e c ti d e n t f y e r ) 或者是一个集合对象 或者是一个变量； ( 2 ) 一个变量是一个值或者一个o i d 或者一个集合对象； ( 3 ) 一个o i d 项是一个对象( o i d ) 或者一个变量； ( 4 ) 一个值项( v a l u et e r m ) 是一个值或者是一个变量； 演绎对象数据库中几个关键问题的研究与实现 ( 5 ) 一个集合项( s e tt e r m ) 是一个值项的集合或一个o i d 项的集合或一个变量； 如果一个项中没有变量那么这个项是基项。 定义2 3 表达式( e x p r e s s i o n ) 表达式的定义是建立在项的基础上。 ( 1 ) 如果c 是类，d 是o i d 项，那么c j0 是一个简单表达式，称为正的o i d 成员 表达式； ( 2 ) 如果。是一个o i d ，是一个属性标签，o 是一个项，那么o ，一 o 堤一个简 单表达式，称为正的属性表达式。当0 是t h i s 时，我们可以简单写为l - 0 ： ( 3 ) 如果0 是一个o i d 项，m 是n 元方法的方法名，0 l ，0 2 ，0 。，d r 是项。那么 o m ( o l , 0 2 ，仉) 一 q 是一个简单的表达式，称为一个正的方法表达式，如果0 是 t h i s 这个变量，那么整个表达式可以写作m ( o l ，d 2 ，0 n ) 一 0 r ，如果o 。是n i l ，那么 这个表达式可以写作o m ( o l ，0 2 ，o 。) ，当o 为t h i s ，o ，为n i l 是整个表达式可以 简单写为m ( o i ，0 2 ，o 。) ； ( 4 ) 如果e 时正的o l d 成员、属性表达式式或方法表达式，那么一e 时个简单 表达式，称为负的o i d 关系、属性表达式或方法表达式； ( 5 ) 如果c j0 是正的o i d 成员、属性式或方法表达式，dn ，0 k ，一0 u ， 一d u 。是属性表达式或方法表达式，n o ，m 0 ，那么c ；o 【h ，环，一m ，一c ，m 】和0 h ，碥，一矾，一0 是复合表达式。当n = o 时，0 一己 ，一乙k 】称为负的复合的表 达式，当m = 0 时，0 【巧，嘲成为正的复合表达式： ( 6 ) 如果e 是正的简单的或复合的表达式那么u p d a t ee 、d e l e t ee 是主动表达式； 2 1 3 模式语法 在数据库模式中，我们定义了类层次、类的属性、类的方法和继承冲突处理方 法，我们将用下面的例子来说明这些面向对象的特征。 例1 ：一个s d d o o d 系统的模式定义 c l a s sp e r s o n d a m e = s t r i n g ； b i r t h y e a r = i n t e g e rd e f a u l t 2 0 0 0 ； h o m e p h o n e 2 i n t e g e r ； s p o u s e 2 p e r s o n ； e m e r g e n e y c o n t a c t 2 i n t e g e rd e f a u l t9 1 1 ： a g e 0 = i n t e g e r a g e ( ) 一 a ：一b i r t h y e a r - b ，a = 2 0 0 6 一b c o n t a c t n u m b e r 0 2 i n t e g e r c o n t a c t n u m b e r 0 - x ：h o m e p h o n e x l 1 n 第二章演绎对象数据库语言d o o l m a r r i e d _ t o ( p e r s o n ) m a r r i e d _ t o ( 均：一s p o u s e 一 x ) s i n g l e ( ) s i n g l e ( ) ：一一m a r r i e dt o ( x ) 1 c l a s se m p l o y e ei s ap e r s o n b i r t h y e a rd e f a u l t19 6 0 ； w o r k p h o