Variant domains and variant maps in a versioned database management system

Abstract

A method is provided in a versioned database management system for allowing parts to be versioned according to different variant hierarchies, and for maintaining correct configurations of versions of parts as those parts are drawn down, changed, and promoted. Each version of a part is associated with a variant domain. Each variant domain is represented by a single variant hierarchy whose levels can be used to reference versions of parts in that variant domain and controls how versions of parts in that variant domain are drawn down, changed, and promoted. Variant domain default groups are provided so that tools may add new parts without specifying the variant domains to which the parts are to belong. In order to control which versions of parts and from which version domains are visible, variant maps are defined by the user installation. When a change is made for one configuration, it is simultaneously made in any other configuration identified by a variant map which includes the same variant ID. A variant map thus constructed is used by the VDMS to determine the variant hierarchy level to which any instances created belong, and to determine which instances in a promote group are promoted and to which hierarchy level they are promoted.

Claims

Having thus described the invention, what is claimed is:

1. A machine-readable program storage device tangibly embodying a program of instructions executable by a machine to perform method steps to provide simultaneous visibility to a plurality of variant hierarchies in a versioned data management system, said method steps comprising the steps of:

associating parts with variant domains, each part associated with a respective variant domain;

representing variant domains by variant hierarchies;

upon creation of a new variant of a part associating with the new variant a variant ID included in the variant hierarchy that represents the variant domain associated with the part:

upon drawing down a new variant of a part from an existing variant of the part, associating with the new variant a variant ID signifying a lower level in the variant hierarchy than the variant ID of the existing variant on the same branch of the variant hierarchy that represents the variant domain associated with the part; and

representing views of the parts by variant maps, each variant map including a set of variant IDs, each variant ID belonging to a different variant domain.

2. The program storage device of claim 1, wherein the method steps further include the steps of:

ordering each set of variant maps, each set including variant IDs from the same set of variant domains, so that the variant IDs in each variant domain appear in the set of maps in the same order as they appear in the branches of their respective variant hierarchies; and

upon promoting a variant of a part, associating with the promoted variant the variant ID for the variant domain of the part in the next higher variant map in the ordered set of variant maps which include variant identifiers from the same set of variant domains.

3. The program storage device of claim 1, wherein responsive to a request to retrieve a part the variant IDs in the variant map identify the search path which determines the version selected.

4. The program storage device of claim 1, wherein all current versions of a part are associated with the same variant domain.

5. The program storage device of claim 1, wherein each variant domain is represented by a single variant hierarchy.

6. The program storage device of claim 1, wherein each variant ID is defined in exactly one variant hierarchy.

7. The program storage device of claim 1, wherein the method steps further comprise the steps of:

providing variant domain default groups for specifying default variant domains for parts added to the versioned data management system without specification of a variant domain;

associating variant domain default groups with part types;

associating default variant domains with variant domain default groups; and

upon addition of a part having no variant domain specified, associating the part with the default variant domain specified by the variant domain default group of its part type.

8. The program storage device of claim 1, wherein every part type in the versioned data management system is associated with one variant domain default group.

9. The program storage device of claim 1, wherein the method steps further comprise the step of, responsive to an alteration of a part in a view of the data, applying the alteration to the part in any other view of the data identified by a variant map which includes the same variant ID as the variant map of the view of the data to which original alteration was made.

10. The program storage device of claim 9, wherein alteration includes any of add, update, delete, and promote.

11. A combination operable in conjunction with a digital processing apparatus to provide simultaneous visibility to a plurality of variant hierarchies in a versioned data management system, said combination comprising:

a data storage medium operable in conjunction with a data storage system of the digital processing apparatus;

said data storage medium having resident thereon a program of machine-readable instructions executable by the digital processing apparatus to perform method steps comprising:

associating parts with variant domains, each part associated with a respective variant domain;

representing variant domains by variant hierarchies;

upon creation of a new variant of a part associating with the new variant a variant ID included in the variant hierarchy that represents the variant domain associated with the part:

upon drawing down a new variant of a part from an existing variant of the part, associating with the new variant a variant ID signifying a lower level in the variant hierarchy than the variant ID of the existing variant on the same branch of the variant hierarchy that represents the variant domain associated with the part; and

representing views of the parts by variant maps, each variant map including a set of variant IDs, each variant ID belonging to a different variant domain.

12. The combination of claim 11, wherein the method steps further comprise the steps of:

ordering each set of variant maps, each set including variant IDs from the same set of variant domains, so that the variant IDs in each variant domain appear in the set of maps in the same order as they appear in the branches of their respective variant hierarchies; and

upon promoting a variant of a part, associating with the promoted variant the variant ID for the variant domain of the part in the next higher variant map in the ordered set of variant maps which include variant identifiers from the same set of variant domains.

13. The combination of claim 11, wherein responsive to a request to retrieve a part the variant IDs in the variant map identify the search path which determines the version selected.

14. The combination of claim 11, wherein all current versions of a part are associated with the same variant domain.

15. The combination of claim 11, wherein each variant domain is represented by a single variant hierarchy.

16. The combination of claim 11, wherein each variant ID is defined in exactly one variant hierarchy.

17. The combination of claim 11, wherein the method steps further comprise the steps of:

providing variant domain default groups for specifying default variant domains for parts added to the versioned data management system without specification of a variant domain;

associating variant domain default groups with part types;

associating default variant domains with variant domain default groups; and

upon addition of a part having no variant domain specified, associating the part with the default variant domain specified by the variant domain default group of its part type.

18. The combination of claim 11, wherein every part type in the versioned data management system is associated with one variant domain default group.

19. The combination of claim 11, wherein the method steps further comprise the steps of:

responsive to an alteration of a part in a view of the data, applying the alteration to the part in any other view of the data identified by a variant map which includes the same variant ID as the variant map of the view of the data to which original alteration was made.

20. The combination of claim 19, wherein alteration includes any of add, update, delete and promote.

21. An apparatus for providing simultaneous visibility to a plurality of variant hierarchies in a versioned data management system, said apparatus comprising:

a digital data processor;

a data storage device, tangibly embodying a program of instructions executable by the digital data processor to perform method steps to provide simultaneous visibility to a plurality of variant hierarchies in a versioned data management system;

said method steps comprising the steps of:

associating parts with variant domains, each part associated with a respective variant domain;

representing variant domains by variant hierarchies;

upon creation of a new variant of a part associating with the new variant a variant ID included in the variant hierarchy that represents the variant domain associated with the part:

upon drawing down a new variant of a part from an existing variant of the part, associating with the new variant a variant ID signifying a lower level in the variant hierarchy than the variant ID of the existing variant on the same branch of the variant hierarchy that represents the variant domain associated with the part; and

representing views of the parts by variant maps, each variant map including a set of variant IDs, each variant ID belonging to a different variant domain.

22. An apparatus to provide simultaneous visibility to a plurality of variant hierarchies in versioned data management system, said apparatus comprising:

a digital data processor programmed to perform the following steps:

associating parts with variant domains, each part associated with a respective variant domain:

representing variant domains by variant hierarchies;

upon creation of a new variant of a part associating with the new variant a variant ID included in the variant hierarchy that represents the variant domain associated with the part:

upon drawing down a new variant of a part from an existing variant of the part, associating with the new variant a variant ID signifying a lower level in the variant hierarchy than the variant ID of the existing variant on the same branch of the variant hierarchy that represents the variant domain associated with the part; and

representing views of the parts by variant maps, each variant map including a set of variant IDs, each variant ID belonging to a different variant domain.

Description

FIELD OF THE INVENTION

This invention relates in general to computer database management systems, and in particular to a database management system which manages multiple versions of data.

BACKGROUND OF THE INVENTION

Modern computer installations generate, manipulate, and store enormous quantities of data. Data base management systems have emerged as an indispensible component of such installations, serving the purpose of promoting efficient data storage and program design, enhancing file maintenance and modification, and eliminating data redundancy. The typical data base management system (DBMS) includes programs which interface with designers and users, accept and understand models or tables for subsequent use in organizing data, organize data according to the models or tables, store and retrieve the data in the actual data base contained in a computer storage subsystem, perform queries on the data, and generate reports based on the stored data.

A DBMS may be designed to store data according to any of a variety of data models, where the data model is the basic organizational concept for the underlying data base. These models, or schemas, for data base organization can be divided into several different classes, including hierarchical, network, relational, and entity-relationship. A detailed discussion of these types of databases may be found in "The Database Book," by Mary E. S. Loomis, Macmillan Publishing Company, New York, N.Y. 10022 (1987). The present invention is applicable to all of the above database schemas. The preferred embodiment is described with particular reference to the entity-relationship modelling methodology provided by the Repository Manager/MVS product, which uses the DB2 relational DBMS as a back end to manage the storage and retrieval data on the computer hardware. Entity-relationship databases are discussed in "The Entity-Relationship Model--Towards a Unified View of Data." by Peter Chen. ACM Trans. on Data Base Systems. Vol. 1 (1976). Relational databases and DB2 in particular is discussed in "IBM Database 2: General Information." IBM Publication GC26-4373 (1990). The Repository Manager/MVS product is discussed in "Repository Manager: Concepts and Facilities." IBM Publication SR21-3608 (1990).

A significant problem in maintaining any data base whose data entries represent objects, events, people, or relationships in the real world, is that although those things may change over time, the typical DBMS maintains only a single version of any given entry, making it impossible to concurrently represent a thing in its past, present, and future states. A second significant problem, which arises in maintaining a data base which is shared among a plurality of users, involves the toleration of concurrent but independent work on the same data entries by different users without sacrificing the semantic consistency of the data. Yet a third problem in maintaining a data base involves maintaining a record of the state of the data base itself as it existed at given times in the past. Such information is often needed for error recovery and for audit-trail purposes. Typical solutions to this problem involve taking "snapshots" of the data base and logging change activity, so that if necessary the data base can be "reconstructed" as it existed at some point in the past. This reconstruction is usually a time-consuming batch procedure, and a system so constructed cannot allow the past and current data bases to be accessed concurrently.

