home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / database / theory / 413 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  2.6 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!ucbvax!mtxinu!sybase!houdini!jeffl
  2. From: jeffl@houdini.sybase.com (Jeff Lichtman)
  3. Newsgroups: comp.databases.theory
  4. Subject: Re: What is the _Halloween Problem_ ?
  5. Message-ID: <22838@sybase.sybase.com>
  6. Date: 26 Aug 92 20:01:00 GMT
  7. References: <1992Aug24.000720.7563@news2.cis.umn.edu>
  8. Sender: news@Sybase.COM
  9. Organization: Committee to Increase The Entropy
  10. Lines: 74
  11.  
  12. In article <1992Aug24.000720.7563@news2.cis.umn.edu>, kencham@ulysses.cs.umn.edu (Deepak) writes:
  13. > What is the _Halloween Problem_ ?
  14.  
  15. The Halloween Problem is that, when applying updates to a table, the results
  16. of the updates might depend on the order that they are applied.  For example,
  17. suppose you have the following table:
  18.  
  19.     employees (id, salary, manager_id)
  20.  
  21. and you want to give a 10% raise to everyone who earns less than his or her
  22. manager.  In SQL, you would write the query like this:
  23.  
  24.     update employees
  25.     set salary = salary * 1.10
  26.     where salary <
  27.         (select salary
  28.          from employees e
  29.          where e.id = employees.manager_id)
  30.  
  31. (This is how you might write it in Sybase's version of SQL, anyway.)
  32.  
  33. Now suppose the data looked like this:
  34.  
  35.     id    salary        manager_id
  36.  
  37.     1    1000.00        NULL
  38.     2     950.00        1
  39.     3     950.00        1
  40.     4     960.00        2
  41.     5     960.00        3
  42.  
  43. Let's say the database engine updated the rows one at a time, as it saw
  44. them.  If it started from the first row and worked its way down, it would
  45. get the following result:
  46.  
  47.     id    salary        manager_id
  48.  
  49.     1    1000.00        NULL
  50.     2    1045.00        1
  51.     3    1045.00        1
  52.     4    1056.00        2
  53.     5    1056.00        3
  54.  
  55. But, if it started at the last row and worked its way up, it would get the
  56. following result:
  57.  
  58.     id    salary        manager_id
  59.  
  60.     1    1000.00        NULL
  61.     2    1045.00        1
  62.     3    1045.00        1
  63.     4     960.00        2
  64.     5     960.00        3
  65.  
  66. In the latter case, employees 4 and 5 don't get the raise because they are
  67. earning more than their managers at the time when the database engine looks
  68. at their rows.
  69.  
  70. Relational theory mandates that the updates be determined by the state of
  71. the data when the update started.  That is, an update is not allowed to make
  72. any decisions or calculations based on its own partial results.
  73.  
  74. Most relational database systems solve this problem by logging all the changes
  75. that the update will produce before they make any of the changes.  Only
  76. after all the changes are logged will they be applied.  This effectively
  77. makes the results of an update depend on the state of the data at the time
  78. the update started.
  79.  
  80. By the way, I have it on good authority, that it's called the "Halloween
  81. Problem" because it was first thought of on Halloween.
  82. ---
  83. Jeff Lichtman at Sybase
  84. {mtxinu,pacbell}!sybase!jeffl  -or- jeffl@sybase.com
  85. "Saints should always be judged guilty until they are proved innocent..."
  86.