296网址：http://www.elsevier.nl/locate/entcs/volume67.html17页面向对象数据库中的可计算查询FINSET案例Klaus-Dieter Schewe，Jose-Maria Turull-Torres梅西大学信息系统系，Private Bag 11222，Palmerston North，NZ [k.d.schewejj.m.turull]@massey.ac.nz摘要关系数据库可以被认为是一阶逻辑中的nite关系签名的nite结构，即，没有功能符号。 在这样的结构中解释这个签名上的逻辑允许详细研究查询的表达能力和复杂性。这是尼特模型理论的起点，尼特模型理论已被证明是研究关系数据库理论的可行工具。特别地，已知表示为保同构的部分递归函数的可计算查询可以由相关关系机形式化。这些是扩展的图灵机，具有额外的关系存储，查询磁带和在单个步骤中针对存储中的数据库评估磁带上的查询的设施。在本文中，我们开始推广的理论后关系数据库。我们首先考虑具有基于集合的复杂值和引用的情况，使得语义仍然可以用集合来表达遵循的方法，面向对象的数据库一般包括那些，其中底层类型系统不再允许语义定义的集合，可以表示为理论在高阶直觉逻辑，我们使用这样的逻辑，而不是一阶逻辑。然而，由于我们还没有充分利用这种逻辑的全部功能，我们可以解释nite集合的FINSET类别中的逻辑，即，同样在由数据库定义的结构中。这样，可计算查询的定义和相关关系机的模型就很容易继承了。我们可以证明，新模型的相关对象机保证完整性，即，所有可计算的查询都可以由该模型表示。关键词：可计算查询，面向对象数据库，反应机，尼特模型理论2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。2971引言数据库理论主要是关系数据模型理论. 因为数据库模式可以简单地由一组关系定义， 符号，我们可以考虑一阶逻辑中的关系签名。 由于给定数据库模式上的数据库是由节点关系给出的，这样的数据库只是一个节点结构，其中可以解释由签名定义的逻辑。通过这种方式，逻辑以自然的方式定义了查询语言，这导致了尼特模型理论[6，13]。为了获得更有表现力的查询语言，已经研究了将这种简单查询与可计算函数相结合的几种形式。这导致了可计算查询[9，10]。粗略地说，可计算函数和可计算查询之间的主要区别在于，对于后者，我们希望域的排列与查询交换。我们说计算保持同构。我们说某种形式是完备的，因为它能表示所有的可计算查询。为了找到表达可计算查询的完整形式，[9，10]中的工作引入了抽象程序设计语言QL和RQL。替代的形式主义是关系机器（RM）[2，3，4]|然而，RMs的模型并不完整|相关关系机器（RRM）[1，5]。关系机是一个图灵机，由一个只能通过一阶查询访问的关系存储扩展一个关系型关系机通过一个额外的查询带扩展了一个关系机，该查询带用于计算要针对关系存储进行评估的查询。Nite模型理论的框架允许对逻辑进行限制和扩展，从而导致具有不同复杂性结果的不同查询语言。因此，我们可以对查询进行分类。 另一方面，我们可以研究数据库的属性，允许较弱的逻辑是完整的，如果仅限于满足这些属性的数据库。到目前为止，尼特模型理论已经导致了关于关系数据模型理论的知识的显著增加[2，3，4，24，25，26]。当从关系模型转移到更通用的数据模型时，例如，[2019 - 07 -17][2019 - 07][由于扩展的要点涉及有理树，类型和（多态）函数，因此用相应的topos来代替nite集似乎是合理的，topos用于定义底层类型系统的语义。粗略地说，topos是一个具有内部非经典逻辑的集合的直觉论宇宙[8，14，21，22]。最有趣的例子是从逻辑的角度研究递归理论的有效topos [18]。它也被成功地用于定义高阶类型化编程语言的语义。在本文中，我们从最简单的情况开始。我们选择底层类型系统来只提供一个记录和一个nite set构造函数。我们还省去了各种各样的基类型，只是将模型简化为一个基类型298B表示值，另一个基类型ID表示对象标识符。然后我们可以选择有限集合的FINSET范畴|事实上，FINSET是一个拓扑|用于表达数据库模式的语义。特别是，从nite值和标识符集合开始是在此基础上，我们回顾了第2节中数据模型的基本概念，并定义了数据库和可计算查询之间的同构我们回顾了高阶直觉逻辑的解释，[14]这是一个很好的例子。然而，我们只考虑拓扑FINSET，在这种情况下，逻辑变得相当经典。根据[21，22]中的工作，我们知道OODB模式和Fourman-Scott语言的签名之间的关系。我们利用这种关系，在我们的限制性的上下文中，以显示如何考虑一个数据库作为一个结构的逻辑解释。与关系情况类似，这定义了简单的查询，可以证明其具有与[23]中研究的查询代数相同的可表达性在第4节中，我们讨论了相对关系机模型的推广。原则上，关系对象机的构造没有太大的不同，主要的不同是关系存储必须由对象存储代替，并且查询带必须包含相应的Fourman-Scott语言中的简单逻辑查询（的编码）利用该模型，可以实现完整性结果，即， 相对对象机能够表达所有针对简单的面向对象数据库的可计算查询。最后，第5节包含一个示例来说明如何将逻辑用作查询语言。我们将只简略地介绍相对对象机的使用，因为在图灵机的水平上看计算通常是很尴尬的。最后，我们做了一个简短的总结，并描述了未来的计划。2面向对象的数据库正如在引言中所宣布的，我们想考虑[20]中介绍的OODM的一个非常简单的版本。我们将不考虑子类或操作，我们将只考虑一个简单的基础类型系统，只使用一个记录和一个集合类型构造函数。但是，我们保留类之间的引用。至于语义，我们不必看有理树，尽管我们知道它们是模型的要点，如[20]所示。我们简单地考虑具有对象标识符的数据库，知道标识符只是一个实现概念[7]，这当然会在数据库同构的定义中得到反映。2992.1数据模型在[20]之后，我们从底层类型系统表达的值的级别开始。使用抽象语法，我们的类型系统可以被描述为t=Bjxjt1tnjftgjID：这里，B表示单个基类型，ID是对象标识符的类型。x表示类型变量，给出一个（匿名）记录构造函数，f g给出一个nite set构造函数。没有ID的类型称为值类型。 的变量 类型中的参数称为类型的参数的语义类型t，参数为x ;：;x定义为映射（t）：FINSET n！1NFINSET定义如下：对于B和ID，我们有（B）=V和（ID）=O，其中有两个nite，不相交的集合V和O。关于类型变量是身份映射。F或记录ty pes有ve（t1tn）（X）=（t1）（X1）（tn）（Xn），其中Xi是X到ti中参数的投影。对于集合类型，我们有（f t g）（X）= P（（t）（X））和幂集算子P。定义2.1类C由结构表达式exp C定义，它本身是由值类型t将t中的所有参数xi替换为具有成对不同引用名称r i和类名C i的对r i：C i而产生的。我们说r i是从类C到类C i的引用。类C的表示类型tC通过将所有参数替换为类型ID而从t一个数据库模式是一个类的集合S，对于所有的C2 S和从C到Ci的所有引用，我们也有Ci2 S。至于语义，我们必须在给定的数据库模式S上定义数据库在不涉及形式细节的情况下，我们将对所有引用使用出现关系或。如果t0 是一个无参数的ty pe发生在一个无参数的ty pet中，那么这就定义了一个二元关系t;t0 on（t）（t0）with（v;v0）2ot;t0 iv0在发生t0时所指示的位置处， 于t. 特别地，从C到C i的每个引用ri定义t C和ID之间的这种出现关系。 我们用y或i来表示这个发生关系。定义2.2数据库模式S上的数据库D是集合D（C）O（tC）的S-索引族，使得对11个类C，当（i;v）2D（C）和（i;v0）2D（C）成立时，则v=v0;对于从C到Ci的所有关系，只要（i;v）2D（C）和（v;j）2或ri成立，则re是某个（j;v0）2D（Ci）。300设ty pest=ft0g wede ne：P（（t0））！P（（t0））by（fv; ：; vg）=2.2可计算的[9，10]中定义的关系数据模型的可计算查询的概念依赖于同构数据库的概念。对于关系数据模型，这很容易通过排列关系中的值来定义。对于面向对象的数据库，情况稍微复杂一些，因为我们必须区分标识符和（复杂的）值。特别地，如[7]所示，我们应该考虑从标识符的排列中产生的数据库不仅是同构的，而且甚至是相等的。如果有一个非平凡的标识符置换，保持给定的数据库，那么它是不可能唯一地识别对象。因此，数据库更新不是唯一定义的。由于我们只处理查询，因此可以忽略此问题。我们只需要考虑值和标识符的排列定义2.3让类型系统的两个不同语义定义为1和2. 1和2之间的t-同构是一对双射映射：1（ID ）！ 2（ID）和：1（B）！ 2（B）。很容易看出，t-同构=（';）扩展到无参数类型t，如下所示：F或t =IDweh ee（i）='（i）。对于t = B，我们有 （v）=（v）。记录ty pest=（t1tn）wede ne：1（t1）1（tn）！2（t1）2（tn）by（v1; ：;vn）=（（v1）; ： ;（vn））.f（v1）; ：;（vk）g.1 2 1k对于数据库D，我们有D（C）2（fID tC g），t-同构也定义了从语义1上的S-数据库到语义2上的S-数据库的映射。 我们也用y=（';）表示这个映射，称它为S-同构。定义2.4同一数据库模式S上的两个数据库 D1和 D2是同构的（记为：D1'D2），如果从D1存在一个S-同构 到D2。现在可计算查询的定义是直接的，因为[9]的推广只需要保持同构。我们使用D（S）来表示模式S上所有数据库的集合定义2.5对数据库模式S的可计算查询，输出模式为S 是一个偏序递归函数q：D（S）！ D（S0）将同构数据库映射到同构数据库，即，D1'D2^q（D1）#）q（D2）#^q（D1）'q（D2）：在最后一个定义中，q（D1）#表示部分映射q是在D1上定义的.3013逻辑在[21，22]中，已经展示了如何使用Fourman和Scott对这种逻辑的方法[14]将数据库视为高阶直觉逻辑中的理论。我们简要回顾这些逻辑，并集中在FINSET的解释，这将使我们能够查看数据库作为合适的结构，这些逻辑的解释。3.1Fourman-Scott语言本文首先介绍Fourman-Scott语言的一般情况。定义3.1Fourman-Scott签名L包括：两组排序和常量的Sort和Const，a powwersortmap[]：Sn2NSortn！写好了（A1; ：;AN）7！[A1; ： ：;An]，一个由排序和a map #：Const！给每个常量指定其排序。我们还使用Var=Ss2SortVars来表示所有变量的集合。然后对于一个给定的变量x2V ar，我们写#x来表示x的排序。此外，委员会认为，我们使用f =[]作为空幂排序的缩写，它将被视为由真值组成。定义3.2Sort的项Ts（L）对于签名L的Sort是从L作为最小集合构造的，使得sort的每个变量x，每个常数c，其中#c= s和Ix：'对于每个变量x，其中#x=s和每个公式'属于Ts（L）。L上的公式建立最小集合F（L），使得以下公式在F（L）中：E为每项2 T（L），对于术语，相同类型的，（1; ：;n）对于项i2Tsi（L）和2T[s1;：;sn]（L），'^for formulas'和，'）对于公式'和8 x：'for variables x 2 V ar and formulas'.描述符号I背后的内涵需要一些解释。非正式的Ix：'意味着满足的唯一x'。 但是，这样的人可能并不存在。逻辑处理这个问题，通过引入一个正式的存在predicate E，其中E的意思是存在。这是通过区分可能元素的域A~，并让E_pic_k表示实际元素的子域，元素 那么绑定变量的范围将只覆盖实际元素。302一个存在谓词的引入也影响了被认为是实际元素的一个属性的等式pred- icate =。为了比较可能的元素，引入了等价谓词。不存在的元素都被认为是等效的。从那时起，平等可以根据等价和存在谓词来定义，只有在逻辑中被视为一个原语。在[21，22]中，我们已经证明了我们总是可以用这样的方法来重新定义OODB：将类C视为排序 [ID;T~C]的常数，将从C到D 的引用视为排序[T~C;[T~D]]的常数。3.2FINSET口译根据[14]，我们可以在任何topos中解释Fourman-Scott语言。这里我们只考虑nite集的topos FINSET。在这种情况下，真值对象是= fT; F g，平凡布尔代数。另外对于eachsetA的扩张是简单的A~=A[f1 g定义3.3签名的结构（Sort; Const）为每个sort 2分配一个集合As，并为sort s的每个常数c分配一个元素ac2A~s。结 构 可 以 扩 展 为 项 和 公 式 。 为 此 ， 考 虑 变 量 的 序 列 % ， s ay%=（x1; ： ：;xn），其中xi2Varsi。 德内X%=A~s1 A~sn. 映射I%（）的排序条件：X%！ A~s.F或mulae'de nemappingsI%（'）：X%！ . 这些定义如下：对于常数项c，我们得到I%（c）（a1; ：;ann）=c;对于变量x=xi，我们得到I%（x）（a1; ：;ann）=ai;任期=I x：'对于排序为s的x，我们得到I%fxg（Ix：'）（a1; ： ： ：;ai1;ai+1; ： ： ：;an）=aiffag=faijI%（'）（a1; ：;an）=Tg1人对于一个公式'=E，我们得到I%（E）（a1; ：;an）=Tif I%（）（ a1;：; an）2As Felseforaformula'=（1; ：;n）withiofsortsiandofsort[s1; ：;sn]（（3038>：我们得到I%（（1; ：;n））（a1; ：;an）=Tif（I%（1）（a1; ：;an）; ：;>：TifI%（'）（a1; ： ： ：;an）=I%（）（a1; ：;an）=T其他对于公式“），我们得到I%（“））（a1; ：;an）=F，如果I%（n）（a1; ：;an）=T，并且其他对于公式8x：'，其中x= xi，排序为 sI%fxg（8x：'）（a1; ：;ai1;ai+1; ：;an）=TifI%（'）（a1; ：;an）=Tforallai2AsFelse在[14]之后，我们还可以使用以下附加公式作为捷径：为为^E ^E;publicintfindDuplicate（）;'_for8z：（'）z（））^（）z（））z（）;9x：'for8z：（8x：'）z（））z（）;'，for'）^）'。（（其他3043.3作为结构的基于我们的知识，在FINSET中Fourman-Scott语言的解释与[21，22]中的一般情况相比变得相当简单，我们现在也可以简化OODB作为逻辑结构的处理作为排序的集合，我们必须选择包含排序B和ID的最小集合，该集合在幂排序映射[ ]下是封闭的。通过这种方式，我们捕获了底层类型系统的所有类型。我们可以选择任意数量的B类常数。此外，我们必须为每个类C2 S选择一个排序常数[ID;TC]. 这就完成了签名的定义。然后，通过模式S上的数据库D以通常的方式确定结构。排序ID由对象标识符的集合O解释。排序B由与O不相交的集合V解释。幂排序映射使用i解释P（As1 Asn）对于powersort[s1; ：;sn]，假设si由iyAsi解释。B类的常数要么由V中的某个值解释， 或左Under ned，aswehaveeV~=V [f1g. 常数C2C由数据库D中的值D（C注意，这种定义可以用D解释的逻辑查询语言的方式不包括创建新的标识符。我们在最后一节对此至于Fourman-Scott逻辑的表现力，下一个结果是直接的。它从塔函数1是原始递归的，但不是Kalmar（[12]）意义上的初等的事实得出，并且从以下事实得出：阶逻辑精确地表示Kalmar初等函数类（[19]，[17]）。命题3.4 Fourman-Scott逻辑是不完整的。此外，在Fourman-Scott逻辑中可表达的查询类严格包含在原始递归函数类中。24相关对象机器现在让我们解决一个形式主义，使我们能够表达可计算的查询。我们选择推广相关关系机器的模型[1，5]。4.1机器模型关联机的模型是基于图灵机的模型。然而，由于图灵机不能保证保持同构，因此对数据库的访问以不同的方式处理。基本上，该模型通过关系存储进行扩展，其中可以存储任何元的关系。最初，该存储将包含必须对其进行查询评估的数据库。1f（1）=2，f（n）=2f （n1），如果n2.305QQQ12此外，该模型具有用于存储简单查询的单独查询带，即，逻辑公式，针对关系存储。该机器从空磁带开始，像普通图灵机一样工作，具有特殊的查询评估状态，其中查询磁带上的查询在将结果添加到关系存储的单个步骤为了推广这个模型，我们首先需要对关系存储进行推广。很明显，初始内容应该是一个S数据库。根据[27]，我们可以通过连续添加新类和扩展数据库来考虑查询评估。因此，对象存储必须始终包含完整的面向对象的数据库。定义4.1设S是一个数据库模式。 考虑D= SSS0D（S 0）. An基于S的对象存储是一种可以包含D中任何数据库的存储。现在我们可以形式化一个对象机器的模型。为此，我们保留上一个定义中的符号。 另外，设S=fS0jSS0g表示扩展给定数据库模式S的所有数据库模式的集合。定义4.2数据库模式S上的相关对象机 R包括表示为Q的状态的集合，包含三个两两不同的状态z0 （初始状态）、zt（终止状态）和q（查询状态）;两个字母B和Bq，都包含一个特殊的空白符号2和至少一个以上符号;转换功能：QBB ！QBBfL;R;Og2;一个部分查询转换函数q：B SD！SD满足以下条件：Di必须是模式Si上的数据库;S1S2;w必须编码一个公式，该公式被用作对S1上的数据库的查询，使得该查询针对D1的求值 结果在扩展的数据库D2中。我们写R=（Q;z0;q;zt;B;Bq;2;n;nq）。4.2完整性相关对象机的处理类似于图灵机或相关关系机的处理来描述。我们考虑这些之间的配置和过渡。 一种配置是一个四元组（w1zw2;w0“w0;S0;D0），使得下面的翼成立：W1;W22B，其中W1W2描述了具有指向W 2的第一系统的读写头的工作过程的内容;z2Q表示实际状态;3062w 0; w 0 2B，使得w0 w0描述了查询磁带的内容，12q12读写磁头指向w0的第一个符号;S 02 S描述数据库模式，D 02 D描述S 0数据库，它们一起描述对象存储的实际状态。初始构型为（z0;“;S; D）。对于z=zt，我们有一个最终配置，在这种情况下，D0是查询结果。对于z=q，我们有一个查询配置。转换函数f通常描述磁带的状态和内容的变化，包括读写磁头的可能移动。除非我们有一个查询配置，否则这个定义配置会随着S0和D0的变化而在查询配置的情况下，函数应用于（w 0w 0; S0; D0）以完成配置转换。q12现在我们可以陈述一个与我们的广义理论有关的结果定理4.3相对对象机的模型是完备的，即，它能够表示所有可计算的查询。该证明类似于利用结构图的相关关系机的完备性证明，从标准模型理论[11]推广。定义4.4设S=fC1; ：;C是一个数据库模式，D是S上的一个数据库. D的图（表示为D）是Fourman-Scott逻辑中的一个句子，其形 式 为D=9x1; ：;xn;y1; ：;ym：^'^：^^si ^^si'22sis i但须符合下列条件：(i) 考虑从所有表示类型TC和C2S（包括排序B）的所有超类型产生的所有排序si。对于每一个这样排序的值s i，都有一个变量x j：si。(ii) 对于任何类C2 S中的每个元素（i; v）2D（C），都有一个变量yi，其排序ID为它的对象标识符。(iii) 数据库D上的原子是针对每个变量 xi ：s的式xi（z1; ：;zr），其中s=[s1; ： ：;sr]并且所有变量zi：si。 设表示D上满足D的所有原子的集合，设表示所有剩余原子的集合。(iv) 对于（i）中使用的每一种si， 表示所有变量x j：s i对应于D中的不同值。(v) 对于（i）中使用的每一种si， 表示赋值给所有变量x j：s i的值是排序的唯一值i在D中。注意D是一个单一的句子，它是一个规范的表示，307QQQQS-具有输出-s表的数据库S0=fD; ：; Dg. 然后，有一个图灵Q0QQQ数据库D，即，我们有D1'D2 ，D2j=D1：这一事实的证明是直截了当的。现在我们可以用图解证明定理4.3。证据（定理4.3）它可以直接证明由对象机计算的查询是可计算查询。由于基本模型是图灵机，我们可以很容易地将对象存储编码在单独的磁带上。因此，我们得到一个部分递归函数。为了保持同构，我们只需要考虑用逻辑公式表示的基本查询，但对于这些，证明是显而易见的。因 此 ， 让 我 们 把 注 意 力 集 中 在 证 明 的 相 反 方 向 上 。 设 S=fC1; ： ： ：;Cs g是一个数据库表，设q是一个针对1 r马庆明 其中CH计算Q。 我们必须构造一个对象机M0，它计算q.0 开始在其磁带上编码输入数据库D（在其对象存储中）。然后， 工作原理如下：(i) F或eachpossibleS-数据库D0的大小（分别考虑原子值的数量和对象标识符的数量）在它的磁带上编码图表D0.(ii) M0一个接一个地使用这些图作为对对象存储的布尔查询，直到它得到答案T。根据上面提到的事实，这意味着确定与对象存储中的数据库同构的数据库的图。(iii) 现在使用图D0 机器M编码D0在它的磁带中，图中变量的索引作为编码中原子排序的元素。(iv) 下一个，模拟Mq的执行在它的磁带中使用作为输入D0的编码 并在其映射上给出结果q（D0）。 从而得到了一个S0-数据库D00的编码.(v) M生成图D00在它的磁带上，除了它留下自由的对应于类D; ：; D2S0，s ayx; ：; x的变量。1 r 1 r0(vi) 最后，M 评估D00 作为查询。根据上述事实上述查询的评估结果是同构于q（D）的数据库。2M0MQ03085例如让我们考虑一个由四个类组成的小型OODM模式对于这些，我们使用符号C=expC。为了可读性，我们在记录类型中使用eld名称。如果没有指示与这些eld名称关联的类型，则该类型是基类型B。部门=（D姓名，负责人：讲师）讲师=（姓名，部门：部门，参与：f项目：项目g）学生=（学号，姓名，专业：系，主管：讲师）项目=（项目编号，标题，学生：fP学生：学生g）这将导致以下表示类型：T部门 =BIDT讲师=BIDfIDgT学生=BBID ID T项目=BBIDg在Fourman-Scott逻辑中表示模式导致以下四个常量：D：[ID;[B;ID]]L：[ID;[B;ID;[ID]]S：[ID;[B;B;ID;ID]]P：[ID;[B;B;[ID]]3090000有了这些变量，我们可以制定数据库必须满足的常见约束（标识符的唯一性，引用完整性）：8 i; j; xD; yD：D（i; xD）^D（j; yD）^iJ）xDyD（1）8i;j;xL;yL：L（i;xL）^L（j;yL）^ij）xL（2）8 i; j; xS; yS：S（i; xS）^S（j; yS）^iJ）xS（3）8 i; j; xP; yP：P（i; xP）^P（j; yP）^iJ）xPyP（4）8i;xD;d1;d2;h1;h2：D（i;xD）^xD（d1;h1）^xD（d2;h2））d1d2^h1h2（5）8i; xL;n1;n2;j1;j2;p1;p2：L（i; xL）^xL（n1;j1;p1）^xL（n2;j2;p2））n1n2^j1j2^p1p2（6）0 08i;xS;n1;n2;n1;n2;j1;j2;k1;k2：S（i;xS）^0 0xS（n1;n1;j1;k1）^ xS（n2;n2;j2;k2）0 0）n1n2^n1n2^j1j2^k1k2（7）8i;xP;n1;n2;t1;t2;s1;s2：P（i;xP）^xP（n1;t1;s1）^xP（n2;t2;s2））n1n2^t1t2^s1s2（8）现在让我们看看下面的查询：列出每个部门的学生参与任何项目，他们的主管参与。实际上，我们希望通过一个新类来扩展模式PStudent=（部门：部门，fP学生：学生g）所以，我们又是一个变量[ID;[ID;[ID]。 让这成为一个。那么查询可以公式化为Ia：（8i; b：a（i; b），b= Ix：（8z：x（i; z））9y：D（i; y）^8j：（z（j），9s：S（j; s）^9n; n;k：s（n;n; i;k）^9`：L（k;`）^9p; m：`（m; p）^8i：（p（i））0 0 0 0 0 09q：P（i; q）^9p; t;s：q（p; t;s）^s（j）请注意，在这个阶段，我们并不建议在实践中鼓励以无限制的方式使用Fourman-Scott逻辑（如本例中所做的）。310进一步注意，在这个例子中，我们没有创建新的标识符。我们将在下一节中考虑这一方面。3116结论在本文中，我们讨论了尼特模型理论的推广及其在关系数据库中的应用。代替关系数据模型，我们考虑了一个非常简单的面向对象数据模型的变体，它只使用一个记录和一个集合类型构造函数以及一个除了对象标识符类型之外的基本类型。我们还省略了子类化。这个模型与[16，17]中研究的模型非常相似。主要的区别是类之间引用的合并，这是通过使用对象标识符来实现的。从一般理论[20]中我们知道，这相当于允许某种无限但无限可表示的结构|准确地说，是合理的树形结构|被利用对于这个模型，我们能够概括可计算查询的关键概念。我们还可以将关系机器的模型推广到关系对象机器，这给了我们一个表达所有可计算查询的形式主义。本文中报告的工作是一个更大的项目的一部分，该项目致力于将Nite模型理论推广到非标准数据库。正如在[21]中指出的，我们可以选择任何合理的类型系统作为起点。一个类型系统被认为是合理的，如果它的语义可以在某些主题中定义。 这包括迄今为止研究过的所有类型系统in the context上下文of programming编程language语言.如果我们更进一步，从topos FINSET切换到topos SET，我们可以包括创建新的对象标识符，以及其他更高级的功能。根据[23]，创建新的标识符对于查询具有引用的数据库至关重要，除非我们切换到使用有理树的接下来，我们将大致解释如何做到这一点。在每个数据库D中，我们让对象标识符的集合O在nite中可数。 对于每个模式S，我们定义D（S）中的等价关系id如下：两个数据库是等价的i，它们具有相同的对象标识符集合O和相同的原子值集合V，并且如果它们通过V中的恒等关系S-同构而同构。然后，对于一个被认为是可计算的查询，我们要求，每当查询是在两个同构的数据库进行评估，同构可以扩展（纳入新创建的对象标识符），以这样一种方式，所得到的数据库是同构通过原始同构，模id的扩展。 然后我们可以在这种环境下定义一个对象机器，这也是完整的。这将给我们某种在[15]意义上的Meta结构。然而，我们的主要兴趣是关注非谓词多态性[21，22]，因为它允许可计算函数和泛函被用作数据。这使得能够在数据库中表示和存储来自分子生物学、遗传学、地球科学、环境科学、化学等的科学数据。它可以用于，例如，用来描述地震，火山，细胞312过程或化学反应。这种类型系统的语义超出了集合论。我们必须考虑一个更复杂的拓扑，有效的拓扑E[18]，但我们坚信，该理论可以推广和富有成效地应用在这些一般条件下。一旦我们能够在E中定义Nite模型的类似物，我们就可以再次研究用于表达可计算查询的完整这将是使用nite模型理论工具的基础，以深入理解查询及其在后关系数据库环境中的复杂性。引用[1] S.阿比特布尔角Papadimitriou，V. Vianu.相关关系机器的力量。Proc.LICS 1994年。[2] S. Abiteboul，V. Vianu.用一阶逻辑计算计算机与系统科学杂志。卷50（2），309-335，1995.[3] S. Abiteboul，M. Vardi，V. Vianu.用抽象逻辑计算。理论计算机科学第149（1）卷，第101-128页，1995年。[4] S. Abiteboul，M. Vardi，V. Vianu.不动点逻辑、关系机器和计算复杂性。ACM杂志卷44（1），30-56，1997.[5] S.阿比特布尔角Papadimitriou，V. Vianu.相关关系机器。信息与计算卷143，110-136，1998。[6] J. Barwise，S.Feferman（编）.模型理论逻辑。Springer-Verlag 1985.[7] C.贝里湾塔尔海姆作为数据库模型原语的标识。于T. Polle等人（编）。信息系统基础 Kluwer 1999，19-36.[8] A. Boileau，A.乔亚尔地形学符号逻辑杂志第46（1）卷，1981，6-16。[9] A.钱德拉角哈雷尔关系型数据库的可计算表示。计算机与系统科学杂志卷1980年21日[10] A.钱德拉角哈雷尔关系数据库的结构和复杂性。计算机与系统科学杂志卷1982年25日[11] C. Chang，H. 凯斯勒模型理论第三版， Elsevier North Holland，1992年。[12] N.卡特兰可计算性：递归函数理论导论。剑桥大学出版社，1980年。[13] H.- D. Ebbinghaus，J. Flum.有限模型理论月2编辑，Springer-Verlag 1999.[14] M.P.福曼Topoi的逻辑在J. Barwise（编辑）：数学逻辑手册。北荷兰研究逻辑卷。90，1977，1053-1090313[15] E. Gradel，Y. Gurevi ch. MetaniteM o delTheor y. InD. Lei va nt（Ed.）.逻辑和计算复杂性。Springer 1995，313-366.[16] R. Hull，J. Su.无类型集合、发明与可计算集合。Proc. PoDS1989，347-359.[17] R. Hull，J.苏论中间类型数据库的表现力计算机与系统科学杂志。卷45，1991年。[18] J. 海兰有效的拓扑。以. Troelstra，D.van Dalen（编辑）：L.E.J.布劳威尔百年纪念研讨会。North Holland，1982，165-216.[19] D.雷万特计算复杂性的描述性特征。计算机与系统科学杂志。Vol. 39，pp.51-83，1989年。[20] K.- D.舍韦湾塔尔海姆面向对象数据库的基本概念。《控制论学报》第11（4）卷，1993，49-85。[21] K.- D. Schewe。面向对象数据库建模基础。智能系统。第4卷（1-2），1999，195-224（俄文）。[22] K.- D. Schewe 。 OODB 建 模 中 的 类 型 概 念 及 其 逻 辑 含 义 。 In H.Kangassalo，E. Kawaguchi（Eds.）：信息建模与知识基础Xi，256-274，IOS出版社2000年。[23] K.- D. Schewe 。 查 询 代 数 的 统 一 及 其 对 有 理 树 结 构 的 扩 展 。 In M.Orlowska，J. Roddick（编）. 2001年澳大利亚数据库会议论文集[24] J.M.图鲁尔·托雷斯在同构数据库上工作的相关关系机器。在K.- D.舍韦湾Thalheim（编）.第一届信息与知识系统基础国际研讨会论文集。SpringerLNCS 1762，288-303，2000。[25] J.M.图鲁尔·托雷斯论非类型化数据的可表示性和可计算性。纯逻辑与应用逻辑年鉴卷108（1-3），2001，345-371。[26] J.M.图鲁尔·托雷斯面向关系数据库的语义分类。在洛贝尔托西湾Katona，K.- D.舍韦湾Thalheim（编辑）：数据库的语义。Springer LNCS（即将出现）。[27] J. Van den Bussche.数据库操作中对象标识的形式化方面。博士 论文 安特卫普大学，1993年。
