“超图”领域,最基本重要性的结果是Emanuel Sperner1928年得到基本性的无圈超图结果:n阶约化超图的边数£[nn/2];其后我们海南琼州大学证明对它发展推广到非常关键的极化无圈超图结果:即任意k划分的n阶极致约化超图的边数£[nn/2]史上十大天才的Paul Erdös以及美国科学院院士兼美国艺术与科学院院士还是奥斯卡9项提名并获3金奖的《心灵捕手》主角达蒙的天才原型Daniel J. Kleitman等很多大师在6070年已尝试证明这个结果但至今只有发表海南琼大论文的这杂志发表对它的证明)。

可参考Emil Eifrem最近的《图数据库》一书,不过,正如该书正文开头说这并不是一本关于图论的专门著作并注“关于更完整的图论介绍,请参考[图论界世界第4]Gary Chartrand大师撰写的世界名著《图论导引》一书)”(这Gary Chartrand大师为第一作者的这篇重要论文2007年就发表在我们海南琼州大学的杂志发表也就是他的这里这篇无线电Radio Colorings of Graphs–A Survey论文,而海南琼大读研究生时曾百次东方麻省理工学院找资料等并读从清华本科哈佛博士留校任教后1946年回国的该校历史上最厉害大师的多本无线电编译名著

关于我国在“超树”的奠基性就如在这页中下部分看到从中国知网见我国在80年已有十篇论文并其中6篇是海南琼州大学的导师柳柏濂教授的;而从下面C. Beeri4人得到的性质即无圈超图等同超树但也许以前少用无圈超图这个词如此在中国知网的篇名输入“无圈超图”见除一篇外2001起才开始见发表“无圈超图”论文并见如下面见在最近2009年之前我国最先十篇论文中7是海南琼州大学的导师柳柏濂教授及其他的研究生的,而这领域有许多极其关键重要的作用如在数据库理论就如《The Information Hypergraph Theory》开头说“80年代,科学家在研究数据库理论时,发现超图与数据库密切相关,但只有无圈超图在数据库理论中十分有用,而有圈超图的传统定义与数据库的性质相差甚远…”)

1、无圈超图的1—因子定理,刘桂真,数学杂志1984(02)

2(k+1)秩匀称线性无圈超图的计数公式,单志龙,柳柏濂,科学通报2000(16)

3、无圈超图的计数,王建方,李海珠,中国科学(A) 2001(01)

