ハロウィーンの問題

コンピューティングにおいて、ハロウィーン問題とは、データベースにおいて更新操作によって行の物理的な位置が変更され、同じ更新操作で後でその行が再度アクセスされる可能性がある現象を指します。場合によっては、更新によって更新されたレコードが更新操作を実行するスキャンよりも前に継続的に配置されるため、無限ループが発生することもあります。

このデータベース エラーの可能性は、 1976 年のハロウィーンの日にDon Chamberlin、Pat Selinger、および Morton Astrahan によって初めて発見されました。このとき、クエリは給与が 25,000 ドル未満の従業員全員に 10 パーセントの昇給を与えることを目的としたものでした。このクエリはエラーなく正常に実行されましたが、完了したときにはデータベース内のすべての従業員の給与が少なくとも 25,000 ドルになっていました。これは、そのレベルに達するまで昇給が与えられ続けたためです。このクエリは、給与が 25,000 ドル未満の従業員レコードをそれぞれ 1 回ずつ繰り返し処理すると予想されていました。実際には、更新されたレコードもクエリ実行エンジンに表示され、クエリの条件に一致し続けたため、給与レコードが複数回一致し、そのたびに 10 パーセントの昇給が与えられ、最終的にはすべてが 25,000 ドルを超えました。

この名前は問題の性質を表すものではなく、問題が発見された日にちにちなんで付けられたものである。ドン・チェンバレンが語ったところによると: ^[1]

パットとモートンはハロウィーンにこの問題を発見しました... 彼らが私のオフィスに来て、「チェンバリン、これを見てください。オプティマイザが更新処理の計画を立てるときに、更新されるフィールドに基づくインデックスを使用しないようにする必要があります。どうすればいいですか?」と言ったのを覚えています。たまたま金曜日だったので、私たちは「聞いてください、この問題を今日の午後に解決することはできません。名前を付けましょう。ハロウィーン問題と呼んで、来週取り組みます。」と言いました。そして、それ以来ずっとその名前で呼ばれるようになりました。

• 1995 年の SQL 再会 (プロトコル)
• XML API の「ハロウィーン問題」、Mike Champion のウェブログ。
• (アーカイブ)善意のクエリとハロウィーン問題、ロスアラモス国立研究所、逸話、IEEE Annals of the History of Computing