NCSC TECHNICAL REPORT - 005

Volume 2/5

Library No. S-243,039

FOREWARD

This report is the second of five companion documents to the Trusted Database Management 
System Interpretation of the Trusted Computer System Evaluation Criteria. The companion 
documents address topics that are important to the design and development of secure database 
management systems, and are written for database vendors, system designers, evaluators, and 
researchers. This report addresses entity and referential integrity issues in multilevel secure 
database management systems.

ACKNOWLEDGMENTS

The National Computer Security Center extends special recognition to the authors of this 
document. The initial version was written by Vinti Doshi and Sushil Jajodia of the MITRE 
Corporation. The final version was written by Bill Wilson and Stan Wisseman of Arca Systems, 
Inc.

The documents in this series were produced under the guidance of Shawn P. O'Brien of the 
National Security Agency, LouAnna Notargiacomo and Barbara Blaustein of the MITRE 
Corporation, and David Wichers of Arca Systems, Inc.

We wish to thank the members of the information security community who enthusiastically gave 
of their time and technical expertise in reviewing these documents and in providing valuable 
comments and suggestions.

TABLE OF CONTENTS

SECTION	PAGE

1.0	INTRODUCTION	1

1.1	BACKGROUND AND PURPOSE	1

1.2	SCOPE	1

1.3	INTRODUCTION TO ENTITY AND REFERENTIAL INTEGRITY	2

1.4	AUDIENCES OF THIS DOCUMENT	3

1.5	ORGANIZATION OF THIS DOCUMENT	4

2.0	BACKGROUND	5

2.1	BASIC CONCEPTS OF ENTITY AND REFERENTIAL INTEGRITY	6

2.2	REFERENTIAL INTEGRITY RULES	10

2.2.1	DELETE	10

2.2.2	UPDATE of Referenced Relation	13

2.2.3 	NSERT or UPDATE of Referencing Relation	17

2.2.4	Additional Rules	17

2.3	PROBLEMS WITH REFERENTIAL INTEGRITY CONSTRAINTS	17

3.0	ENTITY AND REFERENTIAL INTEGRITY IN MLS DATABASES	18

3.1	RELATED TCSEC REQUIREMENTS	18	

3.2	BASIC CONCEPTS IN MULTILEVEL RELATIONS	19

3.3	THE CONCEPT OF PRIMARY KEY IN MULTILEVEL RELATIONS	21

3.4	ENTITY INTEGRITY IN MULTILEVEL RELATIONS	21

3.5	REFERENTIAL INTEGRITY IN MULTILEVEL RELATIONS	22

3.6	ENFORCEMENT OF INTEGRITY CONSTRAINTS	25

4.0	COVERT CHANNELS	27

4.1	PRIMARY KEY UNIQUENESS	27

4.2	ENFORCEMENT OF REFERENTIAL INTEGRITY RULES	28

4.2.1 Enforcement of Integrity Rules When C[FK] = C[PK]		29

4.2.2 Enforcement of Integrity Rules When C[FK] > C[PK]		30

4.3	RELATION TO DBMS ARCHITECTURE	36

5.0	SUMMARY	38

REFERENCES		39

LIST OF FIGURES

FIGURE	PAGE

2.1:	RELATION SOD	6

2.2:	RELATION PS	8

2.3:	REFERENTIAL CONSTRAINTS IN RELATIONS PR, PS, AND SOD	9

2.4:	RELATIONS SOD AND PS AFTER STARSHIP = "APOLLO" IS DELETED
UNDER THE CASCADES-DELETE RULE		11	

2.5:	RELATIONS SOD AND PS AFTER STARSHIP = "APOLLO" IS
DELETED UNDER THE NULLIFIES-DELETE RULE		12

2.6:	RELATIONS SOD AND PS AFTER STARSHIP = "ENTERPRISE" IS
UPDATED TO THE VALUE "USS ENTERPRISE"
UNDER THE CASCADES-UPDATE RULE		15

2.7:	RELATIONS SOD AND PS AFTER STARSHIP = "ENTERPRISE" IS
UPDATED TO THE VALUE "USS ENTERPRISE" UNDER THE
NULLIFIES-UPDATE RULE		16

3.1:	DIFFERENT SOD VIEWS BASED ON ACCESS CLASS	21

3.2:	TYPICAL RELATION INSTANCES FOR SOD AND PS	23

3.3:	UNCLASSIFIED INSTANCES OF PS AND SOD RELATIONS	24

4.1:	SOD AFTER INSERTION OF TUPLE CORRESPONDING TO
STARSHIP = "VOYAGER" BY UNCLASSIFIED USER		28

4.2:	RELATION PS AND SOD WHEN C[FK] = C[PK]	30

4.3:	RELATIONS SOD AND PS WITHOUT POLYINSTANTIATION	32

4.4:	RELATIONS WITH TUPLE-LEVEL GRANULARITY	34

4.5:	RELATIONS WITH ATTRIBUTE-LEVEL GRANULARITY	35

LIST OF TABLES

TABLE	PAGE

4.1:	SUMMARY OF COVERT CHANNELS IN REFERENTIAL INTEGRITY
RULES		36

SECTION 1

INTRODUCTION

This document is the second volume in the series of companion documents to the Trusted Database 
Management System Interpretation of the Trusted Computer System Evaluation Criteria [TDI 91; 
DoD 85]. This document examines entity and referential integrity issues in multilevel secure 
(MLS) database management systems and summarizes the research to date in these areas.

1.1	BACKGROUND AND PURPOSE

In 1991 the National Computer Security Center published the Trusted Database Management 
System Interpretation (TDI) of the Trusted Computer System Evaluation Criteria (TCSEC). The 
TDI, however, does not address many topics that are important to the design and development of 
secure database management systems (DBMSs). These topics (such as inference, aggregation, and 
database integrity) are being addressed by ongoing research and development. Since specific 
techniques in these topic areas had not yet gained broad acceptance, the topics were considered 
inappropriate for inclusion in the TDI.

The TDI is being supplemented by a series of companion documents to address these issues 
specific to secure DBMSs. Each companion document focuses on one topic by describing the 
problem, discussing the issues, and summarizing the research that has been done to date. The intent 
of the series is to make it clear to DBMS vendors, system designers, evaluators, and researchers 
what the issues are, the current approaches, their pros and cons, how they relate to a TCSEC/TDI 
evaluation, and what specific areas require additional research. Although some guidance may be 
presented, nothing contained within these documents should be interpreted as criteria.

These documents assume the reader understands basic DBMS concepts and relational database 
terminology. A security background sufficient to use the TDI and TCSEC is also assumed; 
however, fundamentals are discussed whenever a common understanding is important to the 
discussion.

1.2	SCOPE

This document addresses entity and referential integrity issues in multilevel secure DBMSs. It is 
the second of five volumes in the series of TDI companion documents, which includes the 
following documents:

�	Inference and Aggregation Issues in Secure Database Management Systems [Inference 
96]

�	Entity and Referential Integrity Issues in Multilevel Secure Database Management 
Systems

�	Polyinstantiation Issues in Multilevel Secure Database Management Systems [Poly 96]

�	Auditing Issues in Secure Database Management Systems [Audit 96]

�	Discretionary Access Control Issues in High Assurance Secure Database Management 
Systems [DAC 96]

This series of documents uses terminology from the relational model to provide a common basis 
for understanding the concepts presented. For most of the topics covered in this series the concepts 
presented should apply to most database modeling paradigms, depending on the specifics of each 
model. For the entity and referential integrity constraints discussed in this document, however, 
there are important differences between different models. This is because the primary keys in a 
relational DBMS represent both unique identifiers for tuples and values of attributes in the tuple. 
They must be protected in accordance with the sensitivity of the data they represent and this can 
interfere with their role as a unique identifier of tuples. By contrast, the object identifier (OID) in 
an Object-Oriented DBMS is not a property or attribute of the object it identifies, and does not 
represent a user-visible data value. Khoshafian and Copeland provide a useful taxonomy of 
different ways of specifying object identity including the techniques used in relational and Object-
Oriented DBMSs [Khoshafian 86]. Similarly, in a relational DBMS, foreign keys represent data 
values and serve as pointers to other tuples. In an Object-Oriented DBMS, pointers to other objects 
are not used to store data values, but rather to represent the inclusion of one object within another. 
As in relational databases, problems may occur if a reference is deleted and some references remain 
in objects. The implications of these distinctions for enforcement of secrecy in an Object-Oriented 
DBMS require further research. This document specifically addresses relational DBMSs.

This document is related to the companion documents Inference and Aggregation Issues in Secure 
Database Management Systems and Polyinstantiation Issues in Multilevel Secure Database 
Management Systems. Much of the discussion of the relationship between enforcement of integrity 
constraints and multilevel security centers on the potential inference channels which integrity 
constraints can introduce. One way to avoid these channels for entity integrity is to use 
polyinstantiation. This is discussed later in more detail.

1.3	INTRODUCTION TO ENTITY AND REFERENTIAL INTEGRITY

Secrecy and integrity are two key concepts in the community of database security researchers and 
users. Secrecy refers to the protection or safety of the data against unauthorized disclosure, and 
integrity refers to the unauthorized alteration or destruction of data. In the wider database research 
community, integrity refers more generally to the correctness, accuracy, and internal consistency 
of data.

Preserving the accuracy of information is extremely important rn any database. In the relational 
model, one way in which accuracy of information is preserved is by preventing updates that violate 
integrity constraints. Entity integrity and referential integrity are two of the most important 
integrity constraints. They are defined on relations and are enforced by the DBMS.

Entity integrity states that no primary key attribute of a relation is allowed to have null values. In 
addition, the primary key must have a unique value. These properties of a primary key correspond 
to the fact that entities in the real world are distinguishable (i.e., they have a unique identification 
of some kind). In the relational model, the primary key performs the function of unique 
identification. Referential integrity is an interrelation integrity constraint. In general, referential 
integrity defines existence relationships between entities in a database that need to be maintained 
by the DBMS. This document defines these integrity constraints formally and presents their 
importance in the context of security in detail.

