Database support for evolving data in product design.
We argue that database support for design processes is still inadequate, despite the many transaction models that have been put forth to fill this deficiency. In our opinion, substantial improvement is not to be gained by introducing yet another transaction model, but by questioning the basic paradigm of transaction processing itself. Instead of the usual view of transactions as destructive operations replacing an outdated database state with a more current one, we propose to view design transactions as non-destructive operations importing additional knowledge about an essentially unchanging final design solution. This leads to a model of designing with constraints, and a natural way of concurrent design. We give a formal presentation of the model and then discuss implementation techniques for centralized and distributed constraint management.
Introduction
Product design, like most other business processes today,
requires database support for all but the most simple under-
takings. Yet, design processes differ from ordinary business
processes in that they are not easily decomposable
into a series of independent steps that would lend themselves
to the ACID paradigm of classical database trans-action
processing. Instead, the various subtasks in a design
task tend to be highly interrelated, and the design process is
best viewed as a set of cooperative activities pursuing these
subtasks simultaneously.
Consequently, research in database support for design
processes has mostly focused on developing alternatives to
the strict isolation property of classical database transac-
tions, and a variety of mechanisms to define and control
cooperative transactions has been proposed.
While these proposals have - sometimes considerably
- departed from the notion of serializability as the classic
correctness criterion, the basic paradigm of transaction
Funded by the German Research Council (DFG) under project number
SFB346.
processing has remained the same: transactions effect state
transitions between consistent database states, which are
defined as being complete and unambiguous descriptions
of the current state of the miniworld under consideration.
From this point of view, the amount of information in
a database is essentially constant: each consistent database
state provides a complete description of exactly one state of
the miniworld. Transactions switch between these states as
dictated by the evolution of the miniworld; they do not, in
general, increase the amount of information available about
the same state. Thus, transactions are essentially non-
monotonous: information about the old state is destroyed
and replaced by information about a new state. From non-monotonicity
follows non-commutativity, and therefore the
importance of serializability.
In a design process, however, information is predominantly
added to the information already available. Ideally,
design means a continuous refinement of specifications until
a unique artifact is singled out. In other words, the
"state" of the world - the artifact that is the eventual result
of design - never changes; instead, the amount of knowledge
available about that state increases monotonically. Of
course, real design processes are less straightforward; proposed
designs may prove to be infeasible, in which case
some specifications must be retracted. Nevertheless, the
fundamental operation in design is narrowing the solution
space, which is a monotonous, and hence commutative, operation