A solution to all of these problems is to maintain versions of the data entries. These versions may correspond to the different states of the real-world things represented, or to work in progress by different users. Such an approach is called versioning, and in general requires that the DBMS control the creating of the versions and all access to them, both to assure the semantic consistency of the data in all its versions, and to free users from the need to deal with the additional complexity that such a versioning scheme requires. Users of non-versioned data base systems sometimes simulate versioning by giving qualified names to the data base entries. However, this approach is undesirable, because it conceals from the DBMS the true identity of the things represented, and makes it impossible for the DBMS to verify the semantic consistency of the data base.

The generally preferred approach to implementing versioning is to provide direct versioning of entries in the DBMS, with the versioning managed by the DBMS to preserve the semantic validity of the data in the system. Such a system provides both parallel and serial versioning, with the capability for the user to define a hierarchy of versions, and to direct the DBMS to move versions of data from one hierarchy level to another. It also provides historical versioning of the database, allowing the user to view the data as it existed at any arbitrarily-selected time in the past. It provides a simplified programming interface that allows a user tool to interact with the data as though it were not versioned, the specification of which version is seen being made outside the program.

For a VDMS to serve the needs of a user community, it must tolerate the co-existence of multiple approaches to versioning, some or all of which may not be complementary. This is because different projects, or different processes, dealing with the same entity and relationship types, need variant hierarchies having different topologies. For example, the program development process for the Payroll project, which is large, may require four levels, with a variant hierarchy of: ##STR1## The smaller inventory project may need only three levels. Its variant hierarchy would be: ##STR2##

Parts from both projects must sometimes be accessed simultaneously, but a single variant hierarchy that satisfies both projects would require a superfluous "Integration" version level and promotions through that level for parts in the Inventory project.

Thus, multiple hierarchies would generally appear to be a desirable feature in a VDMS. However, simply defining multiple hierarchies creates two new problems: determining which parts belong to which hierarchy; and allowing visibility to a tool of only those parts in a certain hierarchy or hierarchies. For instance, a user working on the Inventory project probably would not want visibility to Payroll parts, while a project administrator might need to see parts from all projects.

Heretofore, no method has been available which solves these problems and thus provides a VDMS with simultaneous visibility to multiple variant hierarchies.

SUMMARY OF THE INVENTION

The present invention is directed to a method for allowing parts, including those within the same part type, to be versioned according to different variant hierarchies, and for maintaining correct configurations of versions of parts, where each configuration may contain parts versioned according to different versioning hierarchies, as those parts are drawn down, changed, and promoted. Each version of a part is associated with a variant domain, which is a grouping or classification of parts. A version is said to belong to the variant domain with which it is associated. In the preferred embodiment, all currently existing versions of a part belong to the same variant domain. Each variant domain is represented by a single variant hierarchy whose levels, referred to hereafter as "variant IDs", can be used to reference versions of parts in that variant domain and controls how versions of parts in that variant domain are manipulated, including drawn down, changed, and promoted. In the preferred embodiment, each variant ID is part of exactly one variant hierarchy and each variant domain is represented by a single variant hierarchy.

So that tools may add new parts without specifying the variant domains to which the parts are to belong, the present invention further provides variant domain default groups. Every part type must belong to one of these groups. At execution time a variant domain ID value, provided by the user installation, is associated with each group. This value is used by the VDMS as a default variant domain for new parts which are added with no variant domain value supplied. For example, assume that all part types having to do with program development belong to a default group named "PROGGRP". When a user begins working on the Payroll project, the value "Payroll" is associated with "PROGGRP". Then, when the user adds a new part without explicitly specifying the variant domain, the VDMS automatically adds it to the "Payroll" variant domain.

In order to control which versions of parts and from which version domains are visible, variant maps are defined by the user installation. Variant maps identify configurations of versions of parts. A configuration consists of parts belong to a combination of variant domains, which may include a single variant domain, each viewed from a particular level of its variant hierarchy. Each variant map consists of a set of variant IDs, each of which belongs to a different variant domain. In the preferred embodiment, configurations are defined by a search path through the variant hierarchy beginning at the variant ID specified in the variant map for the variant domain of a part. When a change is made for one configuration, it is simultaneously made in any other configuration identified by a variant map which includes the same variant ID. The effect is that a given version of any part appears the same regardless of the configuration in which it appears.

To maintain data integrity of configurations of versions of parts in different variant domains as those parts are drawn down and promoted, according to the present invention variant maps are constructed in compliance with certain rules of coherence. Variant pairs and variant pair mappings are defined. A "Variant pair" is two variant IDs, from different variant domains, which appear together in the same variant map. A "Variant-pair mapping" is the set of all the variant pairs, for any two variant domains, from all variant maps in which they both appear, with duplicate variant pairs removed. In a variant-pair mapping, the variant IDs from each variant domain are assembled as a sequence of nodes from a single branch of the variant hierarchy for the variant domain. According to the preferred embodiment, a single node may be appear more than once, but there may be no gaps or missing nodes in the sequence. The variant-pair mapping is constructed so that the variant IDs from both domains represented by the variant pair appear sequentially in the same order as in their respective hierarchy branches. A node which appears more than once in a variant-pair mapping is not permitted to be paired with a node from the other variant domain represented by the variant pair which also appears more than once.

A variant map thus constructed is used by the VDMS to determine the variant hierarchy level to which any instances created belong, and to determine which instances in a promote group are promoted and to which hierarchy level they are promoted.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram illustrating the components of a computer system for use in conjunction with the present invention.

FIG. 2 is a block diagram representation of a part in an instance diagram.

FIG. 3 is a block diagram representation of variants in an instance diagram.

FIG. 4 is a block diagram representation of effective time variants in an instance diagram.

FIG. 5 is a block diagram representation of revisions in an instance diagram.

FIG. 6 is a block diagram of a derivation graph.

FIG. 7 is a diagrammatic representation of the components of an entity instance key.

FIG. 8 is a diagrammatic representation of the components of a relationship instance key.

FIG. 9 is a diagrammatic representation of search paths.

FIG. 10 is a block diagram illustrating a variant hierarchy for a variant domain.

FIG. 11 is a block diagram illustrating variant hierarchies for the Pay, Com. and Inv variant domains.

FIG. 12 is a block diagram illustrating two variant hierarchies with variant maps.

FIG. 13 is a diagrammatic representation of a variant map example.

FIG. 14 is a diagrammatic representation of another way to define variant maps.

FIG. 15 is a flow chart illustrating variant domains and variant map processing.

FIG. 16 is a block diagram illustrating the organization of variant domains and variant maps.

FIG. 17 is a block diagram illustrating an example of variant hierarchy definitions.

DETAILED DESCRIPTION OF THE INVENTION

1.0 GLOSSARY OF TERMS

To facilitate understanding the present invention and the versioning architecture in which it is implemented, the following glossary of terms is provided. It is to be noted that terms used in the specification but not included in this glossary are considered as defined according the normal usage of the computer science art, or alternatively according to normal dictionary usage.

active revision. A revision which is still allowed to undergo changes. Changes to the revision are made in place, i.e. without causing a new revision to be created. All revisions are either active or frozen.

active version. A version which is still allowed to undergo changes. Changes to the version are made in place, i.e, without causing a new version to be created. All versions are either active or frozen.

add. A request to a VDMS to create a new part. The part must not have been visible from the view of data of the requestor.

alternate search path. Any search path that is based on an alternate variant hierarchy and hence can be used only for retrievals of data in the repository, not for changes to that data.

alternate variant hierarchy. Any variant hierarchy for a variant domain other than its primary variant hierarchy. Search paths based on an alternate hierarchy can be used to retrieve repository data, but not to perform changes to it.

attribute. A value associated with an entity. Each entity type has associated one or more attributes. Some E/R systems also permit relationship types to have attributes. An attribute is analogous to a field in a record or a column in a relational table.

branch. The subset of a variant hierarchy that is obtained by starting at a leaf node and traversing the hierarchy from the leaf node to its parent, then to its parent's parent, and so forth, up to and including the root node of the hierarchy.

cardinality. A constraint that determines for a given relationship type how many connections may be made between sources and targets.

There are the following four cardinalities:

.cndot. 1 to 1 (1-1)--using the relationship type a given source may be connected to only a single target and that single target may have no other sources.

.cndot. 1 to many (1-m)--using the relationship type a given source may be connected to one or more targets where each of the targets may have no other sources.

.cndot. many to 1 (m-1)--using the relationship type one or more sources may be connected to a single target and where no other the sources may be connected to any other target.

.cndot. many to many (m-m)--using the relationship type one or more sources may be connected to one or more targets. With many to many there are no restrictions as to how parts are connected.

change. The alteration of existing data or the creation of new data. The alteration is the result of an add, update, or delete request. Other requests may be provided by the data management system that result in a change.

A change can be the result of an explicit request or it may be a triggered change that was performed automatically by the data management system as the result of another change.

commit. Actually applying to the repository a set of changes. Changes are not visible to other users until they have been committed. After requesting a set of changes the user can request to either have changes committed or to have the changes undone (called a restore).

commit scope. The commit scope is the time between the first alteration to repository data following a prior commit or restore (or the start of the repository session if there were no prior commits or restores) and the subsequent commit or restore.

context. A context is a permanently stored named collection of values for environmental variables that govern the processing of the VDMS. At any given time each session is using one particular context, with that context being called the current context. For those values that are not specified on add, update, or delete request the value in context is used, i.e, the context value serves as a "default" value.