In multilevel applications, data are classified to control disclosure. It is important to realize the 
necessary trade-off to be made between secrecy and integrity because of the challenges in 
enforcing integrity constraints across multiple secrecy levels without disclosure of information. 
This document defines entity and referential integrity for a standard relational DBMS and then 
presents methods for resolving the inherent integrity/secrecy conflict in an MLS environment.

1.4	AUDIENCES OF THIS DOCUMENT

This document is targeted at four primary audiences: the security research community, database 
application developers/system integrators, trusted product vendors, and product evaluators. In 
general, this document is intended to present a framework for understanding the nature of entity 
and referential integrity policies or requirements and how they conflict with the need to enforce an 
access control policy. This framework is used to describe the research that has been done to date 
and the approaches they present for providing solutions. Each of the specific audiences should 
expect to get the following from this document:

Researcher

This document describes the basic problems in simultaneously enforcing integrity constraints and 
MAC. Some important research contributions are discussed as various topics are covered. Related 
research on other aspects of integrity and the relationship to secrecy is discussed in Section 3.6. 
For additional relevant work, the researcher should consult two other companion documents, 
Inference and Aggregation Issues in Secure Database Management Systems [Inference 96] and 
Polyinstantiation Issues in Multilevel Secure Database Management Systems [Poly 96].

Database Application Developer/System Integrator

This document describes various entity and referential integrity facilities which could be provided 
by an MLS DBMS. It discusses the implications of these facilities relative to the tradeoffs involved 
in meeting a system's requirements for secrecy and integrity.

Trusted Product Vendor

This document describes the conflicts between Mandatory Access Controls (MAC) and multilevel 
entity and referential integrity constraints. It then discusses approaches to entity and referential 
integrity enforcement in an MLS database and the benefits and drawbacks of these approaches. In 
particular, it considers how the issues with enforcement of entity and referential integrity 
constraints in an MLS database relate to the TCSEC access control and covert channel 
requirements. This is discussed in the context of tuple level as well as element level labeling. This 
document will provide a framework for understanding specific requirements interpretations as they 
are developed by the National Computer Security Center.

Evaluator

This document describes access control and covert channel issues related to entity and referential 
integrity. It provides a framework for analyzing specific vendor mechanisms and understanding 
Technical Review Board/Interpretations Working Group decisions.

1.5	ORGANIZATION OF THIS DOCUMENT

The organization of the remainder of this document is as follows:

�	Section 2 gives the definitions of entity and referential integrity with respect to single-level 
DBMSs and describes various important concepts related to referential integrity.

�	Section 3 defines the basic concepts of entity and referential integrity with respect to 
multilevel relations.

�	Section 4 discusses the issues associated with covert channels related to enforcing entity 
and referential integrity constraints.

�	Section 5 presents conclusions.

SECTION 2

BACKGROUND

Entity integrity and referential integrity are two basic integrity requirements in a relational DBMS 
(RDBMS). They help prevent incorrect data from being entered into the database. Entity integrity 
guarantees a unique representation of each entity in the database through specification of primary 
key attributes for each relation. Referential integrity assures that if any references exist between 
two or more entities, then the related entities do exist in the database. Referential integrity places 
restrictions on foreign key attributes.

Referential integrity is one of the most important interrelation integrity constraints for the 
relational data model. Although its basic concepts have been discussed over the past ten years, a 
successful referential integrity capability for a RDBMS is still a challenging implementation 
problem. While referential integrity appears to be a simple concept, the operational definitions that 
appear in the literature are imprecise and lead to a host of anomalies.

A standard relational database can be perceived by its users as a collection of relations. A relation 
has well-defined mathematical properties and is used to store data. Each relation has two parts:

1.	A state-invariant relation schema R (A1, A2, ..., An), where each Ai is an attribute over 
some domain Di, 1 � i � n, which is a set of acceptable values for Ai.

2.	A state-dependent relation R over R, which is a set of distinct tuples of the form (a1, a2..., 
an), where each element ai; is a value in domain di, 1 � i � n.

The following notation and conventions are used throughout this document. In definitions, relation 
schemes are denoted in bold fonts (such as R, R1, R2), and the corresponding relations are denoted 
using plain fonts (such as R, R1, R2). However, when clear in specific examples, the same symbol 
is used to denote the relation schema, as well as the corresponding relation. Let X denote one or 
more attributes of a relation R. If t is a tuple in a relation R, t [X] denotes the projection of t onto X.

This section first defines entity and referential integrity, followed by terminology related to these 
concepts. The examples make use of Structured Query Language (SQL) syntax [ANSI 92, 94]. The 
section then gives various rules for enforcing referential integrity and discusses the problems 
associated with referential integrity in single-level relational databases. From this understanding 
of integrity, we can then better discuss the conflict with enforcement of a MAC policy in Section 3.

2.1	BASIC CONCEPTS OF ENTITY AND REFERENTIAL INTEGRITY

Before defining entity integrity, it is necessary to define the concept of a primary key.

In simple terms, the primary key of a relation is just a unique identifier of each tuple in the relation. 
More precisely, a primary key for a relation R is a set of attributes PK with the following 
properties:

1.	The value of PK uniquely identifies each tuple in the relation R. That is, for any state of 
R, and any tuples t1 and t2, if t1[PK] = t2[PK] then t1 = t2.

2.	PK is minimal. That is, there is no proper subset of PK satisfying property 1.

It is possible there is more than one set of attributes satisfying these properties. Any such set is 
called a candidate key. Precisely one candidate must be chosen and designated as the primary key 
of R.

Example 1. Consider the relation schema SOD (Starship, Objective, Destination), which contains 
for each starship its name (Starship), the purpose of the flight (Objective), and its destination 
(Destination). An example relation for relation schema SOD is given in Figure 2.1.

STARSHIP

OBJECTIVE

DESTINATION

Enterprise

Exploration

Talos

Voyager

Spying

Mars

Apollo

Exploration

Moon

Saratoga

Mining

Moon

Figure 2.1: Relation SOD

Since the attribute Starship uniquely identifies each tuple of the relation SOD, it is a candidate key 
of the relation SOD. As Starship is the only candidate key of the relation SOD, it is also the primary 
key of relation SOD.

In SQL syntax, the attribute(s) constituting the primary key can be specified when a relation 
schema is created, as the following shows:

CREATE TABLE SOD

(Starship CHAR(20) NOT NULL,

Objective CHAR(15),

Destination CHAR(10),

PRIMARY KEY (Starship))

Notice that the ANSI syntax uses the term "TABLE" instead of the term "relation" used in this 
document.

The entity integrity constraint requires that all attribute values of the primary key be defined for 
each tuple.

Entity Integrity: If PK is the primary key for relation R, then for all states of R, for every tuple 
t in R and every attribute A in PK, t[A] is not null.

A foreign key provides a basis for a tuple to refer to another tuple. Let R1 and R2 be two relation 
schemas, and let R1 and R2 denote the respective relations corresponding to these schemas.

Referential Integrity: Let PK denote the primary key of R2, and let FK denote one or more 
attributes of the relational schema R1. FK is said to be a foreign key of R1 referencing R2 if 
given any tuple t1 in R1, the following two requirements are met:

1.	t1 [FK] is either wholly null or wholly non-null, and

2.	Whenever t1[FX] is non-null, there is a tuple t2 in R2 such that t1[FK] = t2[PK].

Here R1 is the referencing relation and R2 is the referenced relation. Sometimes PK is referred to 
as the target value of the foreign key FK. Notice that R1 and R2 need not be distinct.

Example 2. In addition to the relation schema SOD given in Example 1, consider the relation 
schema PS (Person_Name, Starship), which contains the name of the employee (Person_Name) 
and the name of the ship assigned to the employee (Starship). An example relation for PS is given 
in Figure 2.2.

Suppose Person_Name uniquely identifies each employee in the PS relation, then Person_Name 
becomes the primary key for the relation schema PS. If Starship is declared a foreign key for PS 
with the relation schema SOD as the referenced relation, a DBMS that supports referential integrity 
will automatically ensure that whenever an employee is assigned a (non-null) ship, there is a 
matching tuple in the relation schema SOD with an identical value for the attribute Starship.

Notice that employee Mr. Spock, given in Figure 2.2, has not been assigned any starship. It seems 
from the definition of the PS relation that nulls are allowed. In some applications it may be 
desirable to prohibit this situation (i.e., every employee must be assigned a starship). The 
referencing relation's schema definition can specify whether or not the foreign key attribute can 
assume a null value.

Using SQL syntax, foreign keys can be specified as follows:

CREATE TABLE PS

Person_Name	CHAR(15) NOT NULL,

Starship	CHAR(20),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship)).

PERSON_NAME

STARSHIP

James Kirk

Enterprise

Mr. Spock

<null>

Tim McKelley

Apollo

Figure 2.2: Relation PS

It follows from the definition of the foreign key that there is an identical matching primary key 
value in the referenced relation for every foreign key value in the referencing relation. It is 
important to maintain the integrity between the referencing values (foreign key values) and the 
referenced values (primary key values).

Example 3. Consider the relation schema PR (Person_Name, Rank), which contains the employee 
name (Person_Name) and the rank of the employee (Rank). Person_Name is the primary key for 
the relation schema. Person_Name is also the foreign key referring to relation schema PS.

The relation schema PR can be expressed in SQL as follows:

CREATE TABLE PR

(Person_Name	CHAR(20) NOT NULL,

Rank	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Person_Name) REFERENCES PS (Person Name))

