论述文件：数据模型比较及其在软件分析和开发中的应用

网址：http://www.elsevier.nl/locate/entcs/volume61.html13页草图数据模型、关系模式和数据规范？迈克尔·约翰逊麦考瑞大学数学与计算学院澳大利亚悉尼罗伯特·罗斯布鲁蒙特艾利森大学数学与计算机科学系NB，加拿大摘要当不同的数学模型被用于软件分析和开发时，理解它们之间的关系是很重要的。当模型是真正的数学模型时，当它们试图模拟的现实方面是共同的时，就有可能用精确的数学术语来表达它们之间的关系。本文研究了三种数据模型：草图数据模型、关系数据模型和Piessens和Steegmans的数据规范这里提出的构造合理地回答了长期存在的理论问题，并提供了在集成数据模型方面有实际用处的技术。关键词：范畴理论，数据模型，数学规范。1介绍本文是一个系列的文件中，范畴理论的方法被用来开发和应用新的数据模型的信息系统规范，开发和研究。例如，这项工作的最新结果包括视图更新问题的新处理[10]，[17]。 这种新方法已被应用于数据库互操作[16]、企业信息系统的开发[5]和软件维护[18]。此外，与我们的同事Dampney一起，这些技术已经在工业中进行了测试[3]，[8]，？ 研究部分由澳大利亚研究委员会、加拿大NSERC和奥克斯福德计算实验室支持。c2002年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。2[4]的文件。我们使用的范畴理论数据模型被称为草图数据模型随着草图数据模型的应用越来越广泛，特别是随着解决视图更新问题的新方法的发展，使用其他数据模型的实践者和理论家越来越多地寻求草图数据模型和其他数据模型之间的转换方法转换将允许草图数据模型被用作涉及其他数据模型的开发过程的一部分，并且将允许在其他数据模型中表达的问题（包括视图更新问题）被带入利用草图数据模型开发的框架中。潜在地，草图数据模型技术和结果可能被转换成从业者更熟悉的其他模型。本文所要解决的问题是明确草图数据模型与其它数据模型之间的关系。这本质上是一个需要确定数学模型之间的数学关系的理论问题目前，工业问题都是在草图数据模型中进行分析，通常没有参考其他框架中的详细模型。例如，关系数据模型和草图数据模型之间的精确连接将允许翻译现存的关系模型，从而节省相当多的开发时间。该文件的组织如下。在第2节中，我们定义了关系数据库模式和草图数据模型模式的类别我们当然不期望构造是逆的，甚至是伴随的，但我们确实给出了它们两个的合成物和各自的恒等式之间的比较映射。这给出了两个数据模型的模式之间的精确关系，但我们还需要探索它们的模型之间的关系，因此在第3节中，我们开发了某些模型（状态）的类别的等价性。关系数据库的大部分理论都是基于规范化的，在第4节中，我们展示了与草图数据模型（草图数据模型模式的实例）相对应的关系状态至少是第三范式，并指出了如何避免传递依赖的危险。这就完成了我们对关系数据模型和草图数据模型的研究，并且应该允许我们将草图数据模型与许多其他模型联系起来，因为关系数据模型是如此普遍。在处理了本文的主要问题，草图数据模型和关系数据模型之间的关系，以及通过它们其他不同的数据模型之间的关系之后，我们继续考虑草图数据模型和另一个使用草图的模型之间的关系：Piessens和Steegmans的数据规范在第5节中，我们明确了草图数据模型和数据规范之间的关系我们还指出了为什么等价失败，我们仍然得到一个密切的关系-一个等价的一个模型类别与一个完整的子类别的其他。这3-r1rr0rr--2;;;;回答了另一个长期存在的问题，即这两个密切相关但异源的数据模型之间的确切关系。最后，第六节简要回顾了相关工作，第七节做了一些总结性的评论。2关系模式和EA草图关系数据库模式的定义包括几个组件（例如，参见[11]）。在这里，我们抽象的主要项目，并描述了一类数据库方案。定义2.1一个（关系）数据库系统是一个三元组S=（D ;R;F），其中(i) D=hAdid2D是有限集合的有限族-S的域(ii) R= h1 prC rcrDirR是有限族的主键-关系方案;集合Cr的元素是表（关系）r的列标题。(iii) F=h（sf;tf;kf）if2F是四个特征定义的有限族其中Cr对所有r2R，sf;tf2R是有限的，对所有（s;t;k）2F，1kCs是有限的，cs（k）= ct（pt）。请注意，我们要求主键是一个列标题。定义末尾的等式只要求外键定义的源域和目标域相同。定义2.2数据库空间G：S的态射--一 种 S0由映射GD：D指定-- 一 种 D0，GR：R--一 种 R0，GF：F--一 种 F0 和映射族hG（r）：Cr--一 种C0iR2R其中r0=GR（r）满足(i) AGD（d）= Ad（域的相容性）(ii) GDc=c0G（r）和p0 =G（r）p（标题和主要标题的兼容性）键）(iii) 表示GF（stk） =（s0t0 k0），s0=GR（s），t0=GR（t），k0=G（s）k（com-1）外键兼容性）在下一章中，当G的分量很明显时，我们将省略上标.显然，数据库模式的态射形成了一个我们表示为DbSch的类别。一个草图[2]是由一个图、图中的一组图、图中的一组锥和图中的一组上锥组成的四元组。设表示将每个锥取到其底的函数，设表示将每个上锥取到其底的函数。我们从[19]中回忆起EA草图的定义。定义2.3EAsk etc hE=（G;D;L;R）是一种sk蚀刻，(i) 每一个在L中的n都有n（）有限;(ii) R中的每一个R都是有限且离散的;4(iii) 在G中有一个物体1，而具有空底和顶点1的圆锥在L中。5如果A是R中一个cocone的顶点，并且该cocone的底部的对象都是1，则A称为属性。G中既不是属性也不是1的节点称为实体。如果对于G中的每个实体E，存在指定的单态kE：E，则EA草图是键控的。- AE，其中AE是属性。此后，我们所有的EA草图都被假定为键控的，我们用EASk表示键控EA草图和草图态射（也保留键）的类别。我们希望比较DbSch和EASk，并最终比较它们的模型类别。我们首先注意到，从DbSch定义函子S易问。构造1：设S=（D ;R;F）是一个数据库模式。sk蚀刻S（S）具有以下组分：S（S）的基本图具有：(n1)Ad表示的节点，对于每个d 2D（n2），Cr表示的节点，对于每个r 2 R（n3），1表示的节点和(e1)对于集合Ad中的每个元素，从1到Ad(e2)对于每个x2Cr，从Cr到ACr（x）的边（e3）对于每个（s;t; f）2F。S（S）的锥L是：(c1)顶点为1(c2)Cr到Acrpr边的幺一规范S（S）的离散上锥R恰好是使Ad成为其元素之和的那些上锥。没有交换图D，每个实体的键由（c2）提供。这就完成了S（S）的构造。2重要的是要注意，我们没有添加一个节点来表示由cr确定的域的乘积。从每个关系模式的主键中产生的monic规范将保证在草图S（S）的模型中，任何实体的值都是其属性上的关系。命 题 2.4S （S ） 的 定 义 扩 展 到 DbSch的态射， 产 生 函子S ：DbSch-EASK。2在另一个方向和更感兴趣的我们的目的，我们获得了一个数据库计划，忽略大部分的约束数据的EA草图。构造2：设E=（G;D;L;R）是带键的EA_s_k_etch。数据库方案T（E）具有以下数据：6域DE的族由G的属性节点集D表示。定义属性的上锥将域集Ad指定为同构关系模式族RE 由实体的集合R表示。 F或每个r 2 R，集合Cr是G中从节点r开始的边的集合，除了那些是从r开始的交换图的一条路的边（例外在第4节中讨论）。映射cr命名具有来自r的边的属性节点，以及用于到实体的边的目标的主键属性主键是选定的monic规范。外键FE的族由G中实体之间的边的集合F来指示（除了前面段落中指出的例外）。对于每个f 2 F，sf和tf是边的源和目标，kf是与边相关联的Csf的元素这就完成了T（E）的构造。2命题2.5T（E）的定义扩展到EASk的态射，产生一个函子T：EASk-DbSch.2我们不能期望S和T之间的连接，但它们的复合与单位函子有关。首先，注意我们可以很容易地定义一个比较态射中文（简体）在DbSch中。T和S都保留属性数据，因此TS（S）的域信息正好是S的域信息。构造1为S的每个关系模式定义S（S）的实体，构造2为G的每个实体定义关系模式。因此，TS（S）的关系模式的集合与S的关系模式的集合相同。保留主键。然而，构造2在C r中引入了一个新的列标题，只要有一个来自关系模式的外键。态射CWS应该标识由此产生的新标题。最后，TS（S）的外键完全由S的外键产生。注意，因为S（S）中没有交换图，所以构造2中给出外键的边的例外不适用于S（S）。另一方面，我们有一个比较态射EA草图E ：ST（E）-- E如前所述，属性和主键数据由两个实例保留。实际上，通过构造1和2，ST（E）的基础图具有完全相同的节点G。除了构造2中的例外适用的那些边之外，它对G的每个边都有一个边。ST（E）没有E的交换图。它的有限极限约束只产生于在E中作为键出现的monic规范，它的cocones正是定义属性的那些。：7、、、--R23模型我们在本文中的兴趣仅仅是在模型中的有限集集0的范畴内的值。我们用Mod（E）表示EA草图的集合0模型的类别，在本文中不称它们为数据库状态，以便将它们与下面定义的St（S）对象区分开来。回想一下[19]，对于一个带键的EA草图E，Mod（E）是一个前序，模型的态射的所有分量都是幺一的。F或数据库方案S=（D ;R;F），我们需要定义S的状态分类，我们将其表示为St（S）。这也将是一个预排序。定义3.1S的一个态是由R所指示的关系的一族D=hDrir2R对于r2R和f=（s;t;k）2F，满足（s1）Dr有签名Cr，i. e. Dr是x2CrAcr（x）的子集(s2)（主密钥完整性）PR是密钥，即，e.下面的复合是monic：Dr，x2CrAcr（x）Acrpr(s3)（外键完整性）Ds在Ak = Apt上的投影Ds包括在kkptDt在Apt上的投影如下（其中Ds和Dt是其他两个映射在其平方中的合成的图像）DsDkDptDt___zszAAJ=塔兹一个Jz日本A2Cscs（i）cs（k）ctpt，，j2Ctct（j）定义3.2S的态DmD0的态射是族hDrmrD0irR的功能，其中包括Dr和D0的交换，在iCAi。R2R注意，mr必然是monic的。S的态和态射决定了范畴St（S）.给定具有非属性实体hErir2R的EA草图E的模型M，如何将族hM（Er）ir2R视为作为T（E）的状态的关系族是清楚的。类似地，E的模型的态射决定St（T（E））中的态射，我们得到：命题3.3如果E是EA草图，则存在完全忠实的函子C：Mod（E）- St（T（E））事实上，由于E是键控的，所以从C（M）到C（N）的任何态射都是由模型的态射产生的。还有一个函子：Mod（E）- Mod（ST（E））由草图态射（E）- E在前一节中提到。命题3.4存在范畴的等价性我E8J：St（T（E））- Mod（ST（E））9E满意的 =JC。证据如第2节末尾所述，ST（E）具有数据库方案T（E）的属性和主键数据。为了定义J，注意，作为T（E）的状态D的关系族允许将关系的域作为实体处的ST（E）的模型MD外键满足在草图ST（E）的边缘上定义模型MD，并且不存在要检查的交换性或附加限制约束。在另一个方向上，对于ST（E）的模型M，由于关键字约束，实体E处的集合M（E）肯定是T（E）中的关系模式CE的此外，模型将满足T（E）的所有外键约束，因此我们得到St（T（E））中的数据库状态DM。在等价的两边，同态由相容的monos族定义，范畴是前序。我们把所概述的结构本质上是相互对立的验证留给读者。24正常化原则上，由键控EA草图产生的数据库方案应该接近于标准化。回想一下，函数依赖性是从一组属性到另一组属性指定的草图的基础图中的节点之间的边我们有时坚持认为属性不是箭头的领域。在这种情况下，EA草图不表达任何功能依赖性，除了：(i) 从边的源的关键属性到其目标的关键属性的那些(ii) 非键属性对主键的依赖性因此，如果存在其他功能依赖，EA草图无法表达它们。这似乎是模型的一个弱点，因为我们不能期望没有这样的函数依赖。然而，如果我们假设所有的函数依赖性都由EA草图E表示，那么T（E）的关系模式将是3NF（实际上是BCNF，如果除了指定的键之外没有来自实体的monic约束）。构造2中例外的原因是为了避免在T（E）中出现传递函数依赖。当有一个交换图consisting的一个单一的边缘和另一个交换路径从实体E1的传递依赖出现。例如，假设以下E第一季第四、、、、、z你好，第二季第三在这里，如果A2和A4是E2和E4的关键属性，我们有A2-A4是一个派生的依赖关系，如果我们添加从E1到E4到CE1的单条边，它将是传递的。、10;--一 种上述情况似乎是唯一造成潜在问题的情况请注意，如果从E1到第二个实体E2有两条（或更多）边，则它们只会创建两个属性和两个外键，G.母亲孩子家长父亲此外，如果从E1出发的两条具有相同目标的路径的长度都大于1，则不会出现该问题。实际上，目标实体并不对CE1上述考虑证明：命题4.1对于EA草图E所暗示的依赖关系，数据库模式T（E）是3NF。5EA草图和数据规范在他们的文章[21，22]中，Piessens和Steegmans提出了语义数据建模的数据规范的概念。在这里，我们将数据建模视图的模型与EA草图数据模型联系起来。我们修改Piessens定义5.1数据规范（S ;A）包括(i) 有限sk蚀刻S=（G;D;L ;C）(ii) 对于V中的每个T，G的节点是一个有限集合AT，称为实体类型T的属性集，对于每个a2 AT是一个属性集ST（a），我们将这些集合表示为A（T） =a2ATST（a）。所以A可以被看作是一个函子A：V-集（V是离散范畴），它在下面的定义中使用表示明显包含I：V-G（V为离散图）和J：集合0-集合.定义5.2数据规范（S ;A）的模型是一对（M;），其中M是S在集合0中的一个模型，并且是：JMI- A是一种自然的转变。定义5.3从数据规范模型（M;）到数据规范模型（M0）的同态 是一种自然的转换：MM0满足方程$0<$IJ=<$。为了比较EA草图和数据规范，我们首先注意到，后者允许非离散cocones。我们不包括这样的cocone在EA草图，因为他们将，例如，允许约束要求识别的基本实体的值。命题5.4设（S ;A）是一个数据规范，其上锥C是圆盘。然后有一个EA草图E，使得Mod（E）等价于（S ;A）的模型范畴。11;;Pr of. 设（S ;A）为语句中的数据说明。首先通过为规范中的每个属性集ST（a）添加属性cocone来扩充其和一个从T到cocone顶点的箭头得到的草图E（SA）为;显然是EA的草图现在E（SA）的任何模型M都清楚地定义了数据规范的模型（S ;A）：将M限制为S，并使用S的M个分量来定义ST（a）美德.先知-愿状态的任何态射定义了模型的同态此外，（S ; A）的一个y模型（M;）是E（S ;A）的一个状态在刚刚定义的对应下的像。状态在S上有M的值，并且用于定义从M（T）到ST（a）的（由ST（a）构造的上锥的顶点）的所需箭头。由此我们定义了一个从Mod（E（SA））到（S ;A）的模型的函子，它在对象上是满射的.要完成所声称的等效性的证明，只需注意到对应关系是完全忠实的。2我们应该在上面明确一个稍微微妙的观点，那就是从一个状态中定义的RNT更精确（但忽略PiessensM（T）- （T）A（T）在说我们有一个函子时，我们假设iso是连贯地选择的。注意，我们在这里得到的是等价而不是同构命题5.5设E为EA草图，使得(i) 没有属性是交换图的余域(ii) 圆锥体的底部没有属性re是数据规范（SE;AE），其模型类别同构于Mod（E）.Pr of. 设E是如语句中的ERs k etch。将E修改为SE 通过移除属性，它们的定义cocones和指向它们的任何箭头。 将生成的草图称为SE。然后，对于每个剩余的实体T，以及从T到E中的属性的每个映射a，将a添加到A T并定义S T（ a ） 为 具 有 与a的上域上的属性一 样 多 的 元 素 的 集 合 。 这 定 义了（SE;AE）：现在，集合0中的E的模型M具有有限值并且满足SE的约束，使得它限制为唯一的模型ME 关于SE 在集合0中。确定了M在属性上的值在同构范围内，并且与A E一致，因此，对于2个A T组合，M（a）：M（T）-ST（a）定义了AT：ME（T）-A（T）。没有自然性条件需要检查，因此ME和AE 此外，E的模型的任意同态确定（SE;AE）的模型的唯一同态：与此同时，（S E ; A E）的n y模型（M;）可以推广到M d（E）中的模型M 0，因为假设（i）和（2）都满足：（ii）保证可使用所述CBT来在从E中删除的CBT上定义M0，模型的同态M1-M2和数据规范的通路可以扩展到E的模型的唯一态射。2对条件（i）和（ii）的需求源于我们所看到的数据规范概念中的差距。假设E1和E2是实体，A是属性;12大肠E的一个非常自然的交换性 包含一个三角形：E1f、、af，E2一vAzsJ一个数据规范模型只能通过忽略af来强加这个需求。更糟糕的是，如果A是一个交换平方或回调的余域，比如说，在它的角上有属性，那么根本没有办法允许A成为数据规范中的角的属性并强制执行约束。因此，我们只能通过削弱这些条件并使用上述结构来获得以下结果。命题5.6设E是EAs k et c h. re是数据规范（SE;AE）其模型范畴有一个同构于Mod（E）的全子范畴。6相关研究在过去的十年中，在使用范畴理论来支持语义数据建模方面有了相当大的增长Piessens和Steegmans使用如上所述的数据规范，以获得模型类别等效性的算法确定结果[21][22]，旨在支持视图集成计划。Diskin和Cadish使用草图进行各种建模，包括例如[12]和[13]。 他们一直致力于开发“图操作”的图解语言。其他一些人，包括Lippe和ter Hofstede[20]，Islam和Phoa[14]， Tuijn和Gyssens[24]，Rosebrugh和Wood[23]以及Baclawski等人[1]，一直在使用范畴理论进行数据建模。虽然这些作者中的一些人试图使用范畴理论来研究特定的数据模型，包括关系数据模型，但没有人用范畴理论的术语给出关系数据模型的精确陈述，并且据作者所知，以前没有旨在获得普通和范畴理论数据模型之间的显式翻译的（也许这并不令人惊讶，因为只有当范畴论模型在工业中得到足够广泛的应用时，这种翻译的必要性才变得明显。）与此同时，作者和其他人一直在探索草图数据模型的其他方面。Johnson、Rosebrugh和Wood发现了一个数学基础，使用统一处理数据库状态、查询语言（如[9]中所述）和更新的类别的设备，作为2类建模草图的实例[19]; Dampney和Johnson开发了一种数据库互操作技术，减少了互操作数据模型之间属性协调的需要[6];在较少的数学工作中，他们提出了类别理论数据建模技术作为信息系统研究的基础本体[7]。137结论以上提出的命题回答了激发本文的问题还有几点需要说明，可能会引起混淆。首先，我们比较了一个基于范畴理论的模型，草图数据模型，与另一个模型，关系模型，通过将后者的模式和模型表示为范畴。这并不是说，我们已经将关系模型转换为范畴论模型。相反，我们使用了数学中常见的技术，即通过研究数学结构的范畴来研究这些结构之间的关系（例如，代数拓扑研究拓扑空间的范畴、代数的范畴以及它们之间的函子这仅仅是一个偶然事件，其中一个抽象的结构，草图数据模型，已经基于范畴论。第二，在这些领域，“模型”一词明显过多。我们并没有引入新的术语来试图区分不同的用法，而是在这里将它们分类，并将其留给上下文来消除歧义。在最高层次上，寻找世界上事物的数学表示的行为被称为建模。当表示将是数据库的规范时，并且当数据库可以从特定集合中选择作为特定建模方法的一部分时，该集合及其相应的方法被称为数据模型。因此，草图数据模型和关系数据模型依赖于某些基本数据库（分别是EA草图和关系）。通常，建模工作的结果被称为数据模型。例如，关系模式有时被称为正在研究的特定现实领域的数据模型最后，一个特定的项目，例如数据库的快照，它是数据模型的实例，通常被称为模型。这最后一种用法与逻辑学和其他领域中的模型的用法一致--理论的模型。用一个例子来总结：引用[1] K. Baclawski，D. Simovici和W.白.数据库语义的分类方法。计算机科学中的数学结构，4：147[2] M. Barr和C.井计算科学的范畴理论。Prentice-Hall，第二版，1995年。[3] C. N. G.丹普尼和迈克尔·约翰逊。符合时间标准的企业数据模型验证。顾问[4] C. N. G.丹普尼和迈克尔·约翰逊。纤维化和DoH数据模型。顾问14[5] C. N. G. 丹普尼和迈克尔·约翰逊。企业信息系统：使用范畴理论分析项目数据模型之间的联系。企业信息系统国际会议论文集[6] C. N. G.丹普尼和迈克尔·约翰逊。协作信息系统的半双工互操作。《并行工程进展》，IN-1，7页，国际并行工程研究所，ISBN 09710461-0-7，2001年。[7] C. N. G.丹普尼和迈克尔·约翰逊。论范畴论作为信息系统研究的（Meta）本体论。信息系统中的形式本体论（FOIS），缅因州，2001年10月，ACM出版社。[8] C. N. G. Dampney，Michael Johnson和G. M.麦格拉斯审计和加强加德士信息战略规划项目。顾问[9] C. N. G. Dampney，Michael Johnson，and G. P. Monro。一个图解的数学基础ERA。统一计算实验室，第77-84页，牛津大学出版社，1992年[10] C. N. G. Dampney，Michael Johnson，and Robert Rosebrugh.在语义数据模型范例中查看更新。ADC 2001，29[11] C. J.日期。数据库系统导论，第六版。Addison-Wesley，1995年。[12] 齐诺维·迪斯金和鲍里斯·卡迪什。基于代数图的多数据库系统管理方法。第二届下一代信息技术和系统国际研讨会'95），1995年[13] 齐诺维·迪斯金和鲍里斯·卡迪什。广义草图的变量集语义：为什么ER比OO更面向对象。数据与知识工程，2000年。[14] A.伊斯兰教与W. Phoa.关系数据库的范畴模型I：Fibrational Formulation，Schema Integration。TACS94会议记录。Eds M. Hagiya和J. C.米切尔计算机科学讲义，789：618[15] Michael Johnson和C. N. G.丹普尼 关于交换图的值信息建模。统一计算实验室，Rattray和Clarke编，Springer Workshops in Computing，77-[16] 迈克尔·约翰逊和罗伯特·罗斯布鲁。通过基于状态的逻辑数据独立性实现数据库互操作性。International Journal of Computer Applications in Technology，inpress，2001.[17] 迈克尔·约翰逊和罗伯特·罗斯布鲁。查看基于正式规范模型的可更新性。Proceedings of Formal Methods Europe 2001 ， 534-549 ， Lecture Notes inComputer Science2021，2001.[18] 迈克尔·约翰逊和罗伯特·罗斯布鲁。基于互联网互操作的遗留信息系统逆向工程。2001年11月在佛罗伦萨举行的软件维护国际会议的新闻稿15[19] 迈克尔·约翰逊、罗伯特·罗斯布鲁和R. J·伍德权限-关系-属性模型和草图。分类理论与应用Theory and Applications ofCategories[20] E. Lippe和A ter Hofstede。概念数据建模的范畴理论方法。RAIRO TheoreticalInformatics and Applications，30：31[21] Frank Piessens和Eric Steegmans分类数据规格。《范畴理论与应用》，1：156[22] Frank Piessens和Eric Steegmans分类数据规范的选择性属性消除第六届国际AMAST会议录。编. Michael JohnsonLecture Notes in Computer Science，1349：424-436，1997.[23] Robert Rosebrugh和R.J. 木材. 关系数据库和索引类别。在CMS Conference Proceedings，13：391[24] C. Tuijn和M.吉森斯CGOOD是一种面向分类图的对象数据模型。理论计算机科学，160：217-239，1996。