by Mark E. Easterfield, Richard G. Newell & David G. Theriault
Abstract
The majority of today's GIS systems adopt an approach to multi-user working which is based upon the standard model underpinning conventional commercial RDBMS systems. This model is appropriate in applications where only the most recent state of the database is of interest, but it does not work well over long transactions, and is inappropriate for manipulating multiple versions. Many GIS activities involve transactions lasting days or weeks, and others could benefit from the ability to develop, compare, and retain or merge different versions of data. This paper proposes an alternative approach to multi-user working, based around deferred detection of conflict. The paper reviews a number of benefits which the approach brings, such as multi-user data capture, developing and assessing alternative designs, and the ability to include external mapbase updates over time. The paper concludes by considering the features required of the underlying system in order to support the approach.
Introduction
The majority of today's GIS systems adopt an approach to multi-user working based on the one designed for conventional data processing requirements. This approach is based on the principal that it is only permissible to make changes to the most up to date version of the data, a rule which is satisfied by a combination of locking and enforced rollback.
This rule is entirely appropriate in situations where changes tend to be small, where the data represents a single state, and where conflict must be detected at the earliest opportunity. A good example is a ticket reservation system, where it is vital to know with absolute certainty whether a seat has been sold, or is still available.
The approach is much less appropriate to most GIS applications, where changes may be substantial, and be self consistent only over a considerable period of time, and where it may be legitimate to construct alternative versions of data before deciding upon one or another to represent the real world. However, most of the GIS products available currently are locked into the conventional model, as they tend to be heavily dependant upon standard commercial DBMS offerings, which are designed for the DP environment.
The particular deficiency of conventional DBMS systems concerned with their inability to handle long transactions has been recognised, particularly where graphical data is concerned. However, attribute data is still generally managed in the traditional manner, and there are problems in maintaining consistency between the two forms of data. Currently, there is little support for the management of alternative versions of data.
This paper examines the benefits of a data management system which supports alternative versions. It illustrates how such a system also provides a much more appropriate multi-user model in the GIS environment, and provides additional spin-off benefits in a distributed environment.
The paper goes on to consider the requirements of such a system, independent of its implementation, and concludes with one possible implementation strategy.
[ Figure 1 not available ]
The Benefits Of Enabling Alternative Versions
Traditional database technology has encouraged a view of the world, as represented in the database, in which there is a single, canonical state. It is possible to modify the database, from one state to the next, but it is not permissible to have multiple canonical states simultaneously.
At first sight this seems most reasonable there is only one true state of the world (in real life). Furthermore, it precludes incompatible changes from being made in a very simple way there need never be any doubt about the logical integrity of the data. The approach is good at representing a static past, or a present which evolves in small, simple, discrete steps.
However, many applications are actually used to model the future, or to model a loose form of the present in which changes in the real world are not represented as a continuous series of small transitions but rather as a few discreet modifications, each of which is substantial.
When modelling the future, the ability to represent alternatives is of great value. For example, when planning a new development, a number of different possibilities can be reviewed and costed before one is chosen. A system which permits alternative models of the (future) world to co-exist independently of one another must also inherently permit these alternative views to remain separate from the accepted view of the present, so that if there is a canonical view of the world it is not affected by "what if"s.
This requirement to keep a canonical data set apart from changes to it also occurs during customisation. In this case, the alternatives do not necessarily represent real futures at all, but simply experiments to check that the customisation work does what is intended. Traditionally, such verification is performed on a small subset of the data, which has been copied out of the master database. However, this approach tends to conceal problems of scale until the customisation is released, when it is too late to rectify them. Using alternatives, customisations can be tested on the real database, highlighting problems immediately, but without interfering with users in any way.
When modelling the present, there is benefit in being able to defer making individual changes visible until a complete set of changes is in a logically consistent state. In the case of adding a newly acquired data set, or of making substantial changes to the use of a piece of land, say, the data may remain inconsistent for some time. The type and duration of change is more akin to that in a CADCAM environment, rather than the small transitional changes encountered in DP. In an environment which provides alternatives, the canonical state represents one possibility, and the new state resulting from the modifications represents another. The new state can remain hidden from general view for as long as is required, and only released when the whole change is considered complete.
Looking further afield, there are other advantages in an environment which supports alternatives. If a solution has been found to the problem of merging independently developed versions (which is fundamental to the entire alternative strategy), then it is also possible to contemplate merging changes which have occurred entirely outside the particular database.
One example is that of the map base vendor, who issues changes to the map base from time to time to a set of customers. Each customer may have wished to modify his existing base over time, to keep it in step with the real world. At the time the new base is issued, some of the changes will have ceased to be relevant, because they have now been incorporated by the vendor, but others, for reasons of timing or of the nature of the data, will still be required. In such a situation, it is necessary to be able to identify the differences from the original base, and to re- apply those modifications which are still relevant to the new base.
This is illustrated in Figure 1, where the act of bringing the map base up to date would actually prove undesirable if allowed to proceed in an uncontrolled manner. The alternative management approach permits the user's foreground to be reconciled with the new map base in a controlled fashion, so that day to day users of the data never see a dangerous and misleading combination.
A second example where the comparison and merging of disjoint versions is of value is in a distributed database environment. To be truly distributed, parts of the database must be able to function whilst they are cut off from other parts. This necessarily demands that changes must be able to be made which cannot be wholly checked for logical consistency until all the database is visible again. An approach which accepts the mutual coexistence of different versions, with consistency validation deferred until late in the day, makes this feasible.
An approach which allows alternative (and therefore necessarily conflicting) versions of the state of the database to exist is mutually exclusive to an approach which guarantees a single, fully consistent state. In many DP applications, the latter approach is absolutely necessary. We contend, however, that in GIS applications, trans- actions are naturally long, concurrent alternative scenarios are desirable, and that in practice mutually conflicting changes are either rare or wholly unavoidable, and that therefore a model based upon alternatives is more appropriate.
The last of the three points is the most crucial to this argument. If there is a large amount of avoidable conflict which has to be resolved late in the day, then the amount of work required to create a consistent state outweighs the benefits which have been proposed. We believe, however, that day to day conflict will generally be rare in a reasonably well managed environment, and that the other problem of substantial unavoidable conflict is one which is outside the scope of conventional database management techniques.
The Relationship Between Versions And The Management Of Time
The management of versions and the managment of time are often referred to synonymously. However, the two are not the same, and should not be confused (Langran 1988).
Version management, with which this paper is principally concerned, offers control over database time, which runs strictly forwards. As will be seen later, the management of versions may be conveniently implemented by successive overlaying of changes.
Management of real world time is different, because it is possible to modify the past by adding new data (and therefore time in one sense is no longer strictly forwards). For example, the data in a map base may reflect the external world at the current time, say 1990; later on, data may be added which describes what the world was like at an earlier date, for example in 1953. Database time and real world time are thus running in opposite directions.
It is possible to implement mechanisms which manage time in a database, but the methods described here are not generally appropriate. As with alternative version management, an efficient solution demands functions built into the database manager itself which are outside the scope of this paper.
The Requirements Of A System Providing Alternative Versions
Any system which permits alternative states of data to exist concurrently must minimally provide a certain set of features. These are considered in this section, and comprise:
- The ability for different users to work on seemingly wholly independent views of the database, so that other users remain unaware of the changes they are making
- The ability to commit changes to disk without the changes becoming visible to other users
- The ability to make changes potentially visible to other users when they have been authorised as a consistent set
- The ability of a user to defer, until it is convenient, the making visible of changes effected by someone else
- The ability to determine precisely what has changed between two versions
- The ability to validate the consistency of a set of changes to the database.
The first point is an underlying pre-requisite for alternative version management. Conventional GIS solutions to the problem of data access which are based on check-out and check-in suffer from restricting access through excessive locking of data, perform poorly during the check-in/check-out operations themselves, and are expensive in their use of disk. A system providing effective alternative version management demands solutions more directly in tune with that specific approach.
The separation of the action of committing changes to disk, to that of making changes visible to others, is actually more related to long transactions than to alternative management per se. However, since an alternative itself may evolve through a number of states, and may exist for an indefinite period of time, there is the de facto requirement to be able to save individual states of an alternative while it is still hidden from general view.
The traditional DP approach to transaction management combines the act of committing to disk, and that of making changes visible to others. It also incorporates rollback using the same technique, for good measure. These three functions, although related, do not have to be combined, and can actually be considered separately. In an environment which supports a number of individually identifiable alternatives, any one can be committed to disk and rolled back without affecting the others. The act of making the changes visible to a wider audience then becomes a separate administrative function, rather akin to the formal approval and release of drawings or documents.
In an environment where conflicting alternatives may co-exist, the merging of two such alternatives requires a high degree of formality. Three distinct phases are required. The first, making a set of changes potentially visible, has already been described. However, before a user working on another alternative can be allowed to see those changes, he too must take positive action, to prevent the view of the database he is using suddenly going from a self consistent state to an inconsistent one. Just as the user has been buffered from changes going on elsewhere up until now, so he should continue to be protected until there is a good chance that the uptake of the new view will not cause conflict. This process of accepting a set of changes which have been issued from another alternative is called refreshing. The refresh process itself consists of two parts, the first validating that the new combined state is logically consistent, and the second actually making the combined state the one to be used.
When two alternatives are developed independently, the only data which can truly be considered common between the two is that which existed in a common ancestor. The difference between a pair of alternatives is a function of the modifications made to that ancestor in each case. And as these modifications are made in isolation of one another, there is no physical relationship between them, so they may only be compared by considering what logical changes have been made. In particular, it is not possible to simply physically merge two versions together, it is necessary to re-apply the logical changes that have been made.
Thus the ability to refresh demands the ability to determine what changes have been applied to the database during the life of an alternative version.
Before a refresh can be completed, the new view of the database which would be created by incorporating the changes of one alternative into the changes of another must be validated to determine whether any integrity constraints have been broken. In databases based on the relational model, two sorts of conflict can arise. There is a conflict if the same record (identified by primary key value) has been modified in a different way in the two alternatives; and there may be a conflict arising from an application constraint. The former is easy to detect, the latter more difficult, requiring application specific code. However, things are not as bad as they may seem, since if the application possesses the ability to verify the integrity of data generally (for example, as it is entered) then precisely the same verification functions can be used on the set of changed records during the refresh process.
The detection of either form of conflict can be built upon the ability to retrieve the set of records which have changed between the version being refreshed and the common ancestral version. The ancillary problems of how to report or display conflict, and of providing tools to rectify the situation, fall into the application and user interface domain, and are not considered here.
The foregoing has described a set of requirements for a platform which supports the management of alternatives. We next describe one possible mechanism by which these requirements can be fulfilled.
An Implementation Strategy
Many of the demands made of a system which manages alternative versions of data concern the ability to identify the differences between them. Thus we are considering different states of the data, and, most importantly, what has happened to get from one state to the next.
Using the relational model, the changes between one state and another can be described by the set of changed records, identified by primary key value, and the type of change (insertion, deletion or modification). Non relational models present more problems, because there is no simple way of comparing entities between two independently generated sets of data. This paper only considers the relational case.
The implementation described here is based on a tabular datastore constructed from conventional B*-Trees, with the fundamental versioning mechanism built into the underlying data structure itself. This has the properties of low space overhead and almost zero performance overhead during conventional access. This level of the implementation permits multiple versions of the data to co-exist, with blocks which are common to two or more versions being shared between them.
Note that the approach does not demand that all blocks reside in the same file. In particular, benefit can be gained in the long term by storing a version on a mass storage medium such as CD ROM and maintaining the changes on conventional disk.
In order to determine the differences between a version and one of its ancestors, it is only necessary to examine those blocks in that version which differ from the ancestor's version, rather than all the blocks in the database.
Different versions of the same tree are simply accessed via their different rootblocks, and the action of committing a new version to disk simply involves storing the new root block number in an appropriate place. The old version continues to remain accessible while its root block number is still known.
[ Figure 2 not available ]
Alternative versions form a hierarchy, as illustrated in Figure 3. At the top (the root) is the master database, which would probably correspond to what is considered the canonical state. Nodes which are derived from this could be used, for example, to differentiate between themes (e.g. pipework, electrical, cadastral, etc.), between different spatial areas, or between any other aspects where the probability of conflict is low. At the leaves of the tree, each "user" has an alternative in which to work without conflicting with others. In many cases, the levels of the tree will have close correspondence with levels of approval.
[ Figure 3 not available ]
Changes are posted (i.e. made more widely visible) one level at a time. Provided that the up to date version at the higher level is the one from which the changed version was derived, only application validation in the form of "approval" is required the version itself will be self consistent.
If the version at the higher level has since been updated, the version about to post must first refresh, so that it is the up to date state which is being posted into. If this formality were not undertaken, the intervening changes to that higher level version would be lost.
The posting process can generally be implemented using purely physical means; the refresh process cannot. The refresh process is effected by re-applying into the new state the changes which had been made since the last refresh, by determining which records had changed, and the form of change, and repeating the process.
Of all the processes, refreshing is the most complex and potentially time consuming. However, the time taken is proportional to the degree of change, not the overall size of the database.
The cycle of modification, posting and refresh is illustrated in Figure 4.
[ Figure 4 not available ]
Accessing Conventional RDBMs
A GIS may be called upon to access and maintain data which is handled using a conventional DBMS system. We know of no system around today that supports the sort of functionality described in this paper, so if the functionality is to be provided to the end-user it must be achieved by means of a version managed front end to the non version managed underlying system. This solution is bound not to be wholly satisfactory, and includes such problems as:
- Finding an optimal way of populating the version managed datastore tables which performs well and doesn't require too much disk
- Coping with situations where the conventional database is updated by the external access (i.e. outside the version managed environment)
- Retaining version information once data is posted back to the conventional database
The first of these problems is almost certainly soluble by techniques such as remembering frequently used queries and dynamic downloading of data. The latter two problems are much more difficult to resolve. However, we believe that the benefits of a system which supports multiple versions and alternatives in GIS applications outweighs these potential difficulties.
Conclusions
In this paper we have suggested that the conventional DP transaction approach to multi-user working is inappropriate for GIS applications. There are a number of essential differences between the conventional approach and the one described here. These include the ability to maintain, merge and administer a hierarchy of alternative versions in a controlled manner and to safely allow multi-user access without locking.
We contend that a system which uses deferred detection of conflict to permit alternative versions of data to be worked on concurrently provides many benefits. These include the ability to experiment and cost alternative scenarios, to develop and test customisations on a realistic size of dataset, and to resolve many of the current problems relating to long transactions and distributed working.
We have identified a number of requisites of a system which is to successfully support alternative working, which include the ability to separate the process of making one user's changes visible to another into discreet stages, and the ability to determine what has changed between one version and another.
Finally, we have demonstrated the feasibility of the approach by proposing one possible implementation technique which fulfils these requirements efficiently.
References
Armstrong Marc P. (1988). Temporality in Spatial Databases, Proceedings GIS/LIS'88, San Antonio 1988, pp 880-889.
Barrett, Myles 1989. Object-Oriented Language Extensions for CAD/CAM: Journal of Object-Oriented Programming, Vol. 2, No. 2, July/Aug 1989.
Chance, A., Newell, R. G., and Theriault, D. G. 1990. An Object Oriented GIS Issues and Solutions. Conference Proceedings of EGIS, Amsterdam, April 1990.
Chou H., and Kim, W., 1986. A Unifying Framework for Version Control in a CAD Environment. Proceedings of VLDB86.
Ecklund, D. J., Ecklund, E. F., Eifrig, R. O., and Tonge, F. M. 1987. DVSS: A Distributed Version Storage Server for CAD Applications. Proceedings of VLDB87. Katz, R. H. and Chang, E. 1987. Managing Change in a Computer-Aided Design Database. Proceedings of VLDB87.
Kent, William 1989. An Overview of the Versioning Problem. ACM SIGMOD 1989 Conference in Portland, Oregon. SIGMOD record Vol. 18 No 2, June 1989.
Langran Gail and Chrisman Nicholas R. 1988. A Framework for Temporal Geographic Information. CARTOGRAPHICA Vol. 25, No. 3, 1988 pp1-14.
Posts
No comments:
Post a Comment