Here, the relation schema PR references the relation schema PS given in Example 2. In addition, 
the relation schema PS in Example 2 references the relation schema SOD. Since there is a 
referential constraint from PR to PS, and also from PS to SOD, relation schema PS becomes both 
a referencing relation and a referenced relation, see Figure 2.3.

Figure 2.3: Referential Constraints in Relations PR, PS, and SOD

This can be depicted as a referential path from PR to SOD as follows:

PR > PS  > SOD

Referential Cycles: Closed referential paths, or referential paths that point back to the starting 
relation, are referred to as referential cycles. In general, the referential cycle including n 
relations (where n > 1) can be represented as follows [Date 86, 90]:

Rn >  Rn-1 >  Rn-2  > ... >  R2 >  R1 >  Rn.

Referential cycles are of interest since they can cause insertion problems. In the presence of 
referential cycles, it is necessary that one of the following constraints be true; otherwise, it is 
impossible to insert the first tuple in any or each of the relations:

1.	One of the foreign keys in the referential cycle must be allowed to have a null value, or

2.	The constraint check should be done only at the end-of-transaction (i.e., when the 
transaction commits).

A self-referencing relation is a special case of a referential cycle that includes exactly one relation: 
a relation can have multiple foreign keys corresponding to different relations.

Some important concepts related to the terms defined in this section can be summarized as follows:

�	A primary key of a relation cannot have a null value in any tuple within that relation (entity 
integrity) and each primary key must be unique (property of a primary key).

�	Foreign keys can have null values. For example, in Figure 2.2 the employee Mr. Spock has 
not been assigned any starship as yet; therefore, the Starship value for Mr. Spock is null. 
(Note: If in a specific instance it is desired to prohibit null values for foreign keys, this can 
be done by using a NOT NULL clause for the attributes in the foreign key when the 
relation is created.)

�	For referential integrity, every non-null value of a foreign key must be matched by an 
identical primary key value in the referenced relation. But the converse need not be true; 
for example, starship Saratoga in Figure 2.1 has no employee assigned to it in Figure 2.2.

�	A relation can be a referenced relation, as well as a referencing relation.

2.2	REFERENTIAL INTEGRITY RULES

Whenever two or more relations are related through referential constraints, it is necessary that 
references be kept consistent in the face of insertions, deletions, and updates to these relations. Date 
identifies several actions which can be taken to maintain consistency of references [Date 90]. 
Exactly which action is chosen for a particular relation depends on the behavior desired by the 
underlying application. These possible actions are discussed in the following subsections.

2.2.1	DELETE

When the target of a foreign key is deleted it could result in a dangling reference. Some action is 
needed to make sure this does not happen. Four options that may be specified for the referenced 
relation are RESTRICTED-delete, CASCADES-delete, NULLIFIES-delete, and SET 
DEFALILT-delete. Each of these is explained in turn.

RESTRICTED-delete

If the RESTRICTED-delete option is specified, the primary key value in the referenced relation 
cannot be deleted as long as there exists at least one matching foreign key value in the referencing 
relation. The deletion of the referenced value is restricted to the case where there is no 
corresponding referencing value in the referencing relation.

For instance, suppose an attempt is made to delete the starship Apollo from the relation SOD. Since 
the referencing relation PS refers to the relation SOD through the attribute Starship, under the 
RESTRICTED-delete rule, this deletion cannot be performed as there is a tuple in PS referencing 
starship Apollo. The delete is denied and the two relations would remain unchanged.

The syntax for specifying the RESTRICTED-delete rule may be given as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON DELETE	RESTRICT)

CASCADES-delete

Under the CASCADES-delete option, whenever the target tuple of a foreign key is deleted, all 
referencing foreign key tuples are also deleted. In the previous example, if an attempt is made to 
delete the starship Apollo from the relation SOD, the delete would be cascaded to the relation PS 
and the employee tuples referencing the starship Apollo would also be deleted. After such a 
CASCADES-delete operation, the relations SOD and PD would change to the form given in Figure 
2.4.

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise

Exploration

Talos

Voyager

Spying

Mars

Saratoga

Mining

Rigel

PS

PERSON_NAME

STARSHIP

James Kirk

Enterprise

Mr. Spock

<null>

Figure 2.4: Relations SOD and PS after Starship = "Apollo" is Deleted under the
CASCADES-Delete Rule

In SQL, the CASCADES-delete rule can be specified as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON DELETE	CASCADE)

NULLIFIES-delete

Whenever the NULLIFIES-delete option is specified for a foreign key, the referencing foreign key 
attribute values will be set to a null value when the tuple containing the referenced value is deleted. 
In the example given earlier, when starship Apollo is deleted, the foreign key value, for all tuples 
referencing Apollo in relation PS, is set to null. The new state of the relations is as shown in Figure 
2.5.

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise

Exploration

Talos

Voyager

Spying

Mars

Saratoga

Mining

Rigel

PS

PERSON_NAME

STARSHIP

James Kirk

Enterprise

Mr. Spock

<null>

Tim McKelley

<null>

Figure 2.5: Relations SOD and PS after Starship = "Apollo" is Deleted under the 
NULLIFIES-Delete Rule

Before setting the referencing value to null, it is important to make sure that the relation schema 
allows a null value for the foreign key attribute. Otherwise, there will be a conflict.

The NULLIFIES-delete rule can be expressed in SQL as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON DELETE	SET NULL)

SET DEFAULT-delete

The SQL2 [ANSI 92] and SQL3 [ANSI 94] standards provide yet another referential action for the 
delete operation, called SET DEFAULT. This option is similar to the NULLIFIES delete rule 
given above. The only difference is that the SET DEFAULT option contains a default clause that 
specifies the default value for the attribute. The default value may be a null or a non-null value. If 
the referential action specifies the SET DEFAULT option, then each referencing attribute is 
defined by an implicit or explicit default clause. If the default value is null, then SET DEFAULT 
is equivalent to a SET NULL.

The SQL syntax for the SET DEFAULT-delete rule is as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON DELETE	SET DEFAULT < option>)

The default option is specified in the <option> field.

2.2.2	UPDATE of Referenced Relation

Changing the primary key values in a referenced relation could violate referential integrity unless 
appropriate action is taken. There are different options which can be specified for the referencing 
relation whenever an update is made to the target primary key values of a referenced relation. The 
possible options are RESTRICTED-update, CASCADES-update, NULLIFIES-update, or SET 
DEFAULT-update.

RESTRICTED-update

Under the RESTRICTED-update option, an update to the target primary key values of a referenced 
relation cannot be made as long as there exists at least one matching foreign key value in the 
referencing relation. The update to the referenced tuple is restricted to the case where there are no 
matching referencing tuples.

As an example, suppose an attempt is made to update the name of the starship from Enterprise to 
USS Enterprise in relation SOD shown in Figure 2.1. As there is an employee assigned to the ship, 
the update is rejected. The relations SOD and PS remain unchanged, and look like Figures 2.1 and 
2.2.

The syntax for specifying the RESTRICTED-update option may be specified as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON UPDATE	RESTRICT)

CASCADES-update

If the CASCADES-update option is specified for a referencing relation, whenever an update is 
made to the referenced attribute, all changes are cascaded to the matching referencing attributes. 
This means that whenever the target value of a foreign key is modified, all referencing foreign key 
values are also similarly modified. Consider the example where an attempt is made to update the 
name of the starship from Enterprise to USS Enterprise in the relation schema SOD. Under 
CASCADE-update, the update is cascaded to the matching referencing tuples in the relation 
schema PS. For the employee assigned to starship Enterprise, the name is updated to USS 
Enterprise. The new state of the two relations SOD and PS is shown in Figure 2.6.

In SQL, the CASCADE-update option can be expressed as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON UPDATE	CASCADE)

SOD



STARSHIP

OBJECTIVE

DESTINATION

USS Enterprise

Exploration

Talos

Voyager

Spying

Mars

Apollo

Exploration

Moon

Saratoga

Mining

Rigel

PS

PERSON_NAME

STARSHIP

James Kirk

USS Enterprise

Mr. Spock

Null

Tim McKelley

Apollo

Figure 2.6: Relations SOD and PS after Starship = "Enterprise" is Updated to the Value 
"USS Enterprise" under the CASCADES-Update Rule

NULLIFIES-update

Under the NULLIFIES-update option, the referencing foreign key attribute values are set to null 
whenever the target primary key values in the referenced relation are updated. In the example given 
earlier, when the name of the starship is updated from Enterprise to USS Enterprise, the Starship 
for the employee assigned to Enterprise is set to null. The new state of the relations is shown in 
Figure 2.7.

Before setting the referencing value to null, it is important to make sure that the schema definition 
allows a null value for the foreign key attribute. If the nulls rule does not allow a null value, then 
there will be a conflict between the two integrity rules.

The NULLIFIES-update rule is expressed in SQL syntax as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(I5),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON UPDATE	SET NULL)

SOD



STARSHIP

OBJECTIVE

DESTINATION

USS Enterprise

Exploration

Talos

Voyager

Spying

Mars

Apollo

Exploration

Moon

Saratoga

Mining

Rigel

PS

PERSON_NAME

STARSHIP

James Kirk

< null >

Mr. Spock

< null >

Tim McKelley

Apollo

Figure 2.7: Relations SOD and PS after Starship = "Enterprise" is Updated to the Value 
"USS Enterprise" under the NULLIFIES Update Rule

SET DEFAULT-update

SQL2 and SQL3 define another referential constraint for update, which is SET DEFAULT. If the 
referential constraint specifies the SET DEFAULT option, then each referencing attribute is 
defined by an implicit or explicit default clause. The default clause specifies the default value for 
the attribute, and the default value may be a null or a non-null value. If the default value is null, 
then the SET DEFAULT option can be considered equivalent to the NULLIFIES update rule.

The SQL syntax for the SET DEFAULT-update rule is as follows:

CREATE TABLE PS

