基于时态数据库的极小子结构逻辑系统  

A Minimal Substructural Logic in Temporal Database

作　　者：刘冬宁[1,2] 汤庸[3] 滕少华[1] 林哲[2] 

机构地区：[1]广东工业大学计算机学院,广州510006 [2]中山大学逻辑与认知研究所,广州510275 [3]华南师范大学计算机学院,广州510631

出　　处：《计算机学报》2013年第8期1592-1601,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(61272067;60970044;61104156);广东省自然科学基金(10451009001004804);广东省自然基金团队研究项目(S2012030006242);广东省战略新兴产业项目(2011168005;2011A010801007);教育部重点实验室基金(110411)资助~~

摘　　要：逻辑是知识表达的重要方法,但由于时序性知识与时间属性知识交叉应用的复杂性,其对时态数据库支撑一直不尽如人意.目前时态数据运算体系不完备,时态关系演算缺乏系统和有力的逻辑与代数理论支持.为此,文中从子结构逻辑出发,针对时态数据库及其信息处理中关键的知识推理、时态操作与函数依赖等内容,构建了一个极小的(最小的)子结构逻辑系统TDLmin,其恰好等价于传统的数据库函数依赖Armstrong规则.TDLmin系统能在逻辑语义模型中对时序性、时间属性进行表达,而在句法逻辑系统将时间剥离,从而既表达了时态知识,对时态操作进行处理,又降低了逻辑系统的复杂度,使得逻辑系统的时间复杂度为P-time(O(n2)).而该逻辑系统还可与传统的Allen方法进行对接,使得相关时态查询所需的时间代价为传统非时态查询的时间加上一个复杂度仅为O(n)的线性时间,从而使得系统具有更强的普适性和应用前景.At present temporal data arithmetic system is imperfect,moreover,it is short of powerful supported by logic and algebra for the relational calculation of temporalities.Based these,we put forward a minimum substructural logic（TDLmin）,which is aimed at the critical area of research fields of temporality inference,temporality operating,temporal relational algebra and functional dependency of temporal database and its information processing.As substructural logic and its universal algebra model are logical tools,temporal knowledge is represented only in the semantics model of TDLmin,and the syntactic logic has been deprived in presentation of temporality,which is cut down the complexity of logic system so that TDLmin is P-time and its time complexity is only O（n2）.Moreover the syntactic logic of TDLmin is properly equal to the Armstrong Rules of functional dependency of traditional database,while the semantics model can build up a method corresponding to Allen ’ s Method of traditional temporal query,which led to the time cost of temporal query is equal to traditional query without temporality plusing a linear time whose complexity is only O（n）.

关 键 词：时态数据库 子结构逻辑 时态查询 函数依赖 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]