多级关系数据模型分析与优化方案

传统关系数据库包括关系集合、完整性约束和关系操作三个要素。与之对应，多级关系数据模型包括多级关系、扩展的多级关系完整性约束以及多级关系操作。

多级关系数据模型的复杂程度与安全模型中数据的安全标签粒度密切相关。安全标签粒度是标识安全等级的最小逻辑对象单位。按照由大到小的次序排列，安全标签粒度可以分为关系级、元组级和属性级。当控制粒度为关系级时，关系可以具有不同的安全标签，元组安全标签等于其所在关系的安全标签。当控制粒度为元组级时，关系可以具有不同的安全标签，同一关系中的元组也可以具有不同的安全标签，元组中的所有属性值的安全标签等于该元组的安全标签。当控制粒度为属性级时，关系、同一关系中的元组、同一元组中的每个属性值都可以具有不同的安全标签。粒度越小则控制越灵活，相对应的关系模型就越复杂。

1.多级关系

一个独立的多级关系模式记为R（A₁，C_l，A₂，C₂，…，A_n，C_n，TC）。其中，A_i表示R的第i个属性，C_i是A_i的安全标签，TC是元组的安全标签。多级关系是多级关系模式的实例。多关系中的元组表示为t（a₁，c_l，a₂，c₂，…，a_n，c_n，tc）。其中，元组t的安全标签为t[tc]，属性a_i的安全标签表示为t[c_i]。每个C_i的域由集合{L_i，…，H_i}指定，是属性A_i从最大下确界到最小上确界的所有安全等级列表。TC的域是{lub{L_i：i=l，…，n}，…，lub{H_i：i=l，…，n}}。其中，lub表示最小上确界（Least Upper Bound）。

在依赖于状态的关系实例集合中，对于给定格中的每个访问等级c，存在关系实例R_c（A₁，C_l，A₂，C₂，…，A_n，C_n，TC），是一个形如（a₁，c_l，a₂，c₂，…，a_n，c_n，tc）的不同元组的集合。其中，每个A_i∈D_i或a_i=null，c≥c_i，c_i∈{L_i，⋯，H_i}，tc=lub{c_i：i=l，…，n}。访问等级为c的关系实例是访问等级为c的用户所能看到的多级关系的内容，是访问等级为c的用户视图。

假设关系模式为Weapon（Wname，Range，Quantity），其中Wname、Range、Quantity分别表示武器名、射程和数量，Wname是主码。安全等级为{U，C，S，TS}，其中，U、C、S、TS分别表示公开、秘密、机密和绝密。该多级关系见表5-4，而表5-5～5-7分别是多级关系在不同的相应安全等级的关系实例。

表5-4 Weapon多级关系

表5-5 Weapon多级关系的U级实例

表5-6 Weapon多级关系的S级实例

表5-7 Weapon多级关系的TS级实例

2.多级关系完整性约束

在传统完整性约束的基础上，多级关系完整性约束扩展为实体完整性、空值完整性、参照完整性、实例间完整性和多实例完整性。这里，假设存在一个由用户指定的主码，称为外观主码（Apparent Key，AK)，简称为主码。

（i）实体完整性

设AK是定义在关系模式R上的外观主码，一个多级关系满足实体完整性，当且仅当对R的所有实例R_c与t∈R_c有：

1）A_i，A_j∈AK⇒t[A_i]≠null。

2）A_i，A_j∈AK⇒t[C_i]≠t[C_j]，即AK的各属性的安全等级一致。

3）Ai∉AK⇒t[C_i]…t[C_AK]，C_AK表示外观主

上述规则是对标准关系模型实体完整性的扩展，能够处理安全等级。第一个规则要求可以直接由标准模型的实体完整性得出，保证R_c中没有码属性为空的元组。第二个规则要求所有的码属性具有相同的安全等级，保证对所有的码属性，要么完全可见，要么完全不可见。第三个规则要求说明在任何元组中，非码属性的访问安全等级必须支配码属性的访问安全等级。这些要求保证在多级关系的每个实例中，消除了非空属性值具有空的主码值的情况。

（2）空值完整性

在多级关系中，空值有两种解释，一种是确实为空，另一种是实例的等级低于属性的等级，使得此属性不可见，从而显示为空。

空值完整性使用了归类关系。如果属性A_i满足下述条件之一，元组t归类于元组s：

1）t[A_i，C_i]=s[A_i，C_i]。

2）t[A_i]≠null且s[A_i]=null。

空值完整性规则控制空值和它们的密级。一个多级关系R满足空值完整性，当且仅当对R的每个实例R_c真均满足下列条件：

1）对所有的t∈R_c，t[A_i]=null⇒t[C_i]=t[C_AK]，即空值的安全等级等于主码的安全等级。

2）R_c无归类。即R_c中不包含两个不同的元组，其中一个元组归类于另一个元组。

这一规则要求元组中空值属性的等级必须与元组中主码属性的等级相同，并且不包含两个有归类关系的不同元组。

（3）多级外码完整性与参照完整性

假设FK是参照关系R的外码，多级关系R的一个实例R_c真满足外码完整性，当且仅当对所有的t∈R_c满足：

1）或者（任意A_i∈FK）[t[A_i]=null]，或者（任意A_i∈FK）[t[A_i]≠null]。

2）A_i，A_j∈FK⇒t[C_i]=t[C_j]。

第一条由传统关系数据模型得到，表示外码的所有属性要么全为空，要么全非空。第二条要求外码的每一个属性具有相同的安全等级。