(Person_Name	CHAR(20) NOT NULL,

Starship	CHAR(15),

PRIMARY KEY	(Person_Name),

FOREIGN KEY	(Starship) REFERENCES SOD (Starship),

ON UPDATE	SET DEFAULT <option>)

The default option is specified in the <option> field.

2.2.3	INSERT or UPDATE of Referencing Relation

When a tuple is inserted into a relation with a foreign key or a tuple in the relation is updated, the 
insertion (or update) of a foreign key value should be in accordance with referential integrity. Each 
foreign key value must be NULL or have an identical matching primary key value in the referenced 
relation. This requirement can be enforced by disallowing the insert (or update) unless the 
condition is met or by setting the foreign key to a default value or null (if nulls are allowed) when 
the condition is not met.

2.2.4	Additional Rules

In spite of the many integrity rules discussed in this section, the rules above are not exhaustive. 
Additional options include conversation with the end user and transferring information to some 
other files. For instance, an additional option in SQL3 is the PENDANT specification, which 
implies that each primary key value in the referenced relation is the same as some foreign key value 
in the referencing relation. For example, if the referential constraint for the relation EMP is as 
shown below, then as soon as the last employee in a particular department is deleted, the 
department will also be deleted.

FOREIGN KEY (Starship) REFERENCES [PENDANT] SOD(Starship)

2.3	PROBLEMS WITH REFERENTIAL INTEGRITY CONSTRAINTS

Referential integrity plays a major role in RDBMSs where it is employed to express existence 
dependencies. The concept of referential integrity seems to be simple, but it has been a topic of 
discussion for the past several years [Markowitz 90; Horowitz 92]. The operational definitions are 
not precise and, therefore, lead to some anomalies. Confusion surrounds both the concept itself and 
its implementation in RDBMSs. There is a need to carefully examine the data manipulation 
problems caused by certain referential integrity structures and to find ways to avoid these 
problems.

In a RDBMS, a single update or delete can affect multiple tuples through the application of 
referential integrity rules (e.g., cascading deletes or updates). It is necessary for these processes to 
be deterministic. In other words, the final state of the database should be a function of the initial 
state of the database, and the specific statement to be executed. At times, certain referential 
constraints associated with relations may block update or deletion of some tuples because of 
conflicting referential constraint specifications, thus making the outcome of the update or delete 
statement unpredictable. Some of the problems that have been identified are dependency on the 
order in which referential integrity constraints are applied, referential cycles, and dependency on 
the order in which the tuples are processed in response to a query. Discussion of these problems in 
detail is outside the scope of this document.

SECTION 3

ENTITY AND REFERENTIAL INTEGRITY IN MLS DATABASES

Before entity and referential integrity can be defined for multilevel relations, it is necessary to 
extend the basic concepts of classical (single-level) relations to the multilevel context. In MLS 
databases, data are assigned different security levels and each user is assigned a clearance level. 
Each user can only access data they are cleared for based on the user's security clearance. As a 
consequence the meaning of relations becomes more complicated in the multilevel world, and 
there is no clear consensus regarding the exact definition of a multilevel relational model.

To develop an MLS database, it is necessary to (1) define a security policy, (2) develop 
mechanisms that support the policy, and (3) get the necessary assurance that the system developed 
is secure. This section first reviews the basic concepts for the multilevel relational data model, then 
defines entity and referential integrity constraints for multilevel relations.

3.1	RELATED TCSEC REQUIREMENTS

The TCSEC imposes two types of requirements which affect how entity and referential integrity 
can be enforced in a DBMS targeted to meet the TCSEC requirements at B1 and above. A DBMS 
targeted for Class B1 or above must enforce a MAC policy over all subjects and storage objects it 
controls. This places requirements on the sensitivity labels of elements of primary and foreign keys 
and on the relationships between sensitivity levels of foreign keys and the primary keys they 
reference. For a DBMS targeted at Class B2 or above, the TCSEC requires a thorough search for 
covert channels (storage channels only at Class B2). In the multilevel context, enforcement of the 
uniqueness of primary keys and enforcement of referential integrity can create significant covert 
channels. Guidelines on acceptable bandwidths for covert channels are given in Section 8 of the 
TCSEC. This section specifically addresses the implications of direct enforcement of MAC 
controls (as required at B1 and above). The implications of integrity enforcement on covert 
channels is covered in Section 4. A determination of precisely which approaches to enforcing 
entity and referential integrity will be considered compliant with the TCSEC requirements will 
evolve over time as the Evaluation Community publishes official interpretations on this subject. 
However, with the successful evaluation of Trusted Oracle7 DBMS MAC Mode with an 
unmodified integrity mechanism, precedence has been set for Class B1 DBMSs [Oracle 94].

3.2	BASIC CONCEPTS IN MULTILEVEL RELATIONS

The basic model for multilevel relations needs to be defined with a MAC policy in mind. The MAC 
policy for MLS databases is often based on the Bell-LaPadula model [Bell 76], which is stated in 
terms of subjects and objects. A subject is an active entity, such as a process that can request access 
to objects, whereas an object is a passive entity, such as a record, a file, or a field within a record. 
Every subject is assigned a clearance level and every object a classification level. Classification 
levels and clearances are collectively referred to as security levels, and form a lattice. Each security 
level has two components: a hierarchical component and a set (possibly empty) of unordered 
categories. A security level c1 is said to dominate security level c2, in the partial order, if (1) the 
hierarchical component of c1 is greater than or equal to that of c2, and (2) all categories in c2 are 
included in those of c1. A security level c1 strictly dominates security level c2, in the partial order, 
if (1) c1 dominates c2, and (2) c1 does not equal c2. The following are two necessary conditions in 
the Bell-LaPadula model [Bell 76; DoD 85]:

1.	The Simple Security Condition or "No Read Ups": A subject can only read objects at a 
security level dominated by the subject's level, and

2.	The *-Property (Star Property) or "No Write Downs": A subject can only write objects 
at a security level that dominates the subject's level.

To apply these concepts to a DBMS it is necessary to determine the granularity of the objects 
protected by MAC, i.e., the storage objects. Security levels are then associated with these storage 
objects. Work on MLS databases has focused on four choices for assigning security levels to data 
stored in a relation. One can assign security levels to entire relations, to individual tuples (rows) of 
a relation, to individual attributes (columns) of a relation, or to individual elements of a relation. 
In the definitions below, the most general case is considered, in which security levels are assigned 
to individual data elements stored in relations. However, since tuple level labeling is used in all 
DBMS products evaluated to date, the concepts are also considered in the (simplified) context of 
tuple level labeling.

A relation schema in the multilevel context not only contains all its data attributes, but also includes 
the corresponding security level for each data attribute. Formal definitions of a multilevel relation 
schema and multilevel relations are as follows [Denning 87]:

Relation Schema: A multilevel relation schema has the following form:

R(A1, C1, A2, C2, ... , An, Cn).

Each Ai is a data attribute over some domain Di and Ci is the classification attribute of Ai. The 
domain of Ci, i = 1, ...,n is some set consisting of security levels.

If tuple level labeling is used, there will only be one classification attribute for the entire tuple:

R(A1, A2, ... , An, C).

For a multilevel logical relation schema R, there is a corresponding relation Rc per security level 
in the security lattice. A user having a clearance at a security level c sees the relation Rc, which 
contains data at security level c or below. More formally,

Relations: A relation at a security level c has the following form:

Rc(A1, C1, A2, C2, ... , An, Cn)

Rc consists of a set of tuples of the form (a1, c1, a2, .2.... ,an, cn), where each ai  lies in the domain 
Di or ai is null, c > ci, ci, i = 1 ... ,n. Even if ai is null, its classification attribute ci is never null.

When an attribute value ai is null, there are two reasonable possibilities for the corresponding 
security level value: ci could be assigned a value that is identical to c, or the security level of the 
attributes constituting the primary key. In this document, ci would be assigned a value consistent 
with the second possibility.

If the security level of the primary key value is not dominated by c in a tuple, then that tuple is not 
shown in Rc at all. If the security level of the primary key value is dominated by c, then that tuple 
is shown in Rc; however, any attribute value with a security level not dominated by c, is shown 
having a null value with the corresponding security level the same as that of the primary key value.

For tuple level labeling, Rc consists of those tuples whose security level is dominated by c.

These concepts can be better explained with the help of an example taken from [Jajodia 91].

Example 4. Consider the relation schema SOD given in Example 1. Starship is the primary key of 
the relation schema SOD, and the security levels are assigned at the granularity of individual data 
elements. The hierarchical order usually followed is Top Secret (TS), Secret (S), Confidential (C), 
and Unclassified (U). A user with a Secret clearance will see the entire multilevel relation SODS, 
while a user with an Unclassified clearance will see the Unclassified instance SODU as shown in 
Figure 3.1.

SODS



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration U

Talos U

Voyager U

Spying S

Mars S

SODU

STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration 

Talos U

Voyager U

<null>

<nulls> U

Figure 3.1: Different SOD Views Based on Access Class

3.3	THE CONCEPT OF PRIMARY KEY IN MULTILEVEL RELATIONS

The notion of a primary key is a fundamental concept in the world of single-level relational 
databases. The primary key is used to maintain integrity of relations, it is used during the database 
design, and it is also used for storage and retrieval purposes. The primary key for a single-level 
relation must satisfy the uniqueness property and the minimality property, as discussed in Section 
2.1. Entity integrity requires that the primary key serves as a unique identifier of each tuple in the 
relation and that it does not contain a null value. The uniqueness property can create covert 
channels as discussed in Section 4. One approach to avoiding these channels involves augmenting 
the user-defined primary key with security level attributes associated with the primary key 
attributes. However, in the remainder of this document it is assumed that there is a user-specified 
primary key consisting of a subset of the data attributes and not including the security level 
[Denning 87]. It is called the apparent primary key of the multilevel relation schema.

