home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / database / theory / 421 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  2.3 KB
  1. Path: sparky!uunet!stanford.edu!agate!triplerock.CS.Berkeley.EDU!mao
  2. From: mao@triplerock.CS.Berkeley.EDU (Mike Olson)
  3. Newsgroups: comp.databases.theory
  4. Subject: Re: What is the _Halloween Problem_ ?
  5. Date: 28 Aug 1992 17:43:57 GMT
  6. Organization: University of California at Berkeley
  7. Lines: 40
  8. Message-ID: <17loktINN7mi@agate.berkeley.edu>
  9. References: <1992Aug24.000720.7563@news2.cis.umn.edu> <22838@sybase.sybase.com> <1992Aug28.161050.668@news2.cis.umn.edu>
  10. NNTP-Posting-Host: triplerock.cs.berkeley.edu
  11.  
  12. In <1992Aug28.161050.668@news2.cis.umn.edu>, kencham@ulysses.cs.umn.edu
  13. (Deepak) writes:
  14.  
  15. > Consider the query,
  16. > 
  17. >     Update OneK
  18. >     Set unique2 = 10002
  19. >     where unique2 == 10001;
  20. > 
  21. > According to some systems, this is an instance of the 
  22. > _Halloween Problem_. How ? Besides violation of entity constraint 
  23. > what is the other problem that makes it _HP_ for some systems.
  24.  
  25. strictly speaking, this isn't an instance of the halloween problem; it's
  26. a query that could lead to the halloween problem (seeing your own updates)
  27. if you choose a particular access path.
  28.  
  29. suppose the dbms chooses to do a sequential scan of onek, and suppose
  30. the table is clustered on unique2.  then whenever we see a 10001, we
  31. change it to 10002, and move the tuple containing it to a new location in
  32. the table.  later in our sequential scan, we'll see the new record.
  33. transaction semantics force us never to see our own updates, so this is
  34. a violation of transaction semantics.
  35.  
  36. in general, any time you set a value in the target list that you read
  37. elsewhere in the query (either in computing target list expressions or
  38. in a qualification), it's possible to construct a scenario in which the
  39. halloween problem occurs.  existing dbms' generally use some technique
  40. to mark records that should be invisible to the current transaction to
  41. get around this.  oracle, for example, writes monotonic timestamps on
  42. updated pages, and uses the undo log to restore database state to the
  43. transaction's start time.  if a page has not been modified since the
  44. current xact started, then all values on it are visible to the current
  45. transaction.  postgres uses transaction identifiers and commit times on
  46. every record, and computes visibility for every record it reads.
  47.  
  48.                     mike olson
  49.                     project sequoia 2000
  50.                     uc berkeley
  51.                     mao@cs.berkeley.edu
  52.