We believe, therefore, that a database system useful for
design processes should support the notion of specification
(as a constraint on admissible artifacts) and refinement and
release of specifications as primitives in its data model, and
that the leeway offered by the commutativity of refinement
should be exploited in its transaction model.
As a first step in that direction, we propose a constraint-based
data model, thus adopting a perspective originally
introduced by constraint logic programming and then taken
up by constraint database systems. From this perspective, a
database does not provide an explicit characterization of a
single state of the world by assigning precise values to the
state variables. Instead, a database contains a set of constraints
over these variables, which delineate the admissible
values and thereby the possible states of the world. Put
in less abstract terms, a design database holds the requirements
and design decisions gathered so far and thereby
constrains the set of possible design solutions. As design
proceeds, further constraints are added, until either a contradiction
is reached and backtracking becomes necessary,
or the specification progresses to the point that all information
needed for eventual production of the artifact is available
with sufficient precision.
The fundamental primitives in this data model are re-
finement, querying and release of constraints, and we demonstrate
how these primitives play together in collaborative
design. Given that the database always denotes an approximation
to the design solution, the notion of consistency
becomes rather simple: constraints must not be contradictory
(at least not on a level the system can detect), and constraints
introduced by one party must not be released by
another party without proper authorization.
In the case of a single, centralized database, the data
model and its associated consistency guarantees can be
implemented in a straightforward way using techniques
known from constraint databases. The situation becomes
more difficult once data replication is taken into account,
e.g., a sales representative loading a set of product specifications
onto her laptop, making some changes offline at
a customer meeting and then reintegrating the data into
the main database. To maintain consistency in this case,
changes to replicated data must, to a certain extent, be arranged
in advance. We present a locking protocol designed
to announce anticipated changes to replicated data and to
prevent, in a pessimistic fashion, conflicts during reintegra-
tion. However, even if the protocol cannot be observed and
unanticipated changes need to be made, conflicting specifications
will be detected at reintegration time and can then
be resolved manually.
To summarize, the contributions of this paper are as fol-
lows: we demonstrate that the notion of data as constraints
lends itself in a natural way to concurrent design, and we
present the protocols necessary to coordinate concurrent
access and maintain consistency in both in a centralized
and a distributed constraint store.
2. Related work
The view of design as refinement of specifications is fairly
common in design theory (see, e.g., [2]). In the most general
setting, specifications are given by arbitrary concepts
(where a concept denotes a family of related artifacts), and
the result of design is an artifact defined by the intersection
of a sufficient number of such concepts [13]. However,
there is no hope of treating specifications this general algo-
rithmically. We limit ourselves to specifications that constrain
the value of some attribute to a certain range. Such
specifications do cover the most common cases in practice,
and they admit efficient satisfiability tests.
As pointed out in the introduction, the constraint paradigm
has been put to fruitful use in constraint database
systems [7, 10, 8]. The primary motivation for this line
of research was the desire to generalize ordinary relations
(i.e., finite collections of tuples) to infinite relations while
maintaining a finite description. Consequently, constraint
database systems have become very popular for geographic
and temporal applications, where regions or intervals containing
an infinite number of points need to be manipulated.
The transactions conducted by such applications, however,
are rather conventional and in particular non-monotonous,
so that constraint databases have not yet been able to realize
the potential for increased parallelism inherent in the
constraint framework.
Quite to the contrary, parallelism was the main focus in
Saraswat's work on parallel constraint programming [11].
There, the notion of a shared constraint store is proposed
as an elegant means of communication and synchronization
between cooperating agents. Our data model is a rather
simple application of the general framework laid out in this
thesis. Saraswat, coming from a programming language
background, was mostly concerned with a centralized constraint
store; although he addresses distributed constraint
systems, he does not discuss any mechanisms to maintain
consistency in such a setting. This gap is filled by the protocol
presented in Section 6.
Fuzzy sets [14] may be viewed as generalized constraints
that allow varying degrees of satisfaction. Fuzzy
database systems [1, 3] have been proposed to capture
the uncertainty of specifications inherent in early design
stages [12, 15]. Thus, fuzzy database systems share our
view of design as refinement, or reduction of uncertainty.
However, most research in applying fuzzy technology to
design processes has focused on the modeling aspects and
semantics of fuzzy sets, whereas we are mainly concerned
with coordinating parallel access to design information.
Yet, the data model and protocols presented below apply
equally well to "crisp" and "fuzzy" constraints, provided
that efficient consistency checking algorithms for the class
of constraints under consideration are available (e.g., [6]).
Constraint and fuzzy database systems may be regarded
as combinations of a non-standard data model and a standard
transaction model. Conversely, there have also been
many attempts to graft an advanced transaction model
onto a conventional object-oriented or relational database
system, seeking to provide better support for the long-
running, cooperative transactions typical for design pro-
cesses. Space limitations forbid a detailed discussion of
this rather large body of work (see [5] for a survey). In
general, these transaction models trade the strong consistency
guarantees offered by serializable transaction processing
against more flexible control over transaction isolation
and notions of consistency. However, such flexibility
comes at the price of more complex transaction management
schemes and, worse perhaps, depending on each user
to provide information about the desired semantics along
with the transactions themselves. That, in our view, is a
bad tradeoff; the consistency guarantees and semantics of a
database system should be as simple as possible.
A much less drastic modification of the classic ACID
paradigm is the notion of ffl-serializability, introduced in [9]
as a means of trading precision for concurrency. ffl-seriali-
zability is applicable to data that possess a - numerically
quantifiable - degree of uncertainty, and it extends ordinary
serializability by permitting transaction histories whose results
differ (according to a suitable metric) by no more than
a quantity ffl from a serializable history. Unfortunately, ffl-
serializability does not handle write transactions very well:
in the absence of any knowledge about the internal workings
of a write transaction, one must assume that small variations
in the input can lead to arbitrarily large variations in
the output, and hence accept the possibility of unbounded
divergence of the database state from the result of a serial
execution. [4] addresses this problem by suggesting that
transactions that "went too far astray" be periodically un-
done, but in a design setting, with transactions easily representing
a day's work, that may prove very costly.
3. A formal model of constraint-based design
We view design as the manipulation of specifications,
where each specification poses a restriction on the admissible
design solutions. Specifications imposed by external
agents (i.e, design requirements) and specifications resulting
from decisions internal to the design process are treated
alike. We model the design space as a finite collection x 1 ,
of design parameters of types t 1 , t 2 , . , t n ,
such that every possible design outcome is uniquely characterized
by an assignment of values to x 1 , x 2 , . , xn .
The types t 1 , t 2 , . , t n are arbitrary; thus it is entirely conceivable
that a design parameter describes, say, a complex
geometry.
A specification in general is a syntactical characterization
of a subset of t 1 \Theta t 2 \Theta \Delta \Delta \Delta \Theta t n . As pointed out in
Section 2, this notion is too broad to be algorithmically
tractable, so we limit ourselves to specifications that restrict
the value of a single design parameter x i to a range S,
where S has a syntactical characterization in some language
L. Such one-dimensional specifications will henceforth
be called conditions. The exact language L used to
express ranges is left unspecified; for example, S might
be defined by explicit enumeration, numerical intervals,
logical formulas, etc. We do make certain assumptions
about L,
1. If ranges S 1 , S 2 , . , Sm are expressible in L, then
is expressible in L as well,
and there exists a (reasonably efficient) procedure for
computing the corresponding expression.
2. There exists a (reasonably efficient) procedure for
deciding whether the intersection of a collection S 1 ,
ranges expressible in L is empty.
3. The ranges expressible in L are "convex" in the following
sense: if S, S 1 , S 2 , . , Sm are expressible
in L and " m
(This is a technical and not
particularly essential condition having to do with the
constrain operator introduced below.)
These assumptions are obviously true for ranges defined
by numerical intervals, but also for more powerful logical
frameworks (cf. [8] for some examples).
Associated with each condition is a principal, i.e., an
abstract representation of the agent that imposed the condi-
tion. This could be an individual designer, a design team, a
manager, a customer or any other entity authorized to participate
in the design process. The combination of condition
and principal is called constraint.
A design state, or design database, is given by a collection
of constraints, which together describe the values
considered admissible for x 1 , x 2 , . , xn in that particular
state. A design state is called consistent if there is at least
one assignment of values to x 1 , x 2 , . , xn satisfying all
constraints.
This notion of consistency is admittedly naive, because
it does not take interactions between design parameters
due to physical laws or technological limitations into ac-
count. For example, in microprocessor design the conditions
"clock rate - 1000MHz" and "power dissipation -
1W" are formally consistent (because they refer to different
design parameters), but currently not simultaneously
achievable. If desired, such dependencies between design
parameters could be introduced into the model as multi-dimensional
conditions, at the expense of increased overhead
for consistency checking. We believe, however, that
even the simple-minded consistency checks defined here
will prove beneficial in practice.
Design proceeds by means of three basic operations.
Each operation is carried out atomically.
Adds a new constraint with condition x 2
S and the invoking agent as principal to the design
state. This operation succeeds only if the new state
is consistent. If it fails, the set of constraints conflicting
with x 2 S is returned (this set is well defined
because of the convexity property assumed above).
Removes the specified constraint from the
design state, if it exists. (Note that this does not
affect other constraints on x.) This operation succeeds
only if the invoking agent is authorized to remove
constraints introduced by principal p. The specific
scheme whereby such authorization is obtained
is left open.
peek(x) Returns a condition describing the set of values
admissible for x in the current state (i.e., the intersection
of all current constraints on x).
Let us briefly comment on these operations and the invariants
they imply.
constrain is a monotone operation that is used to establish
new design requirements, new design decisions or -
this case will be discussed in the next section - a stake in
existing decisions. release is the inverse operation, used
to retract requirements or decisions that did not come to
fruition. peek serves to query the current state, typically at
the beginning of a design task. From the definition of these
operations, it is clear that the following two properties hold:
Constraint Consistency (CC): The design state is always
consistent. In particular, the result of a peek operation
never denotes the empty set.
Constraint Durability (CD): Once a constraint has been
successfully established, that constraint will be satisfied
by any design solution unless explicitly released
by a properly authorized agent (presumably with notification
of the constraint's principal).
It is worth pointing out that the notion of durability described
here is quite different from the one offered by ACID
transactions: the latter refers to protection from system or
media failures, but not the effects of other transactions. In
values written by ACID transactions are safe from
other transactions only while they are not yet committed;
after being committed, they may be overwritten at any time.
This is contrary to the semantics of committed design de-
cisions, which are supposed to be stable unless explicitly
retracted.
4. Concurrent design with constraints
We will now illustrate how the constraint manipulation
primitives play together in concurrent design.
The design process will usually begin by determining
the major design requirements and entering corresponding
constraints into the design database. As soon as a sufficient
set of requirements has been established to allow a meaningful
subdivision of the design task, design subtasks may
be formulated and assigned. Meanwhile, the acquisition
of requirements continues, resulting in further constraints
being imposed.
A designer charged with a certain design task will initially
use the peek operation to obtain the current constraints
on the relevant design parameters. Three outcomes
are possible:
1. The constraints are such that no solution is possible.
In this case, the design process has reached a dead
end, and some constraints need to be released.
2. The problem is underspecified to the extent that nothing
useful can be done. In this case, the design task
must be postponed until more information is forthcoming

3. The constraints admit one or more solutions. In this
case, a solution is determined and constraints describing
the solution are added to the database, together
with constraints that describe the assumptions
on which the solution was based. In the simplest
case, these additional constraints are simply copies
of the constraints obtained from the initial peek oper-
ations, and thus redundant. More frequently, though,
a design solution requires stronger assumptions than
just the design requirements, so that the additional
constraints describing the design assumptions do actually
narrow the solution space.
In this way, many design tasks can proceed in parallel,
while - by virtue of constraint durability - each designer
can rest assured that the assumptions and results of her design
remain valid throughout the entire process, unless explicitly
retracted.
Of course, this also means that an attempt to establish
a constraint may fail, because it conflicts with the assumptions
or results of a another design activity. No attempt is
made to resolve a conflict automatically, because resolution
typically requires domain-specific expertise. The only
recourse in a conflict is to contact the principal of the offending
constraint (which is returned by an unsuccessful
constrain) and to negotiate a solution.
Note that the consistency and durability guarantees offered
by the constraint store do not require any locking protocols
(besides executing each primitive operation atomi-
cally), but follow simply from the definition and the monotonicity
of constrain.
5. Implementing a centralized constraint store
While the current prototype of our system is a stand-alone
implementation using a main-memory database system, a
layered implementation on top of a conventional relational
database system can be envisioned in a rather straightforward
way.
First, the design parameters describing the design space
need to be identified. It is hardly feasible to submit every
single dimension occurring in an engineering drawing or
every line of code in a program to the constraint paradigm.
Therefore, one would try to identify a set of parameters representing
information that truly needs to be shared among
concurrent design activities, and then use the transaction
management facilities of the underlying database system
to couple other, non-shared parameters to their "govern-
ing" shared parameters. For example, if two design groups
working on a mechanical assembly needed to exchange
only bounding box information for their respective com-
ponents, then just the coordinates of these bounding boxes
would be considered design parameters, and access to all
other dimensions would be wrapped in ACID transactions
that ensure that the bounding box data remain consistent
with the true geometry data.
Second, a domain and a condition language need to
be chosen for every design parameter. In mechanical de-
sign, most information is numerical, and lower and upper
bounds usually suffice as conditions. On the other hand,
software engineering usually deals with free-text specifica-
tions, and for these some sort of symbolic representation
must be found, e.g., by picking the most salient keywords
and defining conditions by explicitly enumerating the required
keywords.
Third, the design parameters and their associated sets
of constraints have to be represented in the relational
model. For example, a numerical design parameter with
constraints defined by intervals might be represented by a
three-column table having a tuple (principal, lower bound,
upper bound) for each constraint on the design parameter.
Finally, the operations constrain, release and peek need
to be implemented as ACID transaction procedures, where
constrain and peek would presumably invoke custom procedures
for satisfiability testing and intersection, respectively

Note that with this scheme, applications can continue
to use ordinary ACID transactions. In fact, if "wrapper"
transactions are written for access to non-shared parame-
ters, transparently inserting calls to constrain and release
their governing shared parameters as outlined above, then
applications need not be aware of the constraint framework
at all.
6. Handling distribution and replication
Our goal is now to extend the (CC) and (CD) guarantees
to a distributed and replicated constraint system. We assume
that replicas may operate temporarily in disconnected
mode, without being able to exchange operations with other
replicas. In this case, two incompatible constrain operations
may be executed at different replicas, raising a conflict
when the replicas are eventually merged. If (CC) and
(CD) are to be maintained under these assumptions, no
such conflicts can be allowed. Hence, constrain operations
must be executed pessimistically. release and peek operations
are less critical, because they can never raise conflicts
on a merge.
6.1. Intention locks
We introduce intention locks as a means to protect disconnected
replicas from incompatible constrain operations.
Intention locks are acquired while the replicas are still con-
nected, and held until reconnection occurs.
The idea behind intention locks is to announce changes
anticipated for the period of disconnected operation. Obvi-
ously, some advance knowledge of these changes is necessary
to acquire the proper locks, but this is not an unreasonable
assumption. If a sales representative copies data to her
notebook and meets with a customer to discuss a design,
she probably has a rough idea of which data may change.
Formally, intention locks are conditions in the sense of
Section 3, i.e., one-dimensional specifications expressed in
some language L. Intention locks are always associated
with a replica and, unlike constraints, do not have a princi-
pal. Also, there are two kinds of intention locks, and their
semantics is somewhat different from conditions.
The two kind of intention locks correspond to classical
shared and exclusive locks and reflect the two different attitudes
a designer may exhibit towards a design parameter.
Firstly, a design parameter x may be viewed as input to
a design task. In this case, the designer will presumably use
peek to obtain the current range of x and then use constrain
to re-impose this range (or perhaps a range somewhat nar-
rower) as a design assumption. The semantics of this constraint
is that she is prepared to accept any outcome of the
design process as long as her design assumption is satisfied.
In particular, she is prepared to accept arbitrary constraints
imposed on x by other principals, perhaps on other replicas,
as long as these other constraints have nonempty intersection
with her own. To express this attitude when about to
enter disconnected mode, she would request a shared intention
lock on x with a range equal to the minimum range acceptable
to her. A shared intention lock on x with range S
held by a replica prohibits other replicas from imposing
constraints on x with a range disjoint from S. As such
it is very similar to a constraint, except that shared intention
locks are immediately and globally published, whereas
constraints are only eventually published (see the section
on protocol implementation below).
Second, a design parameter x may be viewed as a (yet
unknown) output of a design task. In this case, a designer
may foresee that she needs to impose certain constraints
on x, but does not yet know what these constraints will be.
In order to keep other designers from restricting her freedom
of choice, she will want to impose a lock that prohibits
other principals from introducing any constraints on x that
eliminate values she considers potentially interesting. This
attitude is expressed by requesting an exclusive intention
lock on x with a range that is the union of all constraints
the designer might want to introduce later. An exclusive
intention lock on x with range S held by a replica prohibits
other replicas from imposing constraints on x with a range
that does not include S.
The entire locking protocol is determined by the following
rules. The first two rules govern the acquisition of
locks, and the last rule governs the execution of constrain
operations (release and peek operations are always permit-
ted).
Shared lock acquisition A request for a shared intention
lock on design parameter x with range S will be
granted iff the following conditions are met:
1. If another replica holds an exclusive intention
lock on x with range X , then S ' X .
2. If another replica holds a shared intention lock
on x with range S 0 , then S " S 0 6= ;.
Exclusive lock acquisition A request for an exclusive intention
lock on design parameter x with range X will
be granted iff the following conditions are met:
1. No other replica holds an exclusive intention
lock on x.
2. If another replica holds a shared intention lock
on x with range S, then X ' S.
Constraint introduction A request constrain(x; S) executed
on some replica will succeed iff the following
conditions are met:
1. The replica holds a shared intention lock on x
with a range S 0 ' S or an exclusive intention
lock on x with a range X " S 6= ;.
2. The intersection of S and all other constraints
currently imposed on x at that replica is non-empty
and, if the replica holds an exclusive intention
lock on x, meets the range of that lock.
Note that the admissibility of a constrain operation can
be decided locally, whereas the acquisition of locks requires
global communication. How exactly this global
communication is implemented is discussed next.
6.2. Protocol implementation
The protocol for the acquisition of intention locks may
seem simple at first, but the details are somewhat complex.
We note first that constrain operations can be executed locally
at a replica without communication. The resulting
constraints can be propagated eventually to the other repli-
cas, along with the release of the lock covering the opera-
tion. The difficult part is setting and releasing the intention
locks. We call these operations global, because they must
be propagated to all replicas. Global operations can be executed
asynchronously as long as all replicas execute them
in the same order. In particular, a disconnected replica will
see and execute global operations originating from other
replicas only at reconnection time, but as long as their ordering
is preserved, the protocol will remain correct.
The set of replicas will usually be divided into a set of
connected partitions. It is easy to show that only one parti-
tition can be permitted to execute global operations. Now
the problem is to decide which partition is allowed to initiate
global operations. Usually this is done using a quorum
consensus algorithm. However, in our scenario the majority
of replicas might be offline, so that there is no partition
big enough to achieve a quorum. In this case the requirements
for a quorum have to be modified accordingly, e.g. a
quorum could be any partition that contains more than half
of the members of the last quorum.
Last, but not least, even inside a quorum only one replica
can initiate a global operation. No other replica can initiate
a global operation until the preceding global operation has
been completed by all other replicas within the quorum.
7. Conclusions and open problems
We started from the observation that design, unlike most
other business processes, is a process of successive refinement
and monotonous information accretion. This led us
to adopt constraints as the basic design objects. We then
investigated how concurrent design can be achieved within
the constraint framework, and showed how the basic guarantees
of the constraint model, combined with the explication
of design assumptions, lead to a very natural coordination
model that does not require any additional transaction
management. Finally, we presented implementation mechanism
for centralized and distributed constraint systems,
thus demonstrating the basic feasibility of the approach.
The most interesting continuation of this work is certainly
the handling of multidimensional constraints, where
a constraint can specify dependencies between several design
parameters. Unfortunately, the time needed to compute
intersection and satisfiability of such multidimensional
constraints tends to grow rather fast with the number
of dimensions. Further work is necessary to identify constraint
languages and implementation techniques that can
handle multidimensional constraints with reasonable performance




--R

Fuzziness in Database Management Systems.
A Mathematical Theory of De- sign: Foundations
Fuzzy Logic in Data Modeling.
Asynchronous consistency restoration under epsilon serializability.
Database Transaction Models.
A methodology for the reduction of imprecision in the engineering design process.
Constraint Query Languages.
Constraint Databases.
Relaxing the limitations of serializable transactions in distributed systems.
Constraint databases: A survey.
Concurrent Constraint Programming.
Fuzzy Sets in Engineering Design and Configuration.
General design theory and a CAD system.
Fuzzy Sets.
Zimmermann, editor. Practical Applications of Fuzzy Technologies.
--TR
Nested transactions: an approach to reliable distributed computing
RCSMYAMPERSANDmdash;a system for version control
Sagas
Cooperative transaction hierarchies: a transaction model to support design applications
Toward a unified framework for version modeling in engineering databases
ACTA: a framework for specifying and reasoning about transaction structure and behavior
Principles and realization strategies of multilevel transaction management
A flexible and adaptable tool kit approach for transaction management in non standard database systems
Multi-level transactions and open nested transactions
Concurrent constraint programming
Implementing extended transaction models using transaction groups
Fuzzy logic in data modeling
Constraint query languages (preliminary report)
Relaxing the limitations of serializable transactions in distributed systems
Practical Applications of Fuzzy Technologies
Fuzziness in Database Management Systems
A Mathematical Theory of Design
Constraint Databases
Constraint Databases
constraints;concurrent design;databases;consistency