3.4	ENTITY INTEGRITY IN MULTILEVEL RELATIONS

A relation schema R will be assumed to have a user-defined apparent primary key consisting of 
one or more data attributes of R. It will be denoted by PK. The entity integrity property of the 
standard relational model can be extended to the multilevel environment by defining the three 
requirements given below, which are applicable only to element level classification [Denning 87]. 
The three requirements are automatically met for tuple level classification.

The first requirement is the same as for the standard relational model, that no tuple in an Rc have 
a null value for any attribute in PK. The second requirement states that the PK values should be 
uniformly classified; otherwise, the PK value would not be wholly non-null or wholly null for 
some security level. The third requirement states that the security level of values for the attributes 
not in PK must dominate the security level of the PK attributes; otherwise, there could be instances 
where non-null attributes would be associated with a null primary key when viewed below the level 
of the primary key. These three requirements can be more formally defined as follows:

A multilevel relation schema R is said to satisfy entity integrity, if for all relation instances Rc 
of R and, tuple t � Rc,

1.	If Ai  � PK, then t[Ai]  �null,

2.	If Ai, Aj � PX, then t[Ci] = t[Cj], i.e., PK is said to be uniformly classified, and

3.	If Ai  � PK, then t[Ci]  t[C[PK]] (where C[PK] is the classification of the apparent 
primary key PK).

3.5	REFERENTIAL INTEGRITY IN MULTILEVEL RELATIONS

As discussed in the previous section, a non-null foreign key value in a referencing relation should 
always have a matching primary key value in the referenced relation. In an MLS database, this 
requirement has implications for the relationship among the security levels of the attributes of the 
foreign key and the security level of the referenced primary key. In addition, the possible actions 
which could be taken to enforce referential integrity on update and deletion can introduce covert 
channels as discussed in Section 4. Relation schemas, in the following example, will be used to 
illustrate the different situations in which a security conflict may occur.

Example 5. Consider the multilevel relation schema PS given in Example 2. Person_Name is the 
apparent primary key of the relation schema PS, and Starship is the foreign key of PS, which refers 
to the relation schema SOD. Typical relation instances for SOD and PS are given in Figure 3.2. 
Note that in the example schema only the attribute names are part of the primary key and the 
foreign key. The respective security levels are not a part of the key. Therefore, there are some 
tuples with the security level of the foreign key in relation PS higher or lower than the security level 
of the corresponding primary key in relation SOD. The example includes such tuples to explain the 
conflicts arising when the security levels are at different levels.

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration U

Talos U

Voyager U

Spying S

Mars S

Apollo S

Spying S

Moon S

PS

PERSON_NAME

STARSHIP

James Kirk U

Enterprise U

Mr. Spock U

Voyager S

Tim McKelley U

Apollo U

Figure 3.2: Typical Relation Instances for SOD and PS

Recall the definition of referential integrity for standard relational databases:

Referential Integrity: If FK is a foreign key of R1 referencing R2, PK is the primary key of 
R2, t1 is a tuple of an instance R1 of R1, and t2 is a tuple of an instance R2 of R2, then

1.	t1 [FK] is either wholly null or wholly non-null, and

2.	Whenever t1[FK] is non-null, there is a tuple t2 in R2 such that t1[FK] = t2[PK].

For MLS databases we need to have this property be true for the database as seen from any security 
level. Assume tl [FK] is not wholly null as viewed from some security level. The first requirement 
above says that it must then be wholly non-null. If the attribute values making up FK did not all 
have the same security level, there would be some security level for which some of the attribute 
values in FK would be null and others non-null. Since this is not allowed, all attribute values in FK 
must have the same security level. If all attribute values of FK are null, then by convention they 
are assigned the same security level. This argument gives us the first rule for referential integrity.

Rule 1. The foreign key of the referencing relation must be uniformly classified (i.e., all 
attribute values that make up the foreign key must be assigned an identical security level).

This rule is automatically satisfied for tuple level labeling.

The second part of referential integrity requires that if the foreign key FK is not null then there is 
a matching primary key PK in the referenced relation R2. For this to be true for the database as 
seen from the security level of FK, the matching PK must be visible at the security level of FK. 
Hence, the security level of FK must dominate the security level of the matching primary key PK. 
This gives us the second rule of referential integrity.

Rule 2. The security level of the foreign key must dominate the security level of the primary 
key of the referenced tuple (i.e., C[FK] > C[PK]).

For tuple level labeling, this rule reduces to the requirement that the security level of the referenced 
tuple must be dominated by the security level of the referencing tuple.

PS

PERSON_NAME

STARSHIP

James Kirk U

Enterprise U

Mr. Spock U

Null U

Tim McKelley U

Apollo U

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration U

Talos U

Voyager U

Null U

Null U

Figure 3.3: Unclassified Instances of PS and SOD Relations

Example 6. Consider the relations SOD and PS as shown in Figure 3.2. An Unclassified user sees 
the two relations as given in Figure 3.3. For the Unclassified user, the referential integrity property 
has been violated because there is no Starship "Apollo" visible to the Unclassified user. From the 
Unclassified user's point of view either Starship "Apollo" does not exist, which is a referential 
integrity error, or it references a classified Starship that is not displayed to the user, which is a 
security error.

3.6	ENFORCEMENT OF INTEGRITY CONSTRAINTS

Most of the research work on the topics covered in this document has either focused on 
polyinstantiation as a mechanism to deal with primary key requirements and entity integrity or has 
dealt with the broader question of inference. Meadows did some early work on the conflicts of 
integrity and security that mainly considered approaches for maximizing integrity while 
eliminating inference channels [Meadows 88]. Polyinstantiation and inference research are 
covered in the appropriate TDI companion documents. However, there are several works dealing 
with aspects of database integrity which go beyond just entity and referential integrity and do not 
fit into those areas.

Notargiacomo and Wiseman have explored separation of duty as an approach to protect data from 
unauthorized modification within MLS databases [Notargiacomo 91; Wiseman 90]. The concept 
of applying separation of duty to integrity enforcement is to ensure that, before a modification to 
the state is made, sufficient people agree that it properly reflects the real world requirement. The 
fact that certain users are unlikely to collude with a particular change, an underlying assumption, 
is indicated by the way roles are assigned to users. Notargiacomo explores the issues of integrating 
an interpretation of the Clark-Wilson integrity model [Clark 87, 88] into a multilevel DBMS 
security policy. Her preliminary investigation raised issues on object granularity; interaction of 
MAC, DAC, and integrity policies; application of Clark-Wilson type controls to classes of users; 
and the need for nested transactions. Wiseman sees the high level abstract view of separation of 
duty as several people agreeing to change state. Integrity can be encouraged by enforcing 
constraints which ensure the state is always valid and by subjecting inputs to separation of duty.

Reind van de Reit and Beukering describe how constraints involving integrity and security can be 
specified in MOXUM, their active object-oriented knowledge-base system [van de Reit 94]. Their 
premise is that changes to the database should be governed by rules in the form of integrity 
constraints and security checks. In this case, integrity constraints refer to the quality of the data, 
while security constraints refer to protection and access rights. Both kinds of constraints are 
specified in MOKUM as Prolog predicates and are not separated. Each time some manipulation on 
an object or a collection mentioned in a constraint is performed (create/change/inspect/destroy), 
some check has to be performed. The Prolog scripts regulate access to object collections and 
enforce integrity constraints through triggers. This implies a need to extend the Trusted Computing 
Base to include the Prolog compiler which is problematic with respect to assurance.

In addition to considering the entity and referential integrity conflicts with security, Maimone and 
Allen provide alternatives to resolving problems that arise in maintaining transaction integrity and 
value constraints [Maimone 91]. A security conflict with transaction integrity may arise if a single 
transaction is designed so that some steps must perform write operations at different security 
levels. Value constraints are defined integrity rules that may restrict the valid values for a data 
element. A conflict arises when some existing data classified above the label of the user activating 
the constraint does not meet constraints defined after object creation. They make the distinction 
between the use of triggers and constraints for enforcing integrity rules. The utility of declarative 
constraints, including primary and foreign key and value or domain constraints, is that the 
constraint declares an invariant property, detailing the meaning of a consistent state.

Marks and Jajodia [Jajodia 94] have developed a technique to enforce certain integrity constraints 
and minimize the amount of sensitive information disclosed. They transform multilevel constraints 
into constraints that can be enforced at individual levels and approximate enforcement of the 
multilevel constraint.

SECTION 4

COVERT CHANNELS

The B2 or higher MAC requirements of the TCSEC specify that an MLS system must additionally 
guard against indirect accesses through information flows. It is recognized that some covert 
channels will exist in any system. The TCSEC provides guidelines on what actions must be taken 
for channels depending on the bandwidth of the channel. Enforcement of integrity constraints can 
create covert channels. These channels are discussed in this section. Interpretations indicating 
precisely what channels will be deemed acceptable for systems evaluated against various TCSEC 
levels will be developed as the Evaluation Community deals with specific vendor implementations.

4.1	PRIMARY KEY UNIQUENESS

Problems arise in multilevel relations when a user at a lower security level tries to enter a tuple with 
the same primary key value as that of an existing tuple at a higher security level or when a user 
tries to update the primary key attribute to a value that already exists at a higher level. This insert/
update cannot be allowed if primary key uniqueness is to be preserved. On the other hand, if the 
user is not allowed to insert the primary key value, then there exists a covert channel. The following 
example provides a concrete illustration.

Example 7. Consider the multilevel relation schema SOD of Example 4 in Section 3.2; the actual 
relation is the same as the Secret instance shown in Figure 3.3. Suppose the Unclassified user, who 
sees the Unclassified instance in Figure 3.3, attempts to update the missing values in the second 
tuple corresponding to the starship "Voyager." If the user is allowed to do this update, then there 
will be two tuples corresponding to the primary key value of Starship "Voyager" in the Secret 
instance, leading to a violation of the primary key constraint, as shown in Figure 4.1. But if the 
Unclassified user's attempt is rejected, then there is a channel. Since this is unacceptable, a way 
must be found to deal with the existence of both tuples in the Secret instance.



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration U