controlling relationship. A relationship which if deleted causes, based on the definition of the relationship type, its source, target, or both to also be deleted. This is an example of a triggered change.

current revision. A revision whose revision end time is logically infinity. A current revision may be either active or frozen. All revisions that are not current must be frozen.

current version. A version whose contents represent the current time, i.e. a version that is not an historical record of the past. A current version may be either active or frozen. All versions that are not current must be frozen.

data integrity. The syntactic and semantic integrity provided by a VDMS. For an E/R VDMS this might include referential integrity, relationship semantics (cardinality, mandatory, and controlling), and constraint checking.

default variant domain. The current context contains a default variant domain for each variant default group. When a new part is added without explicit indication into which variant domain to place the part, the part is placed in the default variant domain for the variant default group that contains the part type.

delete. A request to a VDMS to remove an existing part. The part must have been visible from the view of data of the requestor.

delete propagation. A set of triggered changes (all deletes) that occurs as the result of a delete request due to referential integrity enforcement or controlling relationships.

derivation graph. A directed acyclic graph which indicates what version or versions a given version is derived from.

Any version can be derived from 0 or more versions and can have 0 or more versions derived from it. No version can be derived either directly or indirectly from itself.

dependent entity. An entity that is the target of an owning relationship.

directed acyclic graph. An arrangement of nodes and connecting branches which may fork in the direction of travel, but may never loop back on itself. There is not necessarily a common ancestor. There may be more than one path between two nodes.

See also "hierarchy" and "network." All hierarchies are also directed acyclic graphs, but not all directed acyclic graphs are hierarchies. All directed acyclic graphs are also networks, but not all networks are directed acyclic graphs.

Following is an example of a directed acyclic graph: ##STR3## drawdown. The creation of a version at the working variant level, when one end not already exist at that level, that is a copy (except for values that identify which version) of the first version that physically exists higher in the search path.

A drawdown may be done either explicitly or implicitly. A drawdown is done implicitly in logical mode when there is a request to add, update, or delete a part. In this case a drawdown is first done implicitly and then the requested change is made to the version that was just drawn down to the working variant level.

drawdown-from identifier. The last-change identifier of the version which was the source of the drawdown. The drawdown-from identifier is set in the resultant version at the time of the drawdown.

effective time versioning. An implementation of the basic versioning mechanisms in which variants represent states of a part effective at different periods in time.

Each variant has an attribute for storing the point in time at which the variant becomes effective, and an attribute for storing the point in time at which it ceases to be effective.

The effective time is also known as the variant time.

entity. A part that represents a thing, such as an enterprise model process or a source program. In an E/P versioned-data management system parts are either entities or relationships.

frozen revision. A revision which is no longer allowed to be changed. Changes to the revision will cause a new active revision to be created. All revisions are either active or frozen.

frozen version. A version which is no longer allowed to be changed. Changes to the version will cause a new active version to be created. All versions are either active or frozen.

hierarchy. An arrangement of nodes and connecting branches which never forks in the direction of travel, though two paths going in the same direction may merge together. Eventually all paths come together at a common (root) node. There is exactly one path between any two nodes.

Also known as a tree.

See also "directed acyclic graph" and "network." All hierarchies are also directed acyclic graphs, but not all directed acyclic graphs are hierarchies. All hierarchies are also networks, but not all networks are hierarchies.

Following is an example of a hierarchy: ##STR4## higher. That portion of a hierarchy (or branch) from, but not including, a given node through and including the root node.

independent change. In a versioned-data management system when two users, without knowledge of the other change, change the same part so that the two changes are applied to different versions of the part. An attempt to promote the two changes to a common version requires a reconciliation of the two changes, to prevent the second promote from unintentionally overlaying the change associated with the first promote.

instance. This is the same as "version.

instance key. The full key that identifies a particular instance (version) of a part.

inverse relationship. A relationship that connects the same source and target as another relationship but goes in the opposite direction. The source of the inverse relationship is the target of the other relationship and the target of the inverse relationship is the source of the other relationship.

last-change identifier. An identifier, which could be implemented as a timestamp, of the last change to a variant of a part. The identifier is set to a value that has not yet been used for changes to the part. The identifier is set as a result of an add, update, or delete, It is not set as a result of a variant being promoted.

lifetime ID. An identifier associated with a part whose value has not been previously used for any other current version of the part. A lifetime ID is assigned to a part when the part is created as a result of an add request. The lifetime ID remains unaltered when a part if changed as a result of an update or delete request. The lifetime ID is stored in the versions of a part.

logical delete. An indication, via a flag in a version of the part, that the part is to be considered to have been deleted. A delete request causes a logical delete, A Logical delete is required to prevent other versions of the part, such as those higher in the search path, from being accessed.

logical relationship. These are the normal relationship types. They logically connect one source part to one target part. Updating a source or target part, even if it causes the creation of a new version, does not change which logical relationships point to that source or target. A new part created via an add is born with no logical relationships pointing to it. Logical relationships have their versioning, which need not be the same as the versioning of the source or target.

lower. That portion of a hierarchy (or branch) from, but not including, a given node through and including the leaf node.

mandatory relationship. A constraint where if a part has an associated mandatory relationship then the part cannot exist without the relationship also existing. Since the relationship cannot be added until after the part is added this constraint is not enforced immediately, but is instead enforced when the data is committed.

network. An arrangement of nodes and connecting branches which may loop back on itself. There may be more than one path between nodes.

See also "directed acyclic graph" and "hierarchy." All directed acyclic graphs are also networks, but not all networks are directed acyclic graphs. All hierarchies are also networks, but not all networks are hierarchies.

Following is an example of a network: ##STR5## old tool. A tool that was written against a data management system that does not support versions of the data. These tools assume that the repository contains only a single version for each part.

ordered relationship. A relationship where the order in which the relationship parts are accessed is user determined. For a relationship that is not ordered the order is system determined, usually by a collating sequence on the relationship part key.

owning relationship. A relationship that is both mandatory and controlling on its target and where the part key of the target contains as a prefix the part key of its parent. The target must be an entity and is called a dependent entity.

overlap. When used in reference to the variant or revision time cursors, an instance is said to overlap the variant/revision time cursor if the following is true:

(instance start time less than cursor end time OR

instance start time less than or equal cursor start time) AND

instance end time greater than cursor start time

parallel versioning. Use of a version or set of versions of a part to maintain more than one active state of the same part at one time. Each active state may be operated on independently by actions such as Update and Delete.

A parallel version or set of versions may be created to represent differences in the target environment, differences from model to model, differences from release to release, differences from one period of time to another, differences from user to user, etc.

Parallel versions may be ordered or unordered with respect to each other.

Parallel versioning is represented by variants.

part. An entity or a relationship.

A part may have many versions which represent different states of the part.

part key. That which identifies a particular part among all the parts of the same part type.

physical relationship. These are special relationship types used for purposes such as maintaining derivation history. They connect one source version to one target version. They are not versioned.

primary variant hierarchy. The one variant hierarchy for a given VDMS installation whose search paths can be used to perform changes to the data in the repository.

promote. Changing the variant ID of a version of a part to the variant ID that is one element higher in the variant hierarchy. If a variant already existed at the higher level it is replaced. A previous request to change a variant that was at a level other than the working variant level caused the changes to be applied to a new variant at the working variant level. By using promote the change can be moved up the variant hierarchy until it applies to the variant against which the original change was requested.

A promote can be either a PROMOTE.sub.-- NORMAL or a PROMOTE.sub.-- FORCE. PROMOTE.sub.-- FORCE, A form of promote where the requestor has acknowledged that reconciliation has been performed as a result of a previous independent change. The promote will fail if a subsequent promoted independent change occurred.

promote group. A named group of instances related to some user task, such as a fix to a given programming error. The purpose of the promote group is to make it easier to promote all such related instances together. At any given time there is a current promote group per session. All operations that cause an instance to be altered cause the instance to be added to the current promote group if it is not already in the group.

PROMOTE.sub.-- NORMAL. The initial promote that is attempted when doing a promote. The promote will fail if a promoted independent change occurred since the time of the initial draw down.

referential integrity. Referential integrity refers to the enforcement by an E/R VDMS of the restriction that a relationship instance can only exist if both its source and target instances exist. If the source or target of a relationship is deleted then the relationship is also deleted. This is an example of a triggered change.

