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

应该出现在创新层面,然而在过去几十年里只表现出一小部分潜力。现在,图和图数据库彻底颠覆了这一切”。“这些行业中具有超前意识的领导者们正在从他们的对手那里赢得不可逆转的优势。图无处不在,它们正在吞噬世界,其趋势已无法逆转”。“如今,Google统治着Web搜索领域。紧随其后,其它行业领军者也开始自我检视,如今,这些问题的答案在我们的线上生活中无处不在,如FacebookTwitter及其他类似的公司”。 

其作用也如该书最后即第7章“使用图论预分析”的最后说“图是真正了不起的东西,我们对它们的了解是建立在数百年的数学和科学研究之上的。然而,我们才刚刚了解如何将它们应用到,其机会无穷无尽”。“我们用本书做一个简单的号召:拥抱图和图数据库。用你所学到的图论建模、图数据库的构架、设计和实现图数据库解决方案,以及应用图论算法解决复杂的商业问题的所有知识,去构建下一个真正的开拓性的信息系统”。不过,正如该书正文开头说这并不是一本关于图论的专门著作并注:“关于更完整的图论介绍,请参考[图论界世界第4]Gary Chartrand大师撰写的世界名著《图论导引》一书)”(这Gary Chartrand大师为第一作者的这篇论文2007我们海南省琼州大学的杂志也就是他的这篇线Radio Colorings of Graphs–A Survey论文,而海南琼大读研究生时曾百次东方麻省理工学院找资料等并读最厉害大线--其作用还可参考这里

 

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

此外,这里见给我来信和寄来他的珍贵资料的匈牙利科学院副院长、欧盟数学会主席也做数据库,就顺此介绍一些相关的基本概念和理论如Graph database下面数据库的定义可见于中科院王建方教授独立撰写的《超图的理论基础》(如第二章关系数据库或见他的《信息超图理论》)(这书有六章专题及另外有二章引言后记-其中后三章专题是哈密顿图和圈的,在最后若干讨论列出共4个猜想其中最后2个猜想是哈密顿图的,前2个猜想也与圈有关).

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

一个约简超图中,如果它的所有的块都只含有单一边,则该超图称为一个无a环超图。如此,上面结果和下面Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis命题密切:

性质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, R 2,…, R n }是数据库模式R(W,F)的一个分解,若该分解r满足保持函数依赖FD、无损联接性和3NF,则称该分解r满足P3;若分解r满足P3外还具有无a环特性,称该分解r满足P3和无a环分解。

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

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

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

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上的数据库。

关于无圈超图刻划关系数据库结构的开创性工作,见以下经典论文:

计算机诺贝尔奖得主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.

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.(下面定理见于这文。用无圈超图来刻划关系数据库结构的这几篇开创性论文是互相参考互相促进的。要打下可靠的基础,把这几篇大师的文献读好是关键。这方面国外文献也并不多,挤出部分时间就可全部读完)。下面是核心定理    

定理D={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个优秀博士中还有袁野也做不确定图数据库, 韩亚洪做基于图模型表达,  

赵克文的主页