4、无圈超图的性质,邓志云,井冈山学院学报(自然科学版) 2006(01)期(邓志云是柳柏濂教授的研究生

5、无标号无圈超图的计数,黄俊源,华南师范大学 2007-06-01(硕士论文,看这篇论文见黄俊源是柳柏濂教授的研究生

6、无圈超图的一个充分必要条件,段广森,高继梅,河南大学学报(自然科学版) 2007(04)

7、严格(d)-连通无圈超图的计数,刘木伙,柳柏濂,数学学报2007(06)

8、真无圈超图的计数,黄俊源,惠州学院学报(自然科学版) 2009(03)期(柳柏濂教授的研究生)

9、匀称无圈超图的计数,刘木伙,柳柏濂,系统科学与数学2009(08)

10、无标号真严格(d)-连通无圈超图的计数,刘木伙,柳柏濂,应用数学学报2009(06)期。          

从下面定理数据库图式几乎等价于无圈超图”“超树,而在期刊网的上面所述,可见这些论文来自3个研究流派或说师承谱组:1、它们中的开创奠基性力量是这页中下部分我的导师柳柏濂教授和他的研究生张显坤以及最近柳教授和他的研究生单志龙院长、刘木伙、黄俊源、邓志云教授等也各合作发表多篇论文;2、另一支主要力量是中科院王建方教授和他的已任中科院数学院院长助理ORSC中国图论组合论学会理事长1995年的博士后闫桂英以及和香港李东教授、他的学生李海珠许保光的合作--刘桂真老师也有1篇而因闫桂英是她的研究生算近谱叉关系; 3、还有2001年起曾多次来信邀请五指山的我给该市唯一大学周口师范学院学报撰稿的总编段广森教授2篇(该大学4个书记6个校长算大校,该市人口8百万多海南省近5百万,段广森主编1983年至1986年在中山大学读研究生并其后也写了许多哈密顿图的论文1998年担任该学报主编-所以感谢他邀请海南山区给该学报写稿)。而我做为柳柏濂教授的研究生,又得到上面王建方教授在我尚没有和他有过任何联系的情况下的1991竟得到他主动亲自打电话给我-使我深受激励(王建方教授可是中国唯一和历史上十大天才Erdos合影并合作的科学家,也曾2次候选中科院院士,王建方教授现仍积极活跃在国际前沿就如南开大学校长陈永川院士邀请他为博士答辩委员会主席-他的四个委员中的是北美著名数学家、院士和院长更是国内领袖),如此我曾甚想更深地涉足他们的领域(另外,以无圈超图的近似特性“超树”搜索见2000年以前国内虽只有21篇论文,但其中我的导师柳柏濂教授就8篇、另有北京科技大学黄汝激教授和陈火旺院士以及孙雨耕教授等的8--虽有些交叉也足见我导师的贡献。当然就象下面看到的-在“主题”搜索不出但在正文或摘要中有的论文还有一些)。

还有,给海南琼州大学寄来他的珍贵资料的Gyula O. H. Katona院士1992Combinatorial and Algebraic Results for Database Relations或见美国MR,他是匈牙利科学院副院长、欧盟数学会主席在美国数学评论见他的数据库方面的论文有十几篇并主要是和该数学研究所的János Demetrovics合作。就顺此介绍一些相关的基本概念和理论如Graph database下面数据库的定义可见于《The Information Hypergraph超图Theory》等(如第二章标题是关系数据库)(这书有六章专题及另外有二章引言后记-其中后三章专题是哈密顿图和圈的,在最后若干讨论列出共4个猜想其中最后2个猜想是哈密顿图的,前2个猜想也与圈有关).

因一个数据库模式就是一个约简超图,如此我们海南琼州大学复旦大学校长全国政协副主席苏步青院士主编的杂志证明的这个结果较关键:一个n阶极致约化超图最多包含(nën/2û)条边(原形式是一个n-集合的最大反链的规模为(nën/2û))。

一个约简超图中,如果它的所有的块都只含有单一边,则该超图称为一个无a环超图。并Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis合作的这篇奠基性论文得到这领域的下面基本重要性定理

(可参考就这页所述:我有在海南琼州大学的导师柳柏濂教授的母校威斯康星大学任教的Raghu Ramakrishnanu大师在“数据库大师访谈”节目中他说有幸和一些大师一起工作并它列在第一的是前面开创无环数据库模型的Catriel Beeri大师并Raghu Ramakrishnanu大师和他的博士Johannes Gehrke院长的《数据库管理系统》一书由这页说90年代初回过信欢迎海南琼州大学去合作的清华大学计算机系系主任周立柱教授[参考这领域的更多代表性书籍]并见这个2006年已是雅虎副总裁的威斯康星大学教授Raghu Ramakrishnanu也是国际信息学奥林匹克竞赛第4名[第 2王小川]的现任拼多多联合创始人、董事长陈磊的博士导师[Ramakrishnanu也是拼多多创始人董事长黄峥硕士导师--黄硕士毕业就创业并刚见黄峥已是中国首富、拼多多的陈磊排在中国CEO榜第一和拼多多总市值超过阿里巴位列市值第一]-中国至今的首富只有黄峥一人在国外读书更他是在国外读研究生

定理R={R1, R 2,, R n }是一个数据库模式,HRR对应的超图,则下述命题是等价的:

(1) HR是一个无a环超图;

(2) R上的每一个两两一致的数据库也是总体一致的;

(3) HR是一个封闭无环的超图;

(4) HR是一个有弦、共形的超图

(5) R上的每一个数据库都有一个完全归约过程;

(6) Graham算法可以对HR成功完成;

(7) R有一个联接树;

(8) R有单调的联接表达式;

(9) R有一个单调的顺序联接表达式;

(10) R有运行相交性。

其中包含性质:超图是无圈超图当且仅今它是超树。(这里的无圈超图是有无圈公理定义的,超树也是定义的,如此这个结论具有基本重要性)。

定义:一个数据库模式R(R1,R2,,Rm)的超图表示HR定义如下:

(1) R(R1,R2,,Rm)中的每一个属性ai对应于超图的一个点;

(2) R(R1,R2,,Rm)中的每一个关系模式Rj对应于超图的一条边ej,即viÎej当且仅当属性ai在关系模式Rj中;

又设r={R1, R 2,…, R n }是数据库模式R(W,F)的一个分解,若该分解r满足保持函数依赖FD、无损联接性和3NF,则称该分解r满足P3;若分解r满足P3外还具有无a环特性,称该分解r满足P3和无a环分解。

性质2:当数据库模式R(W,F)DFF无内部冲突时,算法Hot-Conflict-P3-Na-FJ(W,F)可实现对R(W,F)的一个满足P3的无a环分解,算法是可终止的 ,其时间复杂度为O(m(n+m2))。其中nW中的不同属性个数,mFD的个数。

数据库模式超图的一些基本对应关系,也可参考下面论文:

马垣,属性集合函数依赖的半序同构集,计算机学报1987(10): 577-587(正如这文摘要说“我们把关系型数据库的关系模式R(U, F)F所蕴含的全部函数依赖:‘→’看作是U的幂集2U上的一个偏序,从而(2U,>是一个半序集,借助定义一种有向超图,可建立(2U,→)的一个半序同构集,而这个集以Ê为偏序,从而可把对‘→’的研究转化为对更直观、更通俗的Ê的研究,为关系型数据库函数依赖的研究提供了一种新的思路”。)

郝忠孝,郭景峰,一种基于超图的最小覆盖集求法,计算机研究与发展1990(10): 58-64

郝忠孝,刘国华,郭景峰,基于超图的环的分类有关理论,计算机研究与发展1991(08):36-41

郝忠孝,郭景峰,关系模式一种基于超图的全部候选关键字求法,计算机学报1992(04): 264-270

郝忠孝,付闯,刘国华,基于超图的关系模式到BCNF的无损连接分解,计算机研究与发展1991(08):60-66)

郭景峰,郝忠孝,基于超图的求等价属性集算法研究,计算机研究与发展1995(09)

郝忠孝,丁占鳌,刘文远,基于逆向FD超图的属性闭包求解算法研究,计算机研究与发展1994(12)(此文开头说“八十年代初期,Ronald Fagin等人提出了超图的概念并用于数据库的研究,数据库的许多特性可以方便地用对应的依赖超图来刻划。在这种研究中,一种称作“无环数据库模式”的概念被引入,由于它具有良好的特性,所以引起了计算机数据库界的广泛注意,而且一直持续至今。但Ronald Fagin等人提出的超图主要是用来表示联接依赖及研究无环数据库模式问题,使超图的表现形式及研究范围一直局限在较小的领域内”)

郭景峰,孙绍楠,杨春生,基于超图的BCNF的判定算法,东北重型机械学院学报1995(04)期;

郝忠孝,邓成玉,刘文远,关系数据库中MVD超图的讨论,计算机研究与发展1994(12)期;

郭景峰,顾和荣,邓剑华,孙绍楠,一种基于超图的关系模式主属性判定算法研究,东北重型机械学院学报1996(02)

阿姆斯特朗公理(Armstrong's Axioms)是一组用于推理数据库中函数依赖关系的基本规则。这些规则由 William W. Armstrong 1974 年提出,是形式化函数依赖的基础。

众所周知,数据库是统一管理相关数据的集合,即数据库是管理数据的,则有数据的地方就应该有数据库来对付。而数据是指使用符号记录下来的、可以识别的信息;信息则是关于现实世界事物存在方式或运动状态的反映。如此数据库在信息存储、信息传输、信息处理等领域起中心角度作用,数据库理论也成为信息科学的重要组成部分,从而数据库技术在信息产业中占重要地位:

一个数据库模式可以用一个超图来表示,而且该数据库模式的许多特性可以很方便地用对应超图的某些特征来刻画,因此,超图做为一个工具在关系数据库理论研究中发挥了重要作用。

W={A1,A2,, An}是属性集合,Dom(Ai)表示属性Ai的定义域,即Ai的所有可能取值的集合。W上的一个关系,记为R[W],是这些定义域的笛卡儿积的一个子集合。

Di=Dom(Ai), i=1,2,,n,它们的笛卡儿积记为D1´D2´´DnR[W]ÍD1´D2´´Dn。我们称n为关系R[W]的度。一个关系就是一个表,每个行称为一个tuple,每个列对应一个属性。一个关系的属性集合称为关系图式。D1´D2´´Dn是所有n-tuple(a1,a2,, an)的集合,其中aiDi。例如,若n=2D1={0,1}D2={a,b,c},则 D1´D2{(0,a),(0,b),(0,c),(1,a),(1,b},(1,c)}. {(0,a),(0,c),(1,b)}是一个关系。这个关系写成表的形式为 

A1      A2

0       a

0       c

1       b

Tuple(a1,a2,, an)n个分量,第i个分量是ai。通常我们用a1,a2,, an表示(a1,a2,, an),或简写成a

W是属性集合,WiÍW,i=1,2,, m. 如果对任意i{1,2,,m}WiÆi=1mWi=W,则我们称D={W1, W2,, Wn }W上的一个数据库图式。若RiWi上的一个系,我们称 R={R1, R2,, Rn }是在D上的数据库。

关于这领域可参考一些经典权威著作,而无圈超图刻划关系数据库结构的开创性工作,可见以下经典论文(参照《Readings In Database Systems数据库系统读物》):

博士毕业于密歇根大学的IBMEdgar Codd1981年计算机诺贝尔奖-图灵奖得主)独撰的数据库系统研究领域的开创性论文A Relational Model of Data for Large Shared Data Banks, Commun. the ACM, 13(1970), no. 6, 377–387

图灵奖得主Robert E. TarjanMihalis Yannakakis计算机大牛的论文,Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984), no. 3, 566--579.

M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin等,System R: relational approach to database managementACM Trans. Database Systems,1(1976),no.2, 97–137

1998年度的图灵奖James(Jim) N. GrayR. A. Lorie , G. R. Putzolu Granularity of locks and degrees of consistency in a shared data base,(James(Jim) N. Gray的导师Michael A. Harrison密歇根大学获得组合数学博士学位并曾是Discrete Mathematics, Discrete Applied Mathematics, Annals of Discrete Mathematics组合数学杂志编委,他的博士Oscar H. Ibarra主编《Computing and combinatorics计算与组合数学-见美国数学评论

博士毕业于密歇根大学的刚获得图灵奖的Michael Stonebraker为首的论文The design and implementation of INGRESACM Trans. Database Systems, 1(1976),no 3,189–222

David MaierJeffrey D. Ullman院士的论文,Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), no. 1-2, 185--199.Jeffrey D. Ullman院士部分博士有这里的Mihalis Yannakakis计算机大牛David Maier等,这计算机大牛其实是图论专家)

Alfred V. Aho院士, Catriel Beeri, Jeffrey D. Ullman院士的论文,The Theory of Joins in
Relational Databases
ACM Trans. Database Syst 4 (1979), 3, 297-314

Ronald FaginDegrees of acyclicity for hypergraphs and relational database schemes. J. Assoc. Comput. Mach. 30 (1983), no. 3, 514--550.

Catriel Beeri, Ronald Fagin, David Maier, Mihalis YannakakisOn the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), no. 3, 479--513.(下面定理见于这文。用无圈超图来刻划关系数据库结构的这几篇开创性论文是互相参考互相促进的。要打下可靠的基础,把这几篇大师的文献读好是关键。这方面国外文献也并不多,挤出部分时间就可全部读完)。下面是核心定理    

