全序偏序时态数据库的研究

论文摘要

随着数据库与信息技术的发展,信息系统面临许多新的应用和需求,对时态信息处理的需求越来越迫切。时态信息处理已成为许多新一代数据库与信息系统的关键技术,时态数据库研究已经成为数据库与信息系统的一个重要和充满活力的学科方向。同传统的关系数据库一样,在时态数据库的研究中,核心问题之一就是时态数据库的逻辑设计。多粒度时态数据库由于其对多时间粒度的支持而使其具有较为先进的特性,如何为多粒度时态数据库设计有效的规范化方法就成为时态数据库研究人员的重要课题。在以往的多粒度时态数据库设计方法的研究中,由于算法中所涉及的时态类型间的操作相当复杂,难以用其进行有效的时态数据库设计。本课题致力于研究更加有效的、实用的多粒度时态数据库设计方法。由于现实世界中的许多应用涉及到的时态类型集都能满足全序关系,如秒、分钟、小时、日、月和年,而具有全序时态类型集的全序时态模式有着良好的特性,研究全序时态模式的设计方法将具有现实意义。本课题首先全面研究了全序时态数据库中的时态数据依赖问题以及相关的时态范式分解问题,并在此基础上进一步研究了偏序时态数据库中的规范化问题。具体做了以下几方面的工作:1.全序时态数据库的成员籍问题研究。给出了全序时态模式中的基本概念,全序时态函数依赖（temporal functional dependencies,TFDs）推导规则,全序时态模式中属性集的闭包算法以及全序时态模式中的成员籍算法,并在此基础上解决了全序时态数据库的TFDs覆盖问题。2.全序时态BC范式的分解问题研究。给出了全序时态BC范式的相关概念,时态候选关键字集算法以及满足全序连接无损性的全序时态BC范式的分解算法。3.全序时态简单范式的分解问题研究。给出了全序时态简单范式的相关概念,全序时态简单候选关键字集算法以及一个满足保持时态函数依赖与全序无损连接性的全序时态简单范式分解算法。其规范程度高于全序时态3范式。4.强全序时态模式中多值依赖问题研究。给出了规则的时态多值依赖（Regular Temporal Multi-valued Dependency,RTMVD）等概念,全序RTMVD推理规则,RTMVD与强全序时态模块模式无损分解之间关系的相关定理,强全序时态模式中混合依赖集成员籍算法以及全序时态混合依赖集的覆盖算法。5.非严格偏序时态模式中的TFDs研究。给出了非严格偏序时态类型集、非严格偏序时态模式等基本概念,提出了非严格偏序TFDs推导规则以及非严格偏序时态模式中属性集的闭包算法。6.非严格偏序时态模式中的BC范式分解问题研究。给出了非严格偏序时态BC范式（non-strict-partially-ordered temporal Boyce-Codd normal form,NSPO TBCNF）的判定算法,提出了NSPO TBCNF分解的相关定理并最终设计了非严格偏序时态BC范式的分解方法。论文给出的全序时态模式中的成员籍算法,TFDs覆盖算法,满足全序连接无损性的全序时态BC范式的分解算法,满足保持时态函数依赖与全序无损连接性的全序时态简单范式分解算法以及强全序时态模式中混合依赖集成员籍算法和覆盖算法的时间复杂度都是多项式级的,具有很强的实用性,能有效消除全序时态模式中的时态冗余,保持全序时态模式中时态数据的一致性。论文给出的满足非严格偏序连接无损性的NSPO TBCNF分解算法,在不生成新的时态类型的条件下,可以最大限度地消除时态函数依赖约束下的非严格偏序时态模式中的时态冗余,其算法复杂度也是多项式级的。论文的研究为全序偏序时态数据库的规范化奠定了坚实的基础。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的背景及意义
• 1.2 时态数据库研究现状
• 1.2.1 时态数据库研究概况
• 1.2.2 时态数据依赖研究现状
• 1.2.3 时态范式研究现状
• 1.3 课题来源及主要研究内容
• 1.3.1 课题来源
• 1.3.2 主要研究内容
• 第2章 全序时态数据库的TFDs问题研究
• 2.1 多粒度时态数据库设计基本理论
• 2.1.1 多粒度时态数据库中基本概念
• 2.1.2 TFDs推导公理
• 2.1.3 多粒度时态数据库范式
• 2.1.4 时态类型间操作的复杂性
• 2.2 全序时态数据库中的TFDs成员籍问题
• 2.2.1 基本概念
• 2.2.2 全序时态模式中的全序TFDs推导规则
• 2.2.3 全序时态模式中属性集的闭包
• 2.2.4 全序时态模式中TFDs成员籍问题
• 2.2.5 应用实例
• 2.3 全序时态数据库的TFDs覆盖
• 2.3.1 基本概念
• 2.3.2 全序TFD集的覆盖算法
• 2.3.3 应用实例
• 2.4 本章小结
• 第3章 全序时态数据库范式
• 3.1 全序时态BC范式
• 3.1.1 基本概念
• 3.1.2 时态候选关键字集算法
• 3.1.3 全序时态BC范式分解算法
• 3.1.4 应用实例
• 3.2 全序时态简单范式
• 3.2.1 全序时态简单候选关键字集算法
• 3.2.2 全序时态简单范式判定算法
• 3.2.3 全序时态简单范式分解算法
• 3.3 本章小结
• 第4章 强全序时态模式中多值依赖问题研究
• 4.1 时态多值依赖
• 4.1.1 规则的时态多值依赖
• 4.1.2 全序RTMVD推理规则
• 4.2 RTMVD与强全序时态模块模式无损分解
• 4.3 强全序时态模式中混合依赖集成员籍
• 4.3.1 全序TFDs和RTMVDs混合推导规则
• 4.3.2 强全序时态模式中属性集的依赖基和闭包
• 4.3.3 强全序时态模式中成员籍问题
• 4.3.4 应用实例
• 4.4 全序时态混合依赖集覆盖
• 4.4.1 基本概念
• 4.4.2 全序时态混合依赖集的覆盖算法
• 4.5 本章小结
• 第5章 偏序时态模块模式的规范化
• 5.1 引言
• 5.2 偏序时态数据库中基本概念
• 5.3 非严格偏序时态模式中TFDs的闭包问题
• 5.3.1 非严格偏序时态模式中偏序TFDs推导规则
• 5.3.2 非严格偏序时态模式中属性集的闭包
• 5.3.3 应用实例
• 5.4 非严格偏序时态BC范式
• 5.4.1 基本概念
• TBCNF判定算法'>5.4.2 NSPO_TBCNF判定算法
• TBCNF分解'>5.4.3 NSPO_TBCNF分解
• 5.5 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的学术论文
• 致谢