多级参照完整性规定，每个外部关键字必须引用其他关系中的某个元组，而且该关键字在那个关系中是主关键字。在多级数据库中，这意味着一个外部关键字元素不能引用一个具有更高访问等级的元组。因为从外部关键字元素的访问等级上看，它所引用的这个更高等级的元组是不存在的。另外，在多级关系的每个元组中，构成外部关键字的每个元素的访问等级必须相同，而且，该访问等级必须支配它所引用的元组中的主关键字元素的访问等级。

（4）实例间完整性

多级关系R满足实例间完整性，当且仅当对所有的c'≤c，R_c'=σ（R_c，c'）’其中过滤函数σ按以下方法从R_c产生安全等级为c'的实例R_c'：

1）对任意t∈R_c，t[C_AK]≤c'，存在t'∈R_c，满足t'[AK,C_AK]=t[AK,C_AK]。

2）对任意，有。

R_c＇中所有元组均由上述规则导出，消除R_c´中被其他元组归类的所有元组后，得到过滤函数σ的最终结果。由于彻底排除了归类元组，最终结果是无归类的。(www.xing528.com)

（5）多实例完整性

假设多级关系R的主码集合为AK，主码等级为C_AK。多实例完整性要求由AK、C_AK以及第i个属性的等级C_i便可确定第i个属性值A_i。一个多级关系满足多实例完整性，当且仅当对于每个R_c中的每个属性A_i，满足：AK，C_AK，C_i→A_i成立，也就是说A_i函数依赖于AK、C_AK和C_i。

3.多级关系操作

由于多级关系的特殊性，多级关系上的操作语义也与传统关系操作有所不同。但是，多级关系操作语义应该尽量接近标准SQL，便于用户理解与使用。另外，多实例机制难免导致系统增加一些额外的元组，考虑到系统运行性能，多级关系操作应尽量减少额外元组。

（1）插入操作

多级关系插入操作的形式为：INSERT INTO R_c（A_i[，A_j]...）VALUE（A_i[，A_j]...），其中[]为可选项。为了满足主码完整性约束，插入操作应保证插入的元组满足t[AK]不为空，其中，AK为主码集合。若执行者是c等级用户，则t[c_i]=c，t[TC]=c。若关系中存在与所插入的元组t主码值相同的元组t'，可以分为以下几种情况考虑。

1）如果t[TC]=t'[TC]，为了满足多实例完整性约束，拒绝插入t。

2）如果t[TC]＜t'[TC]，为了防止产生推理通道，必须允许t的插入，这样将引入多实例元组。

3）如果t[TC]＞t'[TC]，因为拒绝高等级用户的操作并不会产生隐蔽通道，因此可以允许也可以拒绝t的插入。

例如，假设访问等级为S的主体要求对表5-6所示多级关系做如下插入操作：

INSERT INTO Weapon

VALUES"Cannonl，10，200"

插入操作的结果见表5-8所示。

表5-8 Weapon多级关系的S级插入

假定访问等级为S的主体再要求做如下操作：

INSERT INTO Weapon

VALUES"Missile1，10，200"

此操作要求插入一个新的元组，其主码值等于一个已存在元组的主码值Missile1。这种情况下，拒绝此插入操作，通知用户已存在一个具有相同主码值的元组。

（2）删除操作

多级关系删除操作的形式为：DELETE FROM R_c[WHERE p]。其中，p表示删除的谓词条件，只有满足删除条件p的元组才可能被删除。由于BLP模型的约束，删除操作的对象只能是满足t[TC]=c的元组。由于关系间完整性约束，在更高等级的关系实例中的元组也应该被相应地删除。

（3）查询操作

访问等级为c的用户的多级关系查询操作的形式为：SELECT A₁[，A₂]…FROM R₁[，R₂]…[WHERE p][AT c_l[，c₂]…]。其中，R₁，R₂…是多级关系名，A₁，A₂…是在R₁，R₂…中的属性名，包括数据属性和安全等级属性，p是包含安全等级属性和数据属性的谓词条件，c₁，c₂…是安全等级值。

SELECT操作语义是如果无AT，则仅有t[TC]=c的元组计算谓词p；如果有AT语句，则仅对t[TC]的值在AT子句安全等级范围内的元组计算谓词p。若FROM子句中有多于一个的关系，则p被隐含替换为p^R₁.TC=R₂.TC…。

（4）更新操作

多级关系更新操作的形式为：UPDATE R_cSET A_i=s_i[，A_j=s_j]…[WHERE p]。其中p是更新谓词条件，表示只有满足条件p的元组才进行更新，s_i，s_j是表达式。更新操作有可能会因为多实例而导致元组数目增加，但是最好尽量避免这种情况。由于关系间完整性的约束，更新操作的语义对不同等级的关系实例的影响有以下3点：

1）操作对同等级关系实例的影响与传统UPDATE语句一样。

2）对更低等级关系实例无影响。

3）对更高等级用户，为避免隐蔽通道，可能引入多实例。

例如，假设Weapon关系的U级实例和S级实例分别见表5-9和5-10，访问密级为U的用户要求对Weapon关系的U级实例做如下更新操作：

表5-9 Weapon关系的U级实例

表5-10 Weapon关系的S级实例

此操作分别更新为表5-11和5-12。

表5-11 Weapon关系的U级实例（更新后）

表5-12 Weapon关系的S级实例（更新后）

在Weapon关系的S级实例中，Wname属性上存在多实例，这是为了防止产生推理通道必须引入多实例的例子。