性质3D={W1, W2,, Wn }是在W上的一个数据库图式,则下述条件是等价的

(1) D是一个无圈超图

(2) DGraham约简是空的

(3) D是一个弦的,保形超图

(4) 连接依赖R[W1]▷◁R[W2] ▷◁▷◁R[Wm] (简记▷◁D)等价于一个多值依赖集合

(5) 连接依赖▷◁D等价于一个无冲突的多值依赖集合

(6) D上每个两两一致数据库是整体一致的

(7) D有一个连接树

(8) D有运行交性质

(9) D有一个单调连接表达式

(10) D有一个单调序列表达式

这是人们在对新型数据模型的探索中,在提出图数据模型、二元数据模型、逻辑数据模型等等中,发现超图等的独到作用才促进关系数据库的重要发展。

在我国起步虽稍晚,但其后也陆续有一些关系数据库专家的相关文献-有参考必要:

“acyclic database schemes”-“无圈-非环数据库组织在数学评论查仅见11篇论文,当然可能还有没有

中国算法研究的开拓者复旦大学朱洪大师和Li KeThe complexity of transformation from cyclic to acyclic database schemes. Comput. Artificial Intelligence 6 (1987), no. 5, 441--447.

2006年以前已以第一完成人获得20上海市及以上级别的科技奖-其中有国家科技二等奖的上海市计算机学会理事长施伯乐,“关系数据库的理论进展1987(这论文中对无环数据库的定义是“无环数据库:对于给定的模式集R1, R2, , Rk, 考虑连接依赖JD▷◁R1, R2,, Rk, 其中DJ可用一个超图来表示…”

第一个诺贝尔物理学奖获得者的大学、X射线发现地-维尔茨堡大学大师Dietmar SeipelDetlev Ruland,的论文:Designing gamma-acyclic database schemes using decomposition and augmentation techniques. Graph-theoretic concepts in computer science, 1987, 171—185

李天庆,张毅教授,许俊华, 清华大学副校长胡东成,“关系数据库理论的与或图等价性分析2001(其时的清华大学副校长胡东成等得到:有向图论一种扩充的与或图的键必对应关系数据库模式的键)

李天庆,张毅,宋靖雁,清华大学副校长胡东成与或图数据库的关系模式规范化算法2001(这论文摘要开头就说“图论基础上提出了与或图数据库。以与或图为描述工具的一种新的数据库理论,它使数据库的理论更加直观,算法更加简洁

李天庆,张毅,宋靖雁,清华大学副校长胡东成“与或图数据库的可达算法和寻根算法2001(这论文摘要说到种数据库理论采用图论作为数学基础 ,将可达算法、搜索算法和分块算法引入关系数据库 ,来解决规范化算法中关键字求解和依赖蕴涵的问题”)

简志敏胡东成,中国电子技术学科和课程建设的主要奠基人童诗白教授一般有向图法的实现及其应用

郝忠孝副校长和姚春龙教授,“The existence condition of r-acyclic database schemes with MVDs constraints. J. Comput. Sci. Tech. 17 (2002), no. 4, 517--521.

郝忠孝副校长和郭景峰教授,“关系模式一种基于超图的全部候选关键字求法2001(正文第一段说“参考文献[2]的方法这在关系数据库的理论研究和实际系统的设计中是远远不够的”,如此正如这论文摘要说“本文详细讨论了基于超图的关系模式的有关候选关键字的某些理论,给出了相应的定理.圆满地解决了关系模式全部候选关键字的求解问题

内蒙古计算机学科的铺路人叶新铭,“An algorithm for determining minimal covers of acyclic database schemes. (Chinese) Neimenggu Daxue Xuebao Ziran Kexue 25 (1994), no. 2, 219--225.

叶新铭刘铁英的An algorithm for determining minimal reduced-coverings of acyclic database schemes. J. Comput. Sci. Tech. 11 (1996), no. 4, 347--355.

国家教委科技委信息学部委员、国家有突出贡献的中青年专家冯玉才教授,“候选关键字的图论求解法(这论文摘要第一句说本文利用图论方法对求解候选关键字的”正文第一句“关系数据库的理论和实际问题中,经常要求解一个关系模式的候选关键字”)

等等……

除了超图,下面是Catriel BeeriRonald Fagin提出的数据库模式线图表示概念(即数据库模式也可以用我们海南琼州大学一直研究并发表多篇论文的线图来表示)

数据库模式R=(R1, R2, ,Rm)的线图LG(R)=(V, E, L)包含一个图G(R)=(V, E)和一个标号的集合:

1viÎV, 当且仅当RiÎRvi的标号L[vi]Ri的集合;

2e=(vi, vj)ÎE, 当且仅当vi, vj ÎE, 并且L[e]Æ,其中L[e]= L[vi]L[vj]称为的弦标号。

一个线图是将数据库模式的每个关系模式包含的属性集作为节点,以属性集间的交作为边。

要注意超图和线图的关系。

信息技术是知识经济的重要支柱,而数据库技术又是现代信息科学与技术的重要组成部分,是计算机数据处理与信息管理系统的核心。数据库技术研究和解决计算机信息处理过程中大量数据有效地组织和存储的问题。数据库系统能够减少数据存储冗余、实现数据共享、保障数据安全以及高效地检索数据和处理数据。
  随着信息处理技术与网络通讯技术的发展,数据库技术已成为信息社会对大量数据进行组织与管理的重要技术手段,是实现现代化信息管理的重要基础。
  数据库技术20世纪60年代出现,虽然历史并不长远,但是其发展速度相当快,目前已成为计算机技术发展的热点之一。在这不长的发展过程中,数据库技术的理论研究和应用系统的开发取得了很大的成就,数据库技术已成为现代计算机领域的重要组成部分。如今,在很多企事业单位都使用数据库系统进行日常事务的管理,以提高工作效率和工作质量

中国计算机学会数据库专业委员会副主任李建中校长是数学系毕业翻译世界名著《图论导引,他的最近的博士邹兆年做不确定图数据库并是中国计算机学会201210优秀博士之一,10个优秀博士中还有袁野也做不确定图数据库, 韩亚洪做基于图模型表达, 

就如最近, Neo4j公司联合创始人兼总裁Emil Eifrem最近的《图数据库》一书的序的标题是:“图正在吞噬世界,其趋势已无法逆转”,并序中说:

应该出现在创新层面,然而在过去几十年里只表现出一小部分潜力。现在,图和图数据库彻底颠覆了这一切”。“这些行业中具有超前意识的领导者们正在从他们的对手那里赢得不可逆转的优势。图无处不在,它们正在吞噬世界,其趋势已无法逆转”。“如今,Google统治着Web搜索领域。紧随其后,其它行业领军者也开始自我检视,如今,这些问题的答案在我们的线上生活中无处不在,如FacebookTwitter及其他类似的公司”;这书前言也说“GoogleFacebookTwitter都将自己的商业模式紧紧地围绕在他们专有的图论技术上”。 其作用也如该书最后即第7章“使用图论预分析”的最后说“图是真正了不起的东西,我们对它们的了解是建立在数百年的数学和科学研究之上的。然而,我们才刚刚了解如何将它们应用到,其机会无穷无尽”。“我们用本书做一个简单的号召:拥抱图和图数据库。用你所学到的图论建模、图数据库的构架、设计和实现图数据库解决方案,以及应用图论算法解决复杂的商业问题的所有知识,去构建下一个真正的开拓性的信息系统”。 可参考Emil Eifrem最近的《图数据库》一书,不过,正如该书正文开头说这并不是一本关于图论的专门著作并注:“关于更完整的图论介绍,请参考[图论界世界第4]Gary Chartrand大师撰写的世界名著《图论导引》一书)”(这Gary Chartrand大师为第一作者的这篇重要论文2007年就发表在我们海南琼州大学的杂志发表也就是他的这篇无线电Radio Colorings of Graphs–A Survey论文,而海南琼大读研究生时曾百次东方麻省理工学院找资料等并读该校最厉害大师的多本无线电编译名著--其作用还可参考这里再多说点:诺贝尔奖得主世界第2多的哥伦比亚大学的世界论网的排名可看到2000-2005年发表图论论文世界第一多的是美籍专家张萍教授,如此我其后和张教授合作发表几篇论文并得到她来信说这样高水平成果会邀请上面Gary Chartrand大师和我们合作---他俩合写了9本书--这应该是图论界最多的--在数学界也很罕见,并在维基网见只选出163个世界图论学家但只有一个华人图论学家是Ping Zhang即这张萍教授)。数据库在个行业领域的应用如刘昌孝院士主编的《药代动力学数据库.临床部分》中国医药科技出版社1994等。

赵克文的主页,可参考这页或参考这里中下部分见海南琼州大学的导师柳柏濂教授作为我国“无圈超图”“超树”主要奠基者-而基于这领域的无环数据库系统至今仍是关系数据库系统的主流,或参考更多数据库领域及其书籍等等