Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!odi!dlw
From: dlw@odi.com (Dan Weinreb)
Newsgroups: comp.object
Subject: Re: Looking for explanation of OODB problem
Message-ID: <1991Jun10.223352.8771@odi.com>
Date: 10 Jun 91 22:33:52 GMT
References: <1991Jun6.194440.2879@apd.mentorg.com> <1991Jun8.114630.1@happy.colorado.edu>
Reply-To: dlw@odi.com
Followup-To: comp.object
Organization: Object Design, Inc.
Lines: 160
In-Reply-To: hsrender@happy.colorado.edu's message of 8 Jun 91 17:46:30 GMT

I think I am in a good position to explain what's going on here.  I've
known Dan Gerson for about ten years.  Between 1985 and 1988, we
worked together at Symbolics on the design and development of an
object-oriented database system (called Statice), which is now a
product.

When the journalist from Unix Today talked to Dan, Dan brought up a
topic that he's been interested in for a long time: the interplay
between interactive I/O and concurrency control, specifically in the
face of deadlocks, aborts, and retries.  Unfortunately, this is a
rather technically abstruse topic, and it appears that the journalist
really didn't understand it at all.  I've exchanged mail with Dan
since the article came out, and he is pretty unsatisfied with the
level of understanding reflected in the article.

There are several, related problems that he's interested in.  To
illustrate them, consider the following scenario.  There is a database
containing information about the canonical domain: employees and
departments.  There is a user interface for examining and updating
information in the database.  In a typical scenario of updating data,
the person says "show me John Smith"; a bunch of data about John Smith
appears on the screen; the person clicks on some fields and types in
some new values; the person says "OK, I am satisfied with these
changes, write it back"; and the database gets updated.

Now, in this scenario, there are two ways that you might divide it
into transactions.  In scheme 1, the whole thing is one transaction.
The transaction starts when we call up the information, and the
transaction ends when we say that we are satisfied.  In schema 2,
there are two transactions instead of one.  The first transaction
reads the data from the database so that it can be displayed on the
screen, and then immediately commits (having made no modifications).
Then we interact with the data.  Finally, when we say we're satisfied,
a second transaction starts, the data items that were displayed on the
screen are written back to the database, and the second transaction
commits.

Under simple circumstances, the two schemes will have the same effect.
However, they can behave differently if someone else is changing the
database while we are doing our interaction.  They can also behave
differently if certain clever concurrency control and caching schemes
are being used.  An example of the latter is optimistic concurrency
control combined with caching, which can cause transactions to abort
because it is discovered that obsolete cached data has been used.
This sort of thing is discussed in two papers in the recent SIGMOD
proceedings.  If someone else is changing the database, or if one of
these concurrency control or caching schemes is being used, any
transaction might deadlock, and so the user's transaction might be
forcibly aborted by the database system.

The problem of aborts is much more severe in scheme 1 than in scheme
2, for two reasons: an abort is more likely, and an abort is more
problematic.  An abort is more likely in scheme 1 because the
transaction is so much longer in duration.  The transaction in scheme
1 spans user interaction, which would take at least seconds and
possibly even hours (suppose we get up for a coffee break in the
middle of editing an entry).  An abort is more problematic because we
have to start all over again; all our work is lost, for apparently no
reason.  If your user interface did this to you, you'd certainly be
frustrated.

You might think that we don't really have to do our work over again;
the user interface system can simply retain the changes that we've
typed in, and restart the transaction invisibly.  That's true, but
there's a hazard: when we start the transaction again, the database
state might have changed, and the new values that we typed into the
user interface might have depended on the values that were displayed
when we started.  For example, suppose I am in the process of
approving a loan application for an employee.  I call up his record on
the screen, scrutinize various field values, and decide that he should
get the loan.  While I'm reading and updating fields, someone else
makes changes to the employee's records, noting that he has just been
convicted of embezzlement.  This causes a deadlock, and I start again,
and now I really had better redo all my consideration and
scrutinization, to see if anything has changed since I last made my
decision.  In other words, if I expect my own interaction with the
database to behave like a transaction, moving from one consistent
state to another consistent state, then I have to behave in an
appropriately transaction-like way, which means starting all over when
there's an abort.

In scheme 2, the transactions are very short and quick. And if they
abort, there's no problem with just automatically starting them again.
However, scheme 2 still suffers from the problem that some other user
might modify some of the data about the employee while we're in the
middle of doing my interactions.  In fact, in scheme 2, even if
ordinary locking is used for concurrency control, we are not holding
any locks, so nothing prevents the employee's data from being changed
"out from under" us.  When our second transaction goes back to store
the data, in fact, we might overwrite someone else's changes.

To my mind, the most important question is: "What is the goal?"  That
is, if two people find themselves editing the same thing at the same
time, what ought to happen, anyway?  Several alternatives make some
sense, but I don't think it's immediately obvious which is best.

This read-modify-store scenario is very simple compared to what we see
in the real world.  There are many problems involving the way
concurrency control works in the presence of interactive user
interfaces.  This is the class of issue that Gerson was talking about.

None of this actually has much to do with "object-oriented databases",
though.  Anything that has a general concurrency control scheme (by
"general" I mean that deadlock avoidance can't be used because it
can't be determined in advance the total set of data items that will
be referenced) will exhibit the same problem.

My colleague Jack Orenstein started writing another reply to this posting,
and we decided to pool our replies together.  Jack says:

  I agree with Hal Render's analysis of the problem. Applications often
  have conflicting requirements on transaction boundaries. On one hand,
  transactions should be kept as short as possible, to maximize
  concurrency. On the other hand, it's awfully tempting to do everything
  inside a transaction because the "synchronization" problems then
  disappear.  (In MVC terms, you have to make sure that your own updates
  of the model are propagated to all views, but you don't have to worry
  about updates posted by someone else.) This is a problem no matter
  WHAT kind of database system is used, relational, object-oriented, or
  something else, (assuming the database system supports transactions,
  of course).

  I'm with Object Design, and we have an OO DBMS product, ObjectStore.
  As Hal points out, OO DBMSs can have transactions too, and ObjectStore
  does.  We provide start-transaction and end-transaction function
  calls, and it is up to the user to select the proper transaction
  granularity. Our part of the deal says that any work done inside a
  transaction will be isolated from any concurrent transactions;
  execution is serializable. If your application is such that the whole thing
  can run in one transaction, that's great - you'll have a particularly
  simple programming job, since your program can manipulate the objects
  in the database directly; you won't have to deal with copies of
  objects, (and you will still get the usual guarantees of transactions,
  e.g. all-or-none behavior.)  If this won't get you enough concurrency,
  then you'll have to work on copies of objects or parts thereof, e.g.
  certain fields from an object in the model that are to be displayed in
  a view.

Of course if no transaction is in progress, you cannot directly
manipulate objects in the database, since direct manipulation of
database objects has to set database locks, and that can only happen
inside a transaction.  But if you split up your program into little
transactions and work on data in between transactions, you still have
to worry about what happens if the state of the database changes out
from under you.

  To bring this back to the original discussion: if you do an
  interactive application over a database system, and you want to keep
  transactions as short as possible, you will have the problem of
  keeping views consistent with models, and you'll have to take
  snapshots of the database, i.e. copies. This is in the nature of
  concurrency, and is not a problem of a particular data model
  (relational or OO).  But in situations where longer transactions are
  okay, relational DBMSs again force you to work on copies of objects
  while OO DBMSs allow you to manipulate objects directly.

A lot of this was lost in the Unix Today article.

-- Dan Weinreb (with Jack Orenstein)
Object Design, Inc.