Talos U

Voyager U

Spying S

Mars S

Voyager U

Exploration U

Moon U

Figure 4.1: SOD After Insertion of Tuple Corresponding to Starship = "Voyager" by 
Unclassified User

Since the user can infer that a Secret tuple exists with the same primary key the user is attempting 
to insert, this channel can be viewed as an example of inference. However, it also represents a 
covert channel because a Secret process can insert or delete tuples with a given primary key and 
this action could be detected by the Unclassified user. To avoid this channel, both the Secret tuple 
and the Unclassified tuple for the starship "Voyager" must somehow co-exist in the instance at the 
Secret level.

These security considerations have led to the notion of polyinstantiation [Denning 87]. 
Polyinstantiation forces a relation to contain multiple tuples with the same primary key but 
distinguishable by their classification levels or by the non-primary key attributes of the relation 
[Lunt 91]. It is because the user designated primary key must be augmented with classification 
levels to maintain primary key uniqueness in a polyinstantiated database that we have used 
Denning'' term apparent primary key for the user-specified primary key. Jajodia contends that the 
use of polyinstantiation for cover stories needs to be confined to those cases where it is intended 
since uncontrolled use of polyinstantiation leads to further loss of integrity and confusion with the 
semantics of the relational data model [Jajodia 90].

The debate continues as to whether polyinstantiation is needed in multilevel relations or not 
[Sandhu 91]. If polyinstantiation is not required in multilevel relations, then there must be a 
solution to close channels. If polyinstantiation is used, then the question is how polyinstantiation 
should be managed. Burns maintains that as a result of the fundamental conflict with enforcing 
confidentiality and secrecy of information in an MLS database with integrity, DBMS products will 
have to be expanded to include the ability to correct the errors and inconsistencies introduced by 
polyinstantiation [Burns 90a]. A thorough discussion of all the issues associated with 
polyinstantiation is beyond the scope of this document, but is covered in another volume in this 
series: Polyinstantiation Issues in Multilevel Secure Database Management Systems [Poly 96]. For 
the purpose of this document, the discussion of polyinstantiation is confined to the impact it has on 
referential integrity.

4.2	ENFORCEMENT OF REFERENTIAL INTEGRITY RULES

Section 3 showed that for referential integrity in an MLS database, the security level of the foreign 
key must dominate the security level of the primary key of the referenced tuple (C [FK]   C[PX]). 
This requirement guarantees that the referenced primary key will be visible to any user who sees 
the foreign key as non-null. However, the situation is somewhat more complicated if the referenced 
relation is polyinstantiated. In this event, there may be more than one tuple with an apparent 
primary key matching FK. Some method must be used to uniquely and consistently determine 
which primary key will be considered to be the referenced primary key. One approach is to 
augment FK with the security level of its attributes (the tuple security level if tuple level labeling 
is used). If that approach is used, a matching PK will have the same security level as FX and the 
requirement on the relationship between security levels of PK and FK becomes C[FK] = C[PK].

Enforcement of referential integrity through the rules described in Section 2.2 can result in covert 
channels. These channels are discussed below. The discussion is divided into the two permitted 
cases: C[FK] = C[PK] and C[FK] > C[PK].

4.2.1	Enforcement of Integrity Rules When C[FK] = C[PK]

To study the enforcement of integrity rules when the security level of the referencing tuple and the 
security level of the referenced tuple are the same, we need to look at the cases of the four different 
levels of granularity in multilevel relations. For relations with relation level labeling or tuple level 
labeling, all the integrity rules are usable without modification because this case can be considered 
to be equivalent to relationships occurring in a single-level database. For attribute and element 
level labeling there is a potential channel for the CASCADFS-delete rule. All other rules can be 
enforced without any problem. This channel can be better explained with the help of an example.

Example 8. Consider the two relations SOD and PS as given in Figure 4.2. The security level of 
the foreign key in relation PS in this example is the same as the security level of the referenced 
primary key in relation SOD. For the second tuple in relation PS, an Unclassified user oily sees the 
attribute Person_Name. The user is not cleared to see the value of Starship for this tuple and also 
the user cannot see the corresponding referenced tuple in relation SOD. Suppose a Confidential 
user comes in and attempts to delete the second tuple in relation SOD where Starship = "Saratoga." 
If the delete rule specified is a CASCADES-delete, then the referencing tuple in PS is also deleted. 
An Unclassified user now will not see the attribute value Person_Name = "Mr. Spock" any more, 
and this causes a channel.

PS

PERSON_NAME

STARSHIP

James Kirk U

Enterprise U

Mr. Spock U

Saratoga C

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration C

Talos C

Saratoga C

Mining C

Rigel C

Figure 4.2: Relation PS and SOD when C[FK] = C[PK]

The channel in this case can be avoided if the equivalence of the security levels of the foreign key 
and the referenced primary key is extended. If the security level of the entire referencing tuple is 
the same as the security level of the entire referenced tuple, then no violations occur when 
enforcing the insert, delete, and update rules. This fact has been acknowledged in the SeaView 
model [Lunt 90] and the referential secrecy model given by Burns [Burns 90b]. Burns also suggests 
selective enforcement of referential integrity in those cases where the security level of both the 
referencing relation and the referenced relation are not the same, assuming that the channel either 
can be monitored or is deemed not to cause a serious threat.

4.2.2	Enforcement of Integrity Rules When C[FK] > C[PK]

Now the final case will be considered where the security level of the referencing tuple dominates 
the security level of the referenced tuple. Each of the integrity rules for insert, delete, and update 
will be considered individually, and the effect of the dominance of the referencing tuple's security 
level over that of the referenced tuple will be investigated. The effect of different levels of labeling 
granularity in multilevel relations upon enforcement of integrity will also be considered. 
Throughout this discussion, we will assume that either the relations are not polyinstantiated or a 
consistent method is employed to determine the unique primary key referred to by a foreign key.

1.	Element-Level Granularity - Each of the integrity rules for insert, delete, and update is 
examined individually for relations with element-level granularity, and conditions 
violating the security constraints are investigated.

a.	Delete Rule - As discussed in Section 2.2.1, the four delete rules for referential 
integrity in single-level relations are as follows:

i.	RESTRICTED-delete Rule

ii.	CASCADES-delete Rule

iii.	NULLIFIES-delete Rule

iv.	SET-DEFAULT-delete Rule

Each of these rules is considered in turn for applicability to multilevel relations labeled at the 
element level.

i.	RESTRICTED-delete Rule - The RESTRICTED-delete rule states that the referenced 
primary key tuple cannot be deleted as long as there is a corresponding referencing 
tuple somewhere in the database. For instance, consider the relations SOD and PS 
given in Figure 4.3.

In relation PS, the security level of the foreign key value Starship = "Voyager" dominates 
the security level of the primary key value in the relation SOD. According to the 
RESTRICTED-delete rule, as long as there is a tuple having foreign key value "Voyager" 
in PS, the tuple with primary key value "Voyager" cannot be deleted from the relation 
SOD. This gives rise to a channel, as there is a downward flow of information from the 
high-level referencing foreign key to the low-level subject attempting to delete the tuple 
containing the primary key. Therefore, the RESTRICTED-delete Rule violates secrecy 
when the security level of the foreign key dominates the security level of the primary key 
of the referenced tuple.

ii.	CASCADES-delete Rule - If the delete rule specified is the CASCADES-delete rule, 
then if the tuple in SOD with Starship = "Voyager" is deleted at the Unclassified level, 
then the tuple in PS with Starship = "Voyager" at the Secret level should also be 
deleted. In the relation instance of PS, given in Figure 4.3, Person_Name = "Mr. 
Spock" is at the Unclassified level in the tuple containing Starship = "Voyager" at the 
Secret level. Although the Unclassified user would not see any value for Starship in 
the PS tuple with Person_Name = "Mr. Spock," this tuple will be deleted as a result of 
the CASCADES-delete action. Therefore, the user will be able to infer that the tuple 
contained Starship = "Voyager." This is a channel. If the attribute value "Mr. Spock" 
were classified as Secret, there would have been no channel. Hence, the CASCADES-
delete rule fails in relations with element-level labeling and C[FK] > C[PK], if any 
non-foreign key attribute value in the referencing tuple is at a lower security level than 
the foreign key attribute value. Even though the CASCADES-delete rule is not invalid 
for all the cases, channels exist that cannot be covered or be removed. Hence, 
CASCADES-delete cannot be used for defining an integrity constraint in relations 
with element-level labeling which allow a foreign key to strictly dominate its 
corresponding primary key.

SOD



STARSHIP

OBJECTIVE

DESTINATION

Enterprise U

Exploration U

Talos U

Voyager U

Spying S

Mars S

Apollo S

Spying S

Moon S

PS

PERSON_NAME

STARSHIP

James Kirk U

Enterprise U

Mr. Spock U

Voyager S

Figure 4.3: Relations SOD and PS without Polyinstantiation

iii.	NULLIFIES-delete Rule - If the delete rule specified is NULLIFIES-delete, then 
the value of Starship = "Voyager" in relation PS is set to null when the tuple in SOD 
for Starship = "Voyager" is deleted. This does not conflict with the security 
constraints, as long as write-ups are allowed, since there would not be a downward 
flow of information.

iv.	SET DEFAULT-delete Rule - The argument for the SET DEFAULT-delete rule is 
the same as for the NULLIFIES-delete rule. As previously noted, the SET 
DEFAULT rule is equivalent to the NULLIFIES rule when null is specified as the 
default.