relationship. A part that represents a connect between two other parts, where the other parts could be an entity or another relationship. Each relationship is directional where the starting part being connected` is called the source and the terminating part being connected is called the target. In an E/R versioned-data management system, parts are either entities or relationships.

repository. This refers to either the place where a data management system stores its data or to the data itself.

restore. Undoing a set of changes. After requesting a set of changes the user can request to either nave the changes applied (commit) or have the changes undone.

resultant version. In a versioned-data management system an add, update, or delete request can cause the change to be applied either directly to the original version or cause a drawdown of the original version to a new version at the working variant with the change applied to the new version. The version that actually gets the change applied is the resultant version.

retrieval. A request to a VDMS to read the contents of an existing part. The part must be visible from the view of data of the requestor.

revision. A version which is organized serially with respect to other revisions in a set. (The set is called a variant.) Revisions are sequentially ordered in time such that there is exactly one "current" revision in any set. They represent historical states of a part. Because they represent an online historical record, no revision can ever be changed once work on it has been completed. A user request to update versioned data for a frozen revision of a part will result in the automatic creation of a new "current" revision.

revision key. That which identifies a particular revision among all the revisions of a variant.

revision time. The time range, stored as a star and end timestamp, when a revision was active in the repository. The start time is the time when the revision was created and the end time is the time the revision was superseded by a more current revision.

revision time cursor. The revision time cursor represents either a range of times between the revision cursor start time and the revision cursor end time, not including the end time itself, or a single point in time in which case the end time is set equal to the start time. Each of the two times takes the form of a timestamp. The revision time cursor restricts the view of data for any request to instances whose revision time range overlaps with the revision time cursor.

search path. An ordered list of variant IDs starting with a given variant ID and progressing higher in the variant hierarchy up to and including the root variant ID.

The domain for all data service actions is limited to those versions whose variant ID values match those of one of the elements in the search path. In addition the variants within the domain are ordered based on the ordering in the search path.

For any given node in any variant hierarchy there is a corresponding search path which starts with the variant ID value at that node.

serial versioning. Use of versions of a part which are serially ordered in time, such that each version supersedes its predecessor in a linear fashion.

Such a set of versions represents the evolution of a part over time. The latest version represents its current state.

Serial versioning is represented by revisions.

source. The part that is at the starting end of a relationship.

target. The part that is at the terminating end of a relationship.

target variant level. The variant level to which a version of a part is being promoted.

time cursors. See revision lime cursor and variant time cursor.

tool. Any program that uses the VDMS interface for accessing or altering the data managed by the VDMS.

tree. See hierarchy

triggered change. A change that was made automatically by the data management system beyond the change originally requested. For example, in an E/R data management system, the request to delete an entity will cause triggered changes that delete all the relationships that are connected to the entity.

update. A request to a VDMS to change the contents of an existing part. The part must have been visible from the view of data of the requestor.

update search path. Any search path that is based on the primary, variant hierarchy and hence can be used for updates to the data in the repository. Other search paths, those based on alternate variant hierarchies, are limited to read only operations.

UTC. Universal Coordinated Time (the acronym comes from the French translation). It is a common global time system which, like Greenwich Mean Time (GMT), is independent of local time zones. A time value in UTC is almost (within a millisecond) the same as its counterpart time value in GMT. All timestamps associated with the versioning architecture are set according to UTC.

variant. An ordered set of one or more revisions, which exists in parallel with other ordered sets of revisions of the same part.

Variants can be created to represent differences between environments, models, releases, effective times, or users. New variants are either created upon request or in logical mode are created automatically at the working variant level in response to a data sen, ice request that attempts to alter data that is not at the working variant level. This automatic creation is known as drawdown.

variant default group. A set of entity and relationship types that share the following as determined by the current context:

.cndot. Default variant domain for adds

.cndot. Default variant start time for adds

.cndot. Default variant end time for adds

Typically entity and relationship types that are used for a related purpose, such as enterprise modelling, are placed in the same variant default group.

variant domain. The set of all allowed variant IDs that share the same VARIANT.sub.-- DOMAIN attribute value. Associated with each variant domain is one primary variant hierarchy and optionally multiple alternate variant hierarchies. For any given revision time all the current versions of a part are in the same variant domain.

The purpose of multiple variant domains is to allow different parts to be versioned using different sets of variant IDs. For example parts for the payroll application could have a four level versioning scheme that had production, integration, test, and user levels, while the parts for the inventory application could have a versioning scheme that used only production and user levels.

variant hierarchy. This is a hierarchy among the variant IDs associated with a given variant domain, where a given variant ID appears once in the hierarchy. The position of the variant IDs within the hierarchy determines the content and ordering of search paths, each one starting at a node in the hierarchy.

An example of a variant hierarchy for the variant IDs: PAY.R1.PROD. PAY.R1.FIX. PAY.R2.PROD, PAY.R2.TEST, and PAY.R2.USER might be: ##STR6## Many variant hierarchies can be defined, but only those search paths based on the one hierarchy defined as the primary hierarchy can be used to perform changes to the data in the repository.

variant ID. The identification of a variant less the variant time. Different variants with the same variant ID represent the same thing with different variant times and/or different revision times.

variant key. That which identifies a particular variant among all the versions of a part. All the revisions of a variant share the same variant key.

variant level. The variant level refers to either all of the versions that share the same variant ID or to the view of data using a variant map that specifies the given variant ID.

variant map. A set of variant IDs and their associated variant hierarchy, where each variant ID is from a different variant domain (and hence also from a different variant hierarchy). A given map need not have a variant ID for all existing variant domains. Each variant ID specifies the starting variant (and also the working variant) for the search path associated with the corresponding variant domain. Updates can be performed only when the current context specifies a variant map all of whose variant IDs were from primary variant hierarchies. Promotes are done from the current variant map to the corresponding map that is its parent (see variant map path).

variant map path. The set of variant maps that can be used for updates and which share the same set of variant domains ordered based on the ordering of the variant IDs in the associated variant hierarchies. The direct parent of a given variant map (unless it is the top map) is the variant map that shares the same variant domains, and all of whose variant IDs are either the same as in the original map or its immediate parent using the associated variant hierarchy and where at least one of the variant IDs is not the same as in the original map (a map cannot be its own parent).

variant time. The time range, stored as a start and end timestamp, when a variant is considered to be effective, as for example the 1991 variant for the FICA deduction part would have an effective time from 01/01/91 through 12/31/91. The start time is the time when the variant is effective for the user installation and the end time is the time when the variant ceases to be effective.

The variant time is also known as the effective time.

variant time cursor. The variant time cursor represents either a range of times between the variant cursor start time and the variant cursor end time, not including the end time itself, or a single point in time in which case the end time is set equal to the start time. Each of the two times takes the form of a timestamp. The revision time cursor restricts the view of data for any request to instances whose revision time range overlaps with the revision time cursor.

VDMS. See versioned-data management system.

version. A representation in the repository whose data describes a particular state of a part. There can be multiple versions of the same part each describing different states of it.

The term version is synonymous with the term "instance."

version key. That which identifies a particular version of a part.

versioned-data management system. A data management system that supports one or more versions of data.

view of data. Associated with each variant map there is a view of data. The view of data is that data which is seen when that variant map is the current variant map.

visible. An instance (version) that exists using the current view of data in conjunction with the current context.

working variant. The first variant within a search path. Whenever a request is made in logical mode to change a version that is not already at the working variant level a version is automatically created at the working variant level and the change is applied to it.

2.0 VERSIONED DATA MANAGEMENT SYSTEM

FIG. 1 shows in block diagram form the typical components of a computer system for use with the present invention. Versioned data management system (VDMS) 100 will normally be loaded into system memory (RAM) from a disk storage unit, although portions of the VDMS may remain in disk storage when not in use, and execution directly from other storage media (eg. ROM, bubble. EPROM, WORM, DASD) is also feasible. The working data, identifier fields, and hierarchy information are normally stored in and read from memory 102 (RAM), but disk storage may also be used. In general, all needed data, including hierarchy information, variant maps, context, promote groups, and the versions themselves are stored in dis when accessed (retrieved or changed) by VDMS 100. However, any read/write permanent memory could be used in addition to or in substitution for disk subsystem 104. A system user 106, which may include a database meta designer, a database programmer, or a database user, interacts with VDMS 100 directly or through Tool 108, in either case using a standard user interface which may include a display, keyboard, mouse, or other input/output device. Central processing unit (CPU) 110 or other processor executes instructions from VDMS 100 and/or Tool 108 using data from memory 102 and disk subsystem 104.

3.0 OVERVIEW OF VERSIONING ARCHITECTURE

This section will provide a high-level description of a versioning architecture for use with the present invention. Later sections will describe most of the concepts in more detail, especially:

.cndot. definition services (also referred to as data definition language, or DDL).

.cndot. data services (also referred to as data manipulation language, or DML),

.cndot. relationship semantics.

It should be noted that this architecture addresses the versioning of entity instances and relationship instances, not entity type and relationship type definitions. However, the basic mechanisms apply to versioning of both instances and types.

3.1 Parts

Both entities and relationships can be versioned. For ease of reference, the term part will be used generically to refer to both entities and relationships.

A version is a representation in the repository of a particular state of a part. There can be multiple versions of the same part, each representing different states of it. Each version is stored as a single record in a file or a single row in a relational table. For some parts, such as library parts, additional data for a version may be stored outside the repository. Such additional data is outside of the versioning architecture, and hence it is the responsibility of a tool maintaining such additional data to keep that data in sync with the data in the repository.

The term instance takes on a specialized meaning. "Instance" refers to the repository data stored as a single record in a file or row in a relational table. For unversioned data, this means a single part. For versioned data, however, an instance is a single version of the part. A single entity or relationship may be represented by a whole set of instances, or versions.

An instance which represents a version of a part has a multi-part key. A key attribute is defined for each entity type. This is referred to as its part key. This is supplemented by one or more key attributes referred to as its version key Instances which represent different versions of the same part have the same part key and different version keys.

In an instance diagram, a part is represented by a box, with the part key (CLOSE in the example below) identified by a p beside the box, as shown in FIG. 2, The part type (Source), if needed for clarity, appears on the top line of the box. Additional lines may be used for the version key. Any necessary non-key attributes appear last in the box. FIG. 2 on page 141 shows a part key and two non-key attribute values.

3.2 Variants

Different versions of a part simultaneously existing in the repository are called variants.

The version key of a variant includes a variant key, which distinguishes one variant from another. New variants can be created to represent differences between environments, models, releases, statuses, effective times, etc.

Some variants have no order relative to each other. Unordered variants provide what is called parallel versioning.

Variants which, for example, represent successive releases of a program, each of which is based on the previous version, are ordered relative to each other. This is one form of serial versioning. An important characteristic of this form of serial variants is that although one variant can be considered the most current, all of the variants are active. The release 1 variant can still be retrieved and even changed after the release 2 variant has been created. (Revisions provide another sod of serial versioning. See 3.3, Revisions.)

Both parallel and serial versioning may be employed at the same time.

One part of a variant key is the variant ID, made up of the values of the variant ID attributes. (See 3.6, Versioning Attributes for a description of variant ID attributes.) In an instance diagram, a variant is shown as a box with the part key followed by the variant ID, identified by a v beside the box, as shown in FIG. 3, which illustrates variants representing successive releases R1, R2, and R3 of the Print program.

In FIG. 3, variants of the Print program were distinguished from each other based on only one factor, the release of a product. It is perfectly possible, and probably more common, to distinguish variants from each other based on combinations of such factors: environment and release and status, for example. Therefore, the variant ID is actually composed of three attributes, as described in 3.6.1. Variant and Revision Keys.

3.2.1 Variant Time Versions

One of the many factors which may distinguish variants from each other is time. Variant effective time might be thought of as "enterprise time." It is the time period during which a variant is in effect in the enterprise. This is what is typically referred to as effective time versioning.

For example, two of the variants of an entity called "Processor" may be

CPU1.91/01/01-92/01/01

CPU1.92/01/01-93/01/01

The former describes a version of a particular processor as it will be configured in 1991 and the latter describes the same processor as it will be configured in 1992.

Note that the end time of the first variant is the same as the start time of the second variant. The recorded start time is interpreted as the first time at which the variant is effective, while the recorded end time is interpreted as the first time at which the variant is not effective.

If variants are to be distinguished from each other based on time, their variant key includes a pair of time stamp attributes used to record the start and end times when the variant was effective.

As is the case for all variants, although the effective times of variants define an ordering of the variants, all variants are active. The 1991 variant can still be updated after the 1992 variant has been created.

In an instance diagram, a variant which has a variant effective time is shown as a box with the the variant time stamps identified by a t beside the box, as shown in FIG. 4. The maximum time value, or infinity, is represented as )).

The term Variant ID is used to refer to the variant key attributes exclusive of the variant start and end times, although all of these attributes constitute the variant key.

3.3 Revisions

To record successive states in the derivation of a particular variant, a series of versions of each variant is maintained. These are called revisions.

Unlike variants, not all revisions are "active" at the same time, Only the most recent revision--the current revision--of a given variant may be altered through VDMS data services (such as UPDATE and DELETE), Earlier revisions, which are no longer active, provide a history of past states of the variant.

Revisions provide a second flavor of serial versioning. An important characteristic is that only the most recent revision of a variant is active. A given revision cannot be changed by normal means after its successor has been created.

The version key of a revision includes a pair of time stamp attributes used to record the start and end times when the revision was active. This pair of time stamps constitutes the revision key.

The time represented by revision time stamps may be thought of as "repository time." It is the time period when a particular version was the most current revision of its variant in the repository. That version may be preceded by earlier revisions and followed by later revisions of the same variant.

When a revision is initially created, its revision start time is set to the current time, and its revision end time is set to infinity, or the highest time stamp that can be recorded.

A revision whose end time is set to infinity is known as a current revision. For a given variant there can be a maximum of one current revision. When it is superseded by another revision, a revision's end time is changed to the time it was superseded, and the new revision becomes current.

in an instance diagram, a revision is represented as a box with the revision time stamps identified by an r beside the box, as shown in FIG. 5. The maximum revision time value is represented as >>. The current (latest) revision of a variant always has this value as its revision-end time. (Note that the value is the same as the maximum variant time value.)

It is not necessary, and normally not desirable, to create a revision representing every change made to a variant. Whenever a new revision is created, it remains active, that is, it may be changed freely, until the next COMMIT action is performed, which renders the revision unchangeable via normal UPDATE and DELETE requests, and forces the automatic creation of a new current revision of the variant when a subsequent UPDATE or DELETE request is processed. Only a current revision may be active.

3.3.1 Example Illustrating Variants and Revisions

Below is a sequence of shorthand representations of variants with effective time versioning as well as revisions. The instances pictured are of an entity type called "Processor" which represents computers.

At time t1, Mary adds an instance defining CPU1, with 10 meg of real storage, to be online starting 7/90. ##STR7## At time t2 Mary changes the variant ID to the Production version, creating a new revision, the first revision of the Prod variant.

Note: The change is accomplished using the PROMOTE action, which will be introduced in 3.9, New Data Actions and Processes.

The Mary revision still exists but is no longer current. ##STR8## CPU1 is scheduled for an upgrade to 16 meg of real storage 7/91.At time t3 Mary updates the variant end time of the Prod variant to 7191. This creates a new Mary variant.

At time t4 Mary adds another variant to be effective starling 7/91. ##STR9## At time t5 Mary changes the variant IDs of both variants to Production. There are now two current revisions, one for each variant. ##STR10##

3.4 Using Time Cursors

Variant time allows the representation in the repository of changes, over time, in the state of real-world entities and relationships. Future time, anticipating changes in state, can be recorded.

Revision time (or "repository time") records the changes, over time, to the state of the repository data itself. It is historical: at any given moment no changes are anticipated: only present and past states are recorded.

The repository data that can be viewed at any given time is normally limited to those instances whose variant time spans overlap the variant time cursor and whose revision time spans overlap the revision time cursor. (See 5.2.2, Time Cursors). This point of view shows the data that exists at present, about real-world entities and relationships as they exist at the present time.

It is possible to view the data about real-world entities and relationships as they exist at any point in the past or future, by resetting the variant time cursor. It is also possible to view the repository data as it existed at any point in the past, by resetting the revision time cursor.

Given the example above, different variants of the CPU1 part are seen with different values of the variant time cursor. (Revision time is presumed to be t6, or the present.

Variant time: 9/90

Revision time: t6 (present) ##STR11## Variant time: 9/91 (present) Revision time: t6 (present) ##STR12##

It is possible to set the revision time cursor to a time in the past, in order to view the repository as it existed then.

Variant time: 9/90

Revision time: t4 ##STR13## Variant time: 9/91 (present) Revision time: t4 ##STR14##

3.5 Derivation Graph

For any new version, the versioned-data management system (VDMS) records which existing versions its data content was derived from. This record is called a derivation graph. Any version can be derived from 0 or more versions and can have 0 or more versions derived from it. However, no version can be derived either directly or indirectly from itself. Thus a derivation graph is a directed acyclic graph. The version(s) from which a given version is derived may be in the same variant, in a different variant of the same part, or in a different part of the same type. A version may not be derived from an instance of a part of a different type.

FIG. 6 shows a set of versions of the Print program. There are four variants of the part, with variant IDs Prod, Test, Mary, and Jerry. The Prod and Test variants each have three revisions, while the Mary and Jerry variants each have one revision. The arrows indicate how each revision was derived. Print.Prod.1-3 was the original revision, not derived from any other. Print.Prod.3-7 was used to derive both the next revision of the Prod variant and the first revision of the Test variant. Print.Test.5-9. Print.Test.5-9 was used to derive both the next revision of the Test variant and the first revisions of the Mary and Jerry variants: Print.Mary.8-14 and Print.Jerry.7-14. Revisions from three different variants were merged to derive the last revision of the Test variant: Print.Test.14->>.

Although the VDMS records a default derivation graph for the versions of a part based on the actions used to create them, it does not determine the data contents of a new version based on this information. The specification of the data for any version is entirely under user control. The derivation graph is actually a user's assertion about what the source(s) of data was for each version. In the example of FIG. 6, although the VDMS records the fact that Print.Test.14->> is derived from Print.Test.9-14, Print.Mary.8-14, and Print.Jerry.7-14, it was up to the user to determine how the data was to be merged and to assert that it was merged.

The VDMS records a derivation graph as instances of physical relationship types. (See 3.12, Logical and Physical Relationship Types.) For each entity type or logical relationship type, a derivation relationship type is automatically defined with the subject type as born its source and its target. The existence of a derivation relationship instance signifies that the source version was derived from the target version. Each instance of a part can be the source and/or target of many of these derivation relationship instances. Constraints will be provided to prevent a derivation relationship from connecting an instance to itself, either directly or indirectly.

The VDMS adds a derivation relationship instance when it automatically creates a new version based on an existing version. If an instance is derived from many others, there may be one derivation relationship instance connecting each of those instances to the new one, the VDMS does not automatically add them.

3.6 Versioning Attributes

In addition to the attributes which are included in the definition of entity types, special attributes are required to manage the versioning data. These additional attributes are not specifically defined for every entity type and logical relationship type; they are automatically included in every entity and logical relationship type definition.

3.6.1 Variant and Revision Keys

These key attributes supplement the key attribute(s) of an entity type or relationship type.

Variant Keys

Multiple variants of an entity or a relationship all have the same part key values. Therefore, a variant key is defined to distinguish them. The variant key consists of three variant ID attributes and and two variant time range attributes.

The names of the three variant ID attributes are:

.cndot. VARIANT.sub.-- DOMAIN

.cndot. VARIANT.sub.-- NAME

.cndot. VARIANT.sub.-- STATUS

The variant time range attributes are a pair of, time stamp attributes with VDMS-defined names, representing the variant effective start and end times.

Revision Keys

Multiple revisions of a variant have the same part key and variant key values. Therefore, a revision key is defined to distinguish them. It consists of a pair of time stamp attributes with VDMS-assigned names, representing the revision start and end times.

The variant and revision keys together are called the version key.

3.6.2 Versioned Entity and Relationship Keys

FIG. 7 graphically shows the component parts of an entity instance key.

FIG. 8 graphically shows the component parts of a logical relationship instance key.

In the examples to follow variant keys and variant IDs will generally be written with periods connecting their component parts.

3.6.3 VDMS-Defined Non-Key Versioning Attributes

In addition to the variant and revision key attributes, there is certain data that is required by the VDMS in order to deal with versioned data. This information is stored as non-key attributes of all instances.

Every entity and every logical relationship automatically has the following attributes:

delete marker (CHARACTER (1)) A value of 1 indicates that the version has been logically deleted. A value of 0 indicates that the version has not been logically deleted. No other values are allowed. (See 3.10. Logical Delete.)

force-required flag (CHARACTER (1)) a value of 1 indicates that the instance can only be promoted using the promote-force tool because an earlier promote attempt failed due to a time stamp mismatch. 0 indicates that the instance can be promoted by the normal means. (See 6.0. PROMOTE.)

create time stamp (DATETIME) This attribute records the time when a part was created by the ADD or COPY actions. It is not changed by any other action.

The create time stamp is used to determine whether two versions with the same part name are in fact versions of the same part. For a description of how this time stamp is used, see 8.2.3, Tolerance of Dangling Relationships.

last-change time stamp (DATETIME) This attribute is set by the VDMS when an action that changes the instance data is performed (like UPDATE or DELETE, but not COMMIT).

This attribute is used by the VDMS when doing promotes to determine whether the version at the promote-to level has changed since the instance being promoted was created. For an explanation of promotes, see 3.9, New Data Actions and Processes.

drawdown-from time stamp (DATETIME) This attribute records the last-change time stamp of the source instance when the present instance was created by an explicit or implicit drawdown action.

This attribute is also used by the VDMS when doing promotes to determine whether the version at the promote-to level has changed since the instance being promoted was created.

The following two attributes are included only in relationship definitions.

source create time stamp (DATETIME) This attribute contains the create time stamp of the relationship's source.

target create time stamp (DATETIME) This attribute contains the create time stamp of the relationship's target.

The above two attributes enable the VDMS to distinguish between relationship sources or targets having the same part key but different create the stamps: they are considered to be different parts, only one of which can be the source or target of a particular relationship instance. For a description of how these time stamps are used, see 8.2.3, Tolerance of Dangling Relationships.

None of the VDMS-defined versioning attributes can be changed or removed from a definition.

Except in literal mode (see 3.11, Three Modes of Working: Logical, Physical, Literal), VDMS-defined versioning attribute values cannot be set or changed directly by a tool or user. Their values are set by the VDMS as a result of data actions.

3.6.4 Attribute Name Conflicts

The VDMS ensures the uniqueness of attribute names within an entity type, or a relationship type.

If a new entity attribute name would conflict with one of its version attribute names, the VDMS will not allow the new attribute to be added. To minimize conflicts, all versioning attribute names are chosen to begin with the characters "DWK.sub.--."

3.6.5 New Data Types

The following new data type is provided:

Datetime

A time, stamp is provided.

The use of this data type is not restricted to versioning attributes.

3.6.6 Policies on Versioning Attributes

The versioning attributes of an entity or relationship type can be referenced from conceptual view policies defined for that type.

Integrity policies can be defined for the versioning key attributes. Derivation policies cannot be defined for any of the versioning attributes.

3.7 Extensions to Entity Type and Relationship Type Definition

Entity and relationship types must be assigned to a variant default group when they are defined. (See 5.1. Variant Default Groups.)

3.7.1 Versioning Entity Types

All instances of an entity type have the versioning attributes described above in addition to the attributes of the entity type. When the attributes of an entity type definition are queried, the versioning attributes are also returned. These may not be deleted or changed in any way via the entity type definitional dialogs and/or functions.

3.7.2 Versioning Relationship Types

A relationship type can be defined as logical or physical. (See 3.12, Logical and Physical Relationship Types.) Only logical relationships are versioned.

Since a relationship type has no attributes other than the versioning attributes, there is no query facility for relationship attributes.

3.8 New Definitional Constructs

3.8.1 Search Paths

It will normally be the case that a user wishes to see one version of each part--the most current version. However, one purpose of variants is to allow concurrent work on more than one version of a part, so that there is a current revision of many different variants. Therefore, there must be a mechanism by which the VDMS can determine which variant to return a revision of when a query is submitted, and which variant to update when an update is submitted. The search path serves as this mechanism.

Suppose that a user is working on the second release of an application that has 300 parts. One possibility is that when work began on R2, a copy of each of the 300 parts was made, identical to the R1 parts. Some of these parts will eventually be changed for R2, but many will remain forever identical to their R1 versions. But, whenever the user asks for a part at the R2 level, it can be found. The second possibility, which avoids the replication just described, is that an R2 version of a part is not created unless a change from the R1 version is necessary. Therefore, there will not necessarily be an R2 version of each part, even though R2 of the application exists. If the user has specified "R2, R1" as his search path, and there is no R2 version of the part, the VDMS automatically looks for the R1 version.

It is up to the user (most likely an administrative user) to specify to the VDMS what search paths can be used. FIG. 9 shows examples of search paths that an administrator might define.

Each search path is a linear sequence of variant IDs, each of which consists of one possible value for each of the three variant ID attributes, Domain, Name, and Status with the restriction that for a given search path all of the variant IDs must have the same Domain value.

On retrievals, only versions with variant ID's in the search path are returned. The VDMS returns a "not found" condition when no versions exist with a variant ID in the search path. Therefore, in addition to defining an ordering, the search path also functions as a filter.

The first variant ID on a search path is called the working variant. In the example above the working variants are shown in bold-face type. All updates, deletes, and adds are performed at the level of the working variant. If the variant retrieved was not the working variant, but some variant beyond it in the search path, the VDMS automatically creates a version at the level of the working variant in order to do an update or delete. All adds occur at the working variant level.

3.8.2 Variant Hierarchies

Rather than defining the search paths individually, the administrator defines a variant hierarchy, which consists of one or more search path collected into a single hierarchy. A variant hierarchy is a named construct, each of whose nodes is a variant ID.

When executing a retrieval, the VDMS uses a linear search path corresponding to a branch in such a hierarchy. A particular search path can be identified by the name of a hierarchy plus the value of one of its nodes. Note that a search path does not necessary begin with a leaf node.

In addition to the search path specification, the variant hierarchy definition also indicates between which pairs the PROMOTE process is permitted. For an explanation of this process see 3.9. New Data Actions and Processes.

3.8.3 Variant Domains

The first variant ID attribute has a special meaning; it identifies the variant domain to which versions of a part belong, All nodes in a variant hierarchy belong to the same variant domain. A variant domain may have one or more variant hierarchies, which determine the possible search paths for the variant domain.

FIG. 10 shows a variant hierarchy for the Pay variant domain which consists of the search paths shown in FIG. 9. Each node has the same value-Pay--which is its variant domain identifier.

A variant hierarchy has these properties:

.cndot. It may contain one or more search paths

.cndot. Each of its nodes has the same variant-domain ID

Different instances of the same entity or relationship type may be in different variant domains subject to the following restrictions:

.cndot. Entities: For any point in revision time, a given part may have instances in only one variant domain.

.cndot. Relationships: For any point in revision time, the restrictions depend on the semantic constraints defined for the relationship type:

--Mandatory: A relationship must be in the same variant domain as the source and/or target for which it is mandatory.

--M-1 (many-to-one): All instances having the same source key must be in the same variant domain. (But not necessarily in the same variant domain as its source or target.)

--1-M (one-to-many): All instances having the same target key must be in the same variant domain.

--1-1 (one-to-one): All instances having the same source key must be in the same variant domain, and all instances having the same target key must be in the same variant domain.

--M-M (many-to-many): There are no variant-domain restrictions for M-M relationships.

For each variant domain an administrator may define multiple variant hierarchies, but only one may be designated as the primary one: this is the only one that can be used to perform updates. This is because it is not possible to preserve data integrity with respect to the conflicting points of view reflected in different hierarchies. Other hierarchies can only be used to do retrievals. It should be expected that the instances visible using alternate hierarchies for retrievals may not conform to constraint rules, relationship cardinality, and relationship mandatory and controlling semantics.

3.8.4 Variant Maps

Tools may work with parts in only one valiant domain, or in different variant domains simultaneously. Variant maps determine which variant domains are visible at a given time.

A variant map is a named construct which defines one or more working variants or search paths from variant hierarchies for different variant domains. A given variant domain has at most one working variant or search path per map. The working variants or search paths are in effect simultaneously.

VDMS provides interfaces by which a user or tool can define a variant map and determine which variant map is in effect. VDMS preserves the current variant map setting from one session To the next.

See 4.0, Search Paths, Variant Hierarchies, and Variant Maps for more detailed information on variant hierarchies and variant maps.

3.9 New Data Actions and Processes

3.9.1 New Data Actions

A number of new data actions are included as part of the versioning architecture of the present invention.

DRAWDOWN

DRAWDOWN is used to make a copy with the working variant as its variant ID of the first instance in the search path. As indicated in 3.8. New Definitional Constructs, VDMS automatically performs this action when an UPDATE or DELETE follows a retrieval which returned an instance whose variant ID is not the working variant.

CANCEL

This action effectively deletes a variant that was created either by an ADD action or by an implicit or explicit drawdown, either by changing the revision time stamp so that it is no longer current, or by physically deleting the variant, depending on whether revisions are being kept.

RENAME

This action functions like UPDATE, except that it may be used to change an entity's key attribute, with the change automatically propagated to all associated relationships.

COPY

This action copies an entity or relationship instance, preserving all associated relationship instances of the original instance. "Associated relationship instances" means all instances which contain the part key of the instance to be copied as part of their key.

3.9.2 New Processes

These versioning processes are provided through VDMS-supplied tools rather than through template actions.

Promote

This process is used to change the variant ID of an all instances in a promote group or groups which are at the working variant level to that of the next higher variant ID on the search path. For more information, see 6.0. PROMOTE.

Version-Attribute Update

A tool is provided to change the versioning attribute values of an instance or a group of instances.

3.10 Logical Delete

As indicated in 3.8. New Definitional Constructs, it is possible on a retrieval to search for the "lowest" variant in a user-defined search path. It is also possible to search for the most recent revision of a variant. In either case, if one physically deletes the repository instance representing the most current version, the next one in the search path will be returned on the next retrieval. This would produce the undesirable result that, having performed a delete of a part, a tool could then perform a successful retrieval of the deleted part, with an older version of it being returned.

A logical delete action leaves a version in the repository, but sets a logical delete marker in it. This delete marker prevents the search from proceeding to the next most current version and causes a "not found" condition.

Logical deletion of a committed revision results in the automatic creation of a new revision, which is logically deleted.

Two factors determine whether a DELETE action results in a logical or a physical deletion.

.cndot. For a physical relationship, a delete is always physical.

.cndot. For a versioned part, if the value of the Action Mode field in the template TCA is logical, the delete is logical. If it is literal, the delete is physical. For more information on the Action Mode, see 3.11, Three Modes of Working: Logical, Physical, Literal.

3.11 Three Modes of Working: Logical, Physical, Literal

The Action Mode for any template action is governed by a field in the template control area (TCA) of templates used to perform data service actions.

There are three action modes:

Logical Retrieves a single version of each part. This mode supports all template actions.

Physical Can retrieve multiple versions of each part. This mode supports retrieval actions, but no update actions except the adding and deleting of physical relationship instances.

Literal Retrieves all versions of each part, and supports all template actions

Tools normally use logical mode. Physical mode retrieval is used primarily by maintenance utilities. Literal mode is used exclusively by VDMS tools and utilities.

Some actions function identically regardless of the action mode set in the template. These actions are:

.cndot. COMMIT

.cndot. RESTORE

.cndot. CANCEL

The other template actions function differently depending on the action mode.

3.11.1 Logical Mode

Using logical mode, VDMS data requests operate as though there were a single, unversioned instance of each part. The instance returned from a retrieval is that revision of the first variant found in the search path whose variant time span overlaps the variant time cursor, whose revision time span overlaps the revision time cursor. (Note that in logical mode the variant and revision cursors each represent a single point in time. See 5.2.2, Time Cursors for a description of the time cursors.) Successive retrievals return one version of each successive part, rather than successive versions of the same part. If the first version of a part encountered by the VDMS, using the search path and time cursors, has been logically deleted, no version of the part is returned. When a delete action is performed, the delete is logical rather than physical.

On actions which change the repository, such as ADD, UPDATE, and DELETE, the VDMS determines the variant ID values and the variant and revision times using the current variant map and time cursors.

New versions of a part may be created automatically by the VDMS in response to actions which change the repository: for example, UPDATE or DELETE actions issued in logical mode against a revision that is committed will result in the automatic creation of a new revision.

3.11.2 Physical Mode

In physical mode, VDMS data requests operate on all existing variants of a part or parts within the scope of the current search path and the variant and revision time cursors. KEYED actions may select the variant ID values to retrieve within that scope. Successive retrievals may return successive variants of the same part, rather than one version each of successive parts. Even if a version of a part has been logically deleted, it is returned; its deleted status is indicated by the value of the template's Delete Marker field.

UPDATE, ADD, DELETE, COPY, and RENAME are not supported in Physical mode for entity instances or logical relationship instances. ADD, DELETE, COPY, and RENAME are supported for physical relationship instances (See 3.12. Logical and Physical Relationship Types).

3.11.3 Literal Mode

In literal mode, VDMS data requests operate on all revisions of all variants. The search path and time cursors are ignored. KEYED actions may select the exact revision to retrieve.

For the ADD action all version attributes, including the variant and revision time stamps, and all the non-key attributes, may be supplied in the template.

For the UPDATE or RENAME actions all attributes except the create time stamp may be supplied. Thus literal mode can be used to update or delete a revision that is not active. Any add or update of a revision time span which causes conflict with those of other repository instances will fail.

DELETE actions in literal mode result in the physical deletion of instances.

3.12 Logical and Physical Relationship Types

The interface for defining a relationship type allows it to be specified as either a LOGICAL or a PHYSICAL relationship type.

3.12.1 Logical Relationship Types

All existing relationships in the Information Model are of this type.

An instance of a LOGICAL relationship type connects a source part and a target part. The relationship instance is insensitive to the version keys of the source and the target. For any particular retrieval performed in logical mode via the relationship, the current search path will determine which version of its target is retrieved.

Logical relationships are versioned an exactly the same way as entities. For a logical retrieval, the current search path will determine which version of a relationship is used to reach the target.

The versioning of a non-owning relationship is completely independent of the versioning of its source and target. The versions of an owning relationship are synchronized by the VDMS with the versions of the dependent entity.

The part key of a logical relationship is the part key of its source plus the part key of its target. Just as for entities, the version key of a logical relationship consists of:

.cndot. variant ID

.cndot. variant time range

.cndot. revision time range

All of the normal relationship semantics apply at the part level, not the instance level. This includes:

--Mandatory semantic

.cndot. Controlling Semantic

.cndot. Relationship Cardinality

as described in 8.0. Data Integrity.

A logical relationship is accessible using any action mode.

For more details on logical relationship types, see 7.1.1. Logical Relationship Types.

3.12.2 Physical Relationship Types

An instance of a PHYSICAL relationship type connects one source instance and one target instance. It records information about instances (versions), not about parts. The relationship instance is therefore sensitive to the version keys of the source and the target, A retrieval performed via the relationship returns precisely the target instance. The current context has no effect on the retrieval.

Physical relationships are not versioned.

The instance key of a physical relationship is the instance key of its source plus the instance key of its target. (If either the source or the target is another relationship, then its key has more than one component.)

All of the normal relationship semantics apply at the instance level. This includes:

.cndot. Mandatory Semantic

.cndot. Controlling Semantic

.cndot. Relationship Cardinality

as described in 8.0, Data Integrity.

A physical relationship is only accessible using physical or literal mode.

The only physical relationships are those used to maintain derivation history. An instance records that one version was derived from another version. For further information on these relationships, see 3.5, Derivation Graph.

3.13 Creation and Retrieval of Versions in Logical Mode

As was described in 3.11. Three Modes of Working: Logical, Physical, Literal, the normal mode in which tools will operate is LOGICAL mode. Therefore, this section focuses on how versions are created and retrieved in logical mode.

3.13.1 Creation of Versions

New versions can be created either explicitly via the ADD, COPY, RENAME, and DRAWDOWN actions, or automatically via the UPDATE, DELETE, PROMOTE and PROMOTE.sub.-- FORCE actions.

in order for the ADD action to succeed, the part must not exist in any other variant domain with a revision time span that would overlap that of the new instance. In addition, a logical retrieval using the part key provided in the template, plus the current search path, must not find and return an existing version of the part. This condition will be met either if there physically is no such instance, or if the first version found by the VDMS was logically deleted, and therefore not returned.

Most new versions are created automatically via the UPDATE and DELETE actions. These actions can be thought of as having both an "input instance" and an "output instance." which may be different instances. If the action is UNQUALIFIED, the input instance is the previously retrieved instance. If the action is KEYED, the input instance is the instance that would be returned by a keyed retrieval using the current search path and template part-key fields.

If the variant ID of the input instance is not the working variant, the VDMS automatically creates a new version at the working variant level. This is referred to as a drawdown. If the variant ID of the input instance is the working variant, and revisions are being kept, the VDMS automatically creates a new revision of the same variant unless the input instance was created within the same commit scope as the action being performed.

When a new version is automatically created in order to perform a DELETE, it is a logically deleted version.

3.13.2 Retrieval of Versions

In both logical and physical modes, the domain of any template includes only instances whose variant time range and revision time range (if any) overlap the values of the variant time cursor and revision time cursor, and whose variant ID is on the search path. Furthermore, in logical mode the template domain includes just one version of each part. The version of each part to be included is the first one encountered on the search path. If the first version of a pall has been logically deleted, the domain will not include any version of that part.

The domain of a subordinate template is further restricted to include only instances connected to the instance at the cursor position of the parent template via a relationship. This relationship may be versioned. The domain of the subordinate template includes only target instances for relationship instances whose variant time range and revision time range (if any) overlap the values of the variant time cursor and revision time cursor, and whose target variant ID is on the search path and is not logically deleted. Furthermore, in logical mode the template domain includes a target instance for just one version of each relationship. The version of each relationship whose target is included is the first one encountered on the search path. If the first version of a relationship has been logically deleted, the domain will not include its target. The version of the target entity is also the first one encountered on the search path. If that version has been logically deleted, it will not appear in the domain.

Once the domain has been established, FIRST returns the first instance in the domain, NEXT returns the next instance, etc.

In literal mode, the domain may include instances whose variant time range and revision time range do not overlap those of the variant time cursor and revision time cursor. (The time cursors are not used.) In both literal and physical modes, the domain may include more than one version of each part, and may include logically deleted instances.

3.14 Role of Create Time Stamp as an Identifier

In the prior art it was possible to have an entity with a given key, delete it, and then add another instance with the same key. Although the "before" and "after" instances would share the same key value, they really would be considered different entities. Their non-key attributes and their relationships would not be assumed to have anything in common. In fact, any relationships of which the original entity was the source or target, would have been deleted when the entity was deleted, and therefore would not apply to the new entity.

In a VDMS according to the present invention, however, instances representing both the original entity and the new entity with the same key can coexist. It is useful to have a means of differentiating between them. The create time stamp attribute of an entity or a relationship serves this purpose.

The value of the create time stamp is set when the first version of a part is created via an ADD or COPY action. When additional versions are created via the UPDATE, DELETE or DRAWDOWN actions, they have the same create time stamp value as the first version. Even a new instance created by a RENAME action has the same create time stamp value

Once a part has been logically deleted, if a new instance with the same part key is later added, that instance will have a different create time stamp value.

Thus, the create time stamp serves as an identifier which can both:

.cndot. differentiate between different "incarnations" of a part even though the part key is the same; and

.cndot. identify instances with different part keys as the same "incarnation" of something, which has had its part key changed.

The create time stamp of an instance cannot be changed even using literal mode.

As previously described, a logical mode retrieval returns one version of each part. It is the part key, not the create time stamp, that determines whether two instances represent the same part or a different part. Thus, if there are two instances on a search path, representing different "incarnations" of the same part, only one of them will be returned via a logical retrieval.

In addition to having its own create time stamp, a relationship also records the create time stamps of its source and target. This aids in recognizing what "incarnation" of a part a relationship was created for. This is discussed in greater detail in 7.3, Create Timestamps of Relationship Sources and Targets.

4.0 SEARCH PATHS, VARIANT HIERARCHIES, AND VARIANT MAPS

4.1 Search Paths

The sequence in which the variant IDs are searched is called the search path.

In the serial versioning implied by a variant hierarchy there is a logical progression among the different variant IDs. For example, in the "Release 2" version of an application, any parts that have not changed since Release 1 are represented by their Release 1 variants, and are not duplicated at the Release 2 level. Those that have changed for Release 2 are represented by Release 2 variants which effectively "mask" their Release 1 counterparts.

When performing a retrieval using the search path R2, R1, the VDMS in effect employs the following method: ##STR15## An instance that is returned from such a retrieval, if any, is said to be visible. Using the search path in the example above, if both an R1 instance and an R2 instance of a part existed, the R2 instance would be visible, but the R1 instance would not. If the R2 instance were logically deleted, no instance would be visible.

Typically, parallel and serial versioning are combined. Variants on the same search path are serial variants, while variants on different hierarchy branches are parallel. Each release of an application might have Production, Test, and multiple user levels specified. All changes are first tried out at a user level. When a change passes unit test, it is tried out at a functional test level along with other changes which have been unit tested. When all the changes pass functional test, they are moved to the production level. This methodology would be implemented with search paths like used, test, prod and user2, test, prod, which the VDMS would process in a manner similar to that shown above.

The user-ID variable

A special value, shown here as &USERID may be used as part of the VARIANT.sub.-- STATUS variant ID value to represent multiple values: its execution-time value is the user ID of the current VDMS session.

&USERID may be used alone as a node value, or may be concatenated before other character strings. e.g. &USERIDSANDBOX.

4.1.1 The Working Variant

The first variant ID on a search path is called the working variant.

For logical mode actions, all alterations to the repository are made to the working variant. If the variant ID of an instance to which an alteration is requested is not the working variant, a working-variant copy of the part is automatically created and the alteration applied to it. This process is called drawdown. A drawdown may skip levels in the hierarchy. For example, a part at the PRODUCTION level can be drawndown to the &USERID level, skipping a TEST level in between.

A corresponding process, called promote, is used to change the variant ID of the part in the working variant to that of the next higher node in the search path.

4.2 Variant Hierarchy

To support these logical searches and to control the use of the DRAWDOWN and PROMOTE actions, for each variant domain, the user must define one or more variant hierarchies.

Search paths having the same variant domain can be combined to form a hierarchical structure known as a variant hierarchy. Each node in a variant hierarchy implicitly defines a search path. The search path is the list of variant IDs, starting at the given node, which includes all of its parent nodes in bottom-to-top order.

Any node can appear only once in a variant hierarchy, but may appear in more than one hierarchy. Therefore, many search paths can begin with the same variant ID, one for each variant hierarchy in which the variant ID participates.

Changes to the repository are permitted only for search paths based on the primary variant hierarchy for the variant domain. These are called update search paths.

In a given VDMS installation, exactly one variant hierarchy per variant domain is defined as the primary variant hierarchy. It contains all update search paths.

Other variant hierarchies, known as alternate variant hierarchies, are optional. Search paths based on alternate variant hierarchies are limited to read-only access to the repository and are called alternate search paths.

4.2.1 Defining a Variant Hierarchy

For each variant hierarchy, the user specifies a name, and specifies whether it is the primary hierarchy for the variant domain.

Defining the Nodes in the Hierarchy

For each node in the variant hierarchy the user specifies:

.cndot. Its identity, consisting of a value for each variant ID attribute.

If &USERID is used in the name of a non-leaf node of the hierarchy, all nodes below it must also contain &USERID

.cndot. The identity of its parent node, if any. The parent node must be in the same variant domain.

The following may only be specified for the nodes in the primary variant hierarchy.

.cndot. Whether promotes are permitted to the node directly above it.

Variant Hierarchy Example

FIG. 11 illustrates three primary variant hierarchies that have the following features:

.cndot. One hierarchy is for the Payroll project variant domain named Pay, one for the Inventory project variant domain named Inv, and one named Com for parts that are common to all projects.

.cndot. Upward arrows show the paths over which promotes can occur. Note that promotes cannot be done to the Pay.R1.Pro node.

.cndot. The variant hierarchies for the Pay and Inv variant domains have &USERID values (abbreviated here to &u.) as their lowest nodes, each of which may result in multiple actual variant-ID values, while the variant hierarchy for the Com variant domain terminates in a single, specified, node identifier.

4.3 Defining Variant Maps

Typical processing requires that parts in different variant domains be accessed by the same tool. In the example in FIG. 11, while working on parts in the Payroll project it may be necessary to have the common parts--in the Com variant domain--available as well. Parts in more than one variant domain which are modified as part of the same unit of work will need to be promoted together. This requires a means to state how the nodes of the variant hierarchies for the different domains relate to each other. This is done by variant maps. A variant map links nodes in one or more different variant domains, thus indicating that the search paths starting at those nodes can be used simultaneously.

For each variant map, the user specifies:

.cndot. A name

.cndot. Whether the variant map is read-only, or is an update map, usable for actions which change repository data, including PROMOTE and CANCEL.

Only a variant map all of whose nodes were associated with primary variant hierarchies may be used for updates.

.cndot. Whether the repository data which can be retrieved using this map is protected; that is, whether data integrity is enforced for this map when data changes are requested by users using other maps.

Only variant maps that may be used for updates can be protected. Read-only maps may not be protected.

See 8.0. Data Integrity for an explanation of protected points of view.

.cndot. A list consisting of a variant hierarchy node (variant ID), and its associated variant hierarchy, for each variant domain which is to be included in the map. These IDs define the search paths. A variant domain may not appear more than once in any map.

A node which contains the &USERID variable as part of its VARIANT.sub.-- STATUS value may not be included in a protected map.

Variant Map Example

FIG. 12 illustrates two simplified variant hierarchies with a valid set of variant maps defined.

Note: For simplicity, all the examples of variant maps in this section show variant IDs without their associated variant hierarchy names. For any ID whose hierarchy name is omitted, the primary variant hierarchy name for that variant domain is assumed as a default.

Note: In all the variant-map examples, the first letter within parentheses indicates whether the mapping is for update (U) or read-only (R). The second letter indicates whether the mapping is protected (P) or unprotected (U).

Variant-pair mappings

Any pair of variant domains (FIG. 12 shows a single pair: Com-Inv) which appears in more than one update map constitutes a variant-pair mapping. A variant-pair mapping can be viewed as a kind of vertical section of a set of variant maps. The variant-pair mapping which is implied by the variant maps in FIG. 12 can be pictured graphically as follows: ##STR16##

Only certain configurations are valid in variant-pair mappings for update maps. These are valid configurations: ##STR17## These configurations are not valid: ##STR18## In order to avoid these illegal configurations, a variant-pair mapping for update maps must follow certain rules:

.cndot. To avoid the gap, for any two nodes on the same branch of a variant hierarchy, there must not be an intervening node which does not appear in the same variant-pair mapping.

.cndot. To avoid the cross, there must not exist any other update map containing a higher level from one variant hierarchy and a lower level of the other (cross)

.cndot. To avoid the zigzag, a node which appears more than once in the variant-pair mapping, may not be connected to another which also appears more than once.

Given the variant map definitions in FIG. 12, the following additional map definitions are not valid according to these rules. Map5 would result in a cross, and Map6 would result in a zigzag.

    ______________________________________
    Map5      (U,P)     Com.00.Adm   Inv.R1.Pro
    Map6      (U,P)     Com.00.Adm   Inv.R1.&u
    ______________________________________

    ______________________________________
    Map1   (U,P)    Pay.R1.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map2   (U,P)    Pay.R1.Fiz Com.00.Pro
                                         Inv.R1.Pro
    Map3   (U,P)    Pay.R1.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map4   (U,U)    Pay.R1.&u  Com.00.Adm
                                         Inv.R1.&u
    Map5   (U,P)    Pay.R2.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map6   (U,P)    Pay.R2.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map7   (U,U)    Pay.R2.&u  Com.00.Adm
                                         Inv.R1.&u
    ______________________________________

    ______________________________________
    Map1   (U,P)    Pay.R1.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map2   (U,P)    Pay.R1.Fiz Com.00.Pro
                                         Inv.R1.Pro
    Map3   (U,P)    Pay.R1.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map4   (U,U)    Pay.R1.&u  Com.00.Adm
                                         Inv.R1.&u
    Map5   (U,P)    Pay.R2.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map6   (U,P)    Pay.R2.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map7   (U,U)    Pay.R2.&u  Com.00.Adm
                                         Inv.R1.&u
    ______________________________________

    ______________________________________
    Map1   (U,P)    Pay.R1.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map2   (U,P)    Pay.R1.Fix Com.00.Pro
                                         Inv.R1.Pro
    Map3   (U,P)    Pay.R1.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map4   (U,U)    Pay.R1.&u  Com.00.Adm
                                         Inv.R1.&u
    Map5   (U,P)    Pay.R2.Pro Com.00.Pro
                                         Inv.R1.Pro
    Map6   (U,P)    Pay.R2.Tst Com.00.Tst
                                         Inv.R1.Tst
    Map7   (U,U)    Pay.R2.&u  Com.00.Adm
                                         Inv.R1.&u
    ______________________________________

    ______________________________________
            Map1         Map1
            Map2         Map5
            Map3         Map6
            Map4         Map7
    ______________________________________