In summary, when the foreign key value is higher than the security level of the primary key 
value, then the NULLIFIES-delete rule and the SET DEFAULT-delete do not create 
downward information flows. However, the RESTRICTED-delete and CASCADES-
delete rules can result in covert channels.

b.	UPDATE Rule - As discussed in Section 2.2.2, the four update rules for referential 
integrity in single-level relations are as follows:

i.	RESTRICTED-update Rule

ii.	CASCADES-update Rule

iii.	NULLIFIES-update Rule

iv.	SET DEFAULT-update Rule

The following paragraphs discuss the application of the update rules to multilevel relations labeled 
at the element level.

i.	RESTRICTED-update Rule - Consider the relations SOD and PS given in Figure 
4.2. In relation PS, the security level of the foreign key value Starship = "Voyager" 
dominates that of the primary key value in the relation SOD. According to the 
RESTRICTED-update rule, as long as there is a tuple having foreign key value 
"Voyager" in PS, the primary key value "Voyager" cannot be updated in the 
relation SOD. This gives rise to a channel because there is flow of information from 
the high-level referencing foreign key to the low-level subject attempting to delete 
the tuple containing the primary key. Therefore, the RESTRICTED-update Rule 
will not work when updating a referenced tuple if the security level of the 
referencing tuple dominates the security level of the referenced tuple.

ii.	CASCADES-update Rule - The CASCADES-update Rule states that if the primary 
key value Starship = "Voyager" in SOD is updated, then the foreign key value 
Starship = "Voyager" in PS will also be updated. This does not conflict with the 
security constraints, as long as write-ups are allowed, since there would not be a 
downward flow of information.

iii.	NULLIFIES-update Rule - The NULLIFIES-update Rule specifies that the value of 
Starship = "Voyager" in relation PS be set to null if Starship = "Voyager" in SOD 
is updated. Again, this does not conflict with the security constraints, as long as 
write-ups are allowed, since there would not be a downward flow of information.

iv.	SET DEFAULT-update Rule - The SET DEFAULT-update Rule does not violate 
any security or integrity constraints when the security level of the foreign key 
dominates the security level of the primary key. The explanation is the same as for 
the NULLIFIES-update rule.

In summary, CASCADES-update, NULLIFIES-update, and SET DEFAULT-update do 
not result in downward information flow. The RESTRICTED-update rule can result in a 
covert channel.

c.	INSERT Rule - The insert rule for integrity states that the insertion of a foreign key 
value should comply with the referential integrity rules; that is, each foreign key value 
in the referencing relation should have an identical primary key value in the referenced 
relation. In MLS databases, it is important to ensure that there is no downward flow of 
information when the insertion is made. If the security level of the referencing tuple 
(foreign key value) dominates the security level of the referenced tuple (primary key 
value), then there is no such possibility of a channel. If a higher user attempts to insert 
a foreign key value, the user's insertion is accepted or rejected based on the presence 
or absence of the referenced value at the lower security level. There will be only an 
upward flow of information, which means that both integrity and security rules are 
satisfied. It should be noted that, unlike with polyinstantiated relations, there is no 
confusion while inserting the tuples in the two relations.

SOD



No.

STARSHIP

OBJECTIVE

DESTINATION

TC

1

Enterprise

Exploration

Talos

U

2

Enterprise

Spying

Mars

S

PS

No.

PERSON_NAME

STARSHIP

TC

3

James Kirk

Enterprise

U

4

Mr. Spock

Enterprise

S

Figure 4.4: Relations with Tuple-Level Granularity

2.	Tuple-Level Granularity - The argument for referential integrity control in relations with 
tuple-level granularity is the same as the discussion above for element-level granularity. The only 
difference is that instead of each data element having an individual security level, the entire tuple 
in the relation is assigned a security level as shown in Figure 4.4. As is the case for element-level 
granularity, a security conflict occurs when the RESTRICTED-update/delete option is enforced. 
There is a downward flow of information when a low user tries to update/delete a target value, and 
is allowed to do so depending on the absence of a matching referencing tuple at a higher level. All 
other integrity rules are valid for relations with tuple-level granularity. The problem with 
CASCADES-delete that occurs for element-level granularity does not occur with tuple-level 
granularity because, for tuple-level granularity, each element in the tuple is explicitly assumed to 
have the same security level as defined in the tuple class. As such, a user will never be in the 
situation where he can view some attributes of a tuple but not others and then witness the tuple 
vanish due to a cascading delete on attributes that the user is not cleared to see, which would be a 
covert channel due to the inference of the high attribute's value.

3.	Attribute-Level Granularity - As described earlier, attribute-level granularity means that each 
attribute in a relation is assigned a single security level. All values of an attribute are classified at 
the same level of security across all tuples in the relation. From the discussion in Section 3.5, to 
maintain referential integrity, the security level of the foreign key attribute in the referencing 
relation must dominate the security level of the primary key attribute in the referenced relation.

The case to be considered is where the security level of the foreign key attribute strictly dominates 
the security level of the apparent primary key attribute. In this case, the relations SOD and PS are 
as given in Figure 4.5.

SOD



No.

STARSHIP U

OBJECTIVE S

DESTINATION U

1

Enterprise

Exploration

Talos

2

Voyager

Spying

Mars

PS

No.

PERSON_NAME U

STARSHIP S

3

James Kirk

Enterprise

4

Mr. Spock

Enterprise

Figure 4.5: Relations with Attribute-Level Granularity

Following the discussion earlier, it can be observed that all the integrity rules can be applied to the 
case above except for the RESTRICTED-delete or the RESTRICTED-update rule. Under 
RESTRICTED-update or delete, whenever a lower subject tries to update or delete the tuple 
containing a particular primary key attribute value, the attempt is accepted or rejected based on the 
presence of a matching value in the foreign key attribute at the higher security level. This gives rise 
to a channel.

4.	Relation-Level Granularity - As defined earlier, a relation with relation-level granularity has 
a single classification level defined for the entire relation, or in other words, all data elements in 
the relation are at the same security level.

For instance, consider the relation schema SOD, given in Example 4, and the relation 
schema PS, given in Example 6. Relation PS references relation SOD, with Starship being 
the foreign key attribute. The security level of the primary key "Starship" (i.e., C[PK]) is 
the same as the security level of the relation SOD, and the security level of the foreign key 
"Starship" (i.e., C[FK]) is the same as the security level of the relation PS. Based on the 
restrictions derived in rule 2 in Section 3.5, the security level of the foreign key should 
always dominate the security level of the primary key. Therefore, for relation-level 
granularity, the security level of the relation PS should dominate the security level of the 
relation SOD.

Let the security level of relation SOD be Unclassified and of PS be Secret. Then C[FK] = 
Secret and C[PK] = Unclassified (i.e., C[FK] > C[PK]). From the discussion in Section 3.5, 
it can be seen that, if C[FK] > C[PK], then all integrity rules except RESTRICTED-delete 
and RESTRICTED-update can be used, without any covert channels.

The table below gives a summary of the integrity rules that apply to different levels of granularity 
without compromising secrecy by permitting downward information flows. In the case of 
polyinstantiated relations it is necessary in all cases that there be a method to unambiguously 
determine which instance of the apparent key is referenced.

Level of Granularity

Element

Tuple

Attribute

Relation

Insert Rule

OK

OK

OK

OK

Delete Rules:

RESTRICTED-delete

Channel

Channel

Channel

Channel

CASCADES-delete

Channel

OK

OK

OK

NULLIFIES-delete

OK

OK

OK

OK

SET-DEFAULT-
delete

OK

OK

OK

OK

Update Rules:

RESTRICTED-update

Channel

Channel

Channel

Channel

CASCADES-update

OK

OK

OK

OK

NULLIFIES-update

OK

OK

OK

OK

SET-DEFAULT-
update

OK

OK

OK

OK

Table 4.1: Summary of Covert Channels in Referential Integrity Rules for C[FK] > C[PK]

4.3	RELATION TO DBMS ARCHITECTURE

A Trusted Computing Base (TCB) consists of one or more sub-elements that together enforce a 
security policy over a system. Complex systems distribute policy enforcement to various sub-
elements. While determining the trust characteristics of a complex system on the basis of a 
collection of subparts is not well understood, there are approaches for arguing about composition 
of systems.

The approach used in the TDI is to view the system as being composed of hierarchically-ordered 
systems. There is a "privilege" hierarchy characterized by dependency. The construct developed 
for dealing with layered systems is TCB subsets. A TCB subset enforces a security policy over a 
set of resources for that layer, and may or may not include hardware. If a TCB subset can be shown 
to be constrained and unprivileged relative to the more primitive TCB subset from which it obtains 
resources, then the scope of the covert channel analysis can be limited. An example of this 
approach is the SeaView prototype.

SRI International developed the SeaView prototype multilevel RDBMS to validate the SeaView 
theoretical model and to demonstrate that the prototype is suitable for engineering development 
[Hsieh 93]. The design approach provides users with element-level labeling. SeaView constructs 
multilevel relations as views over stored single-level relations. The single-level relations are stored 
in files managed by an underlying multilevel operating system. Thus, individually labeled data 
elements need not be stored in individually labeled storage objects. The SeaView approach allows 
multilevel database operations to be decomposed into corresponding single-level operations on the 
single-level relations. The decomposition is transparent to the user, who considers the multilevel 
relations to be stored relations. Thus, the SeaView model extends entity and referential integrity to 
multilevel relations. It also allows application dependent integrity rules to be defined on multilevel 
relations; and it ensures that updates of multilevel relations are well defined. In addition, the 
SeaView model constrains multilevel relations with polyinstantiation integrity, which specifies 
consistency for polyinstantiated tuples and elements.

In the SeaView approach, the underlying architecture guards against covert channels during 
enforcement of entity and referential integrity. This is because the DBMS instance operating on 
behalf of a subject is untrusted with respect to the underlying operating system MAC policy (i.e., 
it can only read data with a security level dominated by the subject's level and can only write data 
with a security level dominating the subject's level). SRI utilized Trusted Oracle OS MAC Mode, 
which has been evaluated as a constrained TCB subset architecture [Oracle 94].

On the other hand, a secure DBMS can be built with MAC enforcement done in the DBMS, not 
just the underlying operating system. In this approach, the DBMS will have the privilege to violate 
the operating system's MAC controls. With this architecture, called a trusted subject architecture, 
the DBMS designer has to make a tradeoff between channel free enforcement of entity and 
referential integrity constraints, or enforcement of the constraints in a manner which allows 
selected channels. In the latter case, the constraint enforcement mechanism must be carefully 
analyzed to make sure that the downward information flows are thoroughly understood and that 
they are acceptable for the target environment or evaluation class. For example, Trusted Oracle7 
DBMS MAC Mode (which uses the trusted subject architecture) was successfully evaluated at 
Class B1 [Oracle 94]. In DBMS MAC Mode, entity and referential integrity can be enforced. An 
audit event was added to Trusted Oracle7 to detect use of potential covert channels.

SECTION 5

SUMMARY

Entity integrity and referential integrity are two important integrity constraints that should be 
enforced by the DBMS. While entity integrity is necessary for preserving correctness of data 
within a relation, referential integrity is required for maintaining interrelation integrity in the 
relational data model. In this document, these concepts have been extended to multilevel DBMSs.

The extension of the concept of referential integrity from single-level relations to multilevel 
relations is not straightforward. This is because restrictions are needed to provide referential 
integrity control in multilevel DBMSs without compromising secrecy. The basic requirement for 
referential integrity is that each referencing foreign key value must have an identical target primary 
key value in the referenced relation. An additional requirement for multilevel relations is that each 
foreign key and primary key should be uniformly classified (i.e., all attributes included in a key 
should have the same security level) and each foreign key dominates its referenced primary key.

From the discussion in the document, it can be concluded that enforcing referential integrity, when 
the security level of the foreign key is equal to the security level of the referenced primary key, is 
simple and without any ambiguity. All integrity rules apply in this case, whether the relations allow 
polyinstantiation or not. When polyinstantiation is allowed, some method such as including the 
security level of the primary and foreign key values as part of the key must be used to differentiate 
references, and allow the referential integrity rules to be enforced.

Referential integrity completely fails when the security level of the foreign key does not dominate 
the security level of the primary key. When the security level of the foreign key strictly dominates 
the security level of the referenced primary key, some of the integrity rules for actions to be taken 
upon deletion or modification of a key value can be applied without channels, with some 
differences based on labeling granularity.

Inclusion of a mechanism which enforces integrity across security levels in Class B2 and above 
DBMSs may not be feasible due to conflicts with the covert channel requirements. However, with 
the successful evaluation of Trusted Oracle7 DBMS MAC Mode with an unmodified integrity 
mechanism, precedence has been set for Class B1 DBMSs.

REFERENCES

[ANSI 92]	ANSI. Database Language SQL2. In ANSI X3.135-1992, American National 
Standards Institute, New York. December 1992.

[ANSI 94]	ANSI. SQL3 - Working Draft. Draft Version, Available From X3 Secretariat, 
Computer and Business Equipment Manufacturers Association (CBEMA), 1250 
Eye St. N.W., Suite 200 Washington, D.C. 20005-3992. September 1994.

[Audit 96]	National Computer Security Center, Auditing Issues in Secure Database 
Management Systems, NCSC Technical Report-005, Volume 4/5, May 1996.

[Bell 76]	D. E. Bell and L. J. LaPadula. Secure Computer Systems: Unified Exposition and 
Multics Interpretation, The MITRE Corporation. March 1976.

[Burns 90a]	R. K. Burns. Integrity and Secrecy: Fundamental Conflicts in the Database 
Environment. In Proceedings of the Third RADC Database Security Workshop, 
Castille, NY. 1990.

[Burns 90b]	R. K. Burns. Referential Secrecy. In Proceedings of the IEEE Symposium on 
Security and Privacy, IEEE Computer Society Press. May 1990.

[Clark 87]	D. D. Clark and D. R. Wilson. A Comparison of Commercial and Military 
Computer Security Policies. In Proceedings of the IEEE Symposium on Security 
and Privacy, Oakland, CA. May 1987.

[Clark 88]	D. D. Clark and D. R. Wilson. Evolution of a Model for Computer Integrity. In 
Proceedings of the 11th National Computer Security Conference, Baltimore, 
MD. October 1988.

[DAC 96]	National Computer Security Center, Discretionary Access Control Issues in 
High Assurance Secure Database Management Systems, NCSC Technical 
Report-005, Volume 5/5, May 1996.

[Date 86]	C. J. Date. An Introduction to Database Systems, Vol. I, 4th Edition, Addison-
Wesley, Reading, MA. 1986.

[Date 90]	C. J. Date. Referential Integrity and Foreign Keys: Further Considerations. In 
Relational Database Writings 1985-1989, Addison-Wesley, pp. 99-184. 1990.

[Denning 87]	D. E. Denning, T. F. Lunt, R. R. Schell, M. Heckman, and W. R. Shockley. "A 
Multilevel Relational Data Model," Proceedings of the 1987 IEEE Symposium 
on Security and Privacy, IEEE Computer Society Press, pp. 220-234. 1987.

[DoD 85]	Department of Defense Trusted Computer System Evaluation Criteria, DoD 
5200.28-STD, Washington, DC. December 1985.

[Hsieh 93]	D. Hsieh, T. Lunt, and P. Boucher. The SeaView Prototype. RL-TR-93-216 Final 
Technical Report, SRI International. November 1993.

[Horowitz 92]	B. M. Horowitz. A Run-Time Execution Model for Referential Integrity 
Maintenance. In Proceedings of the 8th International Conference on Data 
Engineering, Tempe, AZ, pp. 548-556. February 1992.

[Inference 96]	National Computer Security Center, Inference and Aggregation Issues in Secure 
Database Management Systems, NCSC Technical Report-005, Volume 1/5, 
May 1996.

[Jajodia 90]	S. Jajodia, and R. Sandhu. Polyinstantiation Integrity in Multilevel Relations. In 
Proceedings of the 1990 IEEE Symposium on Security and Privacy, Oakland, 
CA. May 1990.

[Jajodia 91]	S. Jajodia, and R. Sandhu. Toward a Multilevel Secure Relational Data Model. 
In Proceedings of ACM SIGMOD International Conference on Management of 
Data, Denver, CO, pp. 50-59. May 1991.

[Jajodia 94]	S. Jajodia and D. G. Marks. Maintaining Secrecy and Integrity in Multilevel 
Databases: A Practical Approach. In Proceedings of the 18th National 
Information Systems Security Conference, Baltimore, MD. Oct. 10-13 1995.

[Khoshafian 86]	S. N. Khoshafian and G. P. Copeland. Object Identity. In Proceedings for 
OOPSLA 1986. pp. 406-416. September 1986.

[Lunt 90]	T. F. Lunt, D. E. Denning, R. R. Schell, M. Heckman, and W. R. Shockley. The 
SeaView Security Model. In IEEE Transactions on Software Engineering, Vol. 
16, No. 6, pp. 593-607. June 1990.

[Lunt 91]	T. F. Lunt, and D. Hsieh. Update Semantics for a Multilevel Relational Database 
System. In Database Security, IV: Status and Prospects, S. Jajodia and C. E. 
Landwehr (editors), Elsevier Science Publishers B. V. (North Holland), IFIP, pp. 
281-296.1991.

[Maimone 91]	B. Maimone and R. Allen. Methods for Resolving the Security vs. Integrity 
Conflict. In Research Directions in Database Security, IV: Proceedings of the 
Fourth RADC Workshop, Rae Burns (editor). April 1991.

[Markowitz 90]	V. M. Markowitz. Referential Integrity in Relational Database Management 
Systems: A Comparative Study. Preprint. 1990.

[Meadows 88]	C. Meadows and S. Jajodia. Integrity Versus Security in Multi-Level Secure 
Databases. In Database Security Status and Prospects, ed. C. Landwehr, North 
Holland. 1988.

[Notargiacomo 91] L. Notargiacomo. Database Integrity: Based on the Clark-Wilson Integrity 
Model. In Proceedings of the 3rd RADC Database Security Workshop. 1991.

[Oracle 94]	Oracle7 and Trusted Oracle7 Final Evaluation Report, NCSC-EPL-94/004, C-
Evaluation Report No. 07-95, Library No. S242,198, National Computer 
Security Center, 5 April 1994.

[Poly 96]	National Computer Security Center, Polyinstantiation Issues in Multilevel 
Secure Database Management Systems, NCSC Technical Report-005, Volume 
3/5, May 1996.

[Sandhu 91]	R. Sandhu and S. Jajodia. Honest Databases That can Keep Secrets. In 
Proceedings 14th National Computer Security Conference, Washington, D.C. 
Oct. 1991.

[TDI 91]	Trusted Database Management System Interpretation of the Trusted Computer 
System Evaluation Criteria, NCSC-TG-021, National Computer Security 
Center. April 1991.

[van de Reit 94]	R. van de Reit and J. Beukering. The Integration of Security and Integrity 
Constraints in MOKUM. In Proceedings of the 8th IFIP 11.3 WG on Database 
Security. Bad Sdzdetfurth, Germany, 23-26 August 1994.

[Wiseman 90]	S. Wiseman. The Control of Integrity in Databases. In Proceedings of the 4th 
IFIP 11.3 WG on Database Security, Halifax, England, 18-21 September 1990.
Rank
Person_Name
Primary key
PR
Foreign key
Primary key
Starship
Person_Name
Foreign key
PS
Primary key
Starship
Objective
Destination
SOD
Keith F. Brewster

Acting Chief, Partnerships and Processes
May 1996