News Column

Patent Issued for Halloween Protection in a Multi-Version Database System

September 9, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- A patent by the inventors Freedman, Craig Steven (Sammamish, WA); Cunningham, Conor John (Austin, TX), filed on October 29, 2010, was published online on August 26, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8818963 is assigned to Microsoft Corporation (Redmond, WA).

The following quote was obtained by the news editors from the background information supplied by the inventors: "Background and Relevant Art

"Computers and computing systems have affected nearly every aspect of modern living. Computers are generally involved in work, recreation, healthcare, transportation, entertainment, household management, etc.

"Data in computing systems is often stored in one or more databases. A database is a collection of related data. Data in the database are commonly organized in a two-dimensional row and column form called a table. A database typically includes multiple tables and multiple associative structures. A table is an object in the database containing zero or more records and at least one field within each record. A record may be embodied as a row in the table that is identified by a unique numeric called a record identifier. A field is a subdivision of a record to the extent that a column of data in the table represents the same field for each record in the table. An example of an associative structure in a database is an index, typically, but not necessarily, a form of B-tree or hash index. Associative structures are transparent to users of a database but are important to efficient operation and control of the database management system. A database management system is a control system that supports database features including, but not limited to, storing data on a memory medium, retrieving data from the memory medium and updating data on the memory medium.

"A query is used to access or update data in a database. The query is typically constructed in a variant of Structured Query Language (SQL) that may or may not be compliant with the American National Standards Institute (ANSI) standard SQL definition. A SQL query is non-procedural in that it specifies the objective or desired result of the query in a language meaningful to a user but does not define the steps or procedure by which the query should be accomplished. When a SQL query is applied to a database, the query optimizer of the database management system processes the non-procedural query to create an execution plan. An execution plan is procedural in that it determines the order and type of operations or operators to be performed to carry out the objectives of the SQL query. The combination of non-procedural update requests (SQL queries) and procedural execution plans creates both the opportunity and the need for automatic planning of execution plans by the query optimizer. A query optimizer can generate a plurality of different query plans for any given SQL query and is typically configured to generate a query plan according to efficiency objectives.

"An update is a common type of query executed on data in a database. An update is any operation that modifies existing records in a database as well as insertions and deletions of records in a database. As used herein, an update includes any database modification, including value changes (updates in the narrow sense), insertions, deletions, upserts (combination of update and insert which updates if exists in the database or inserts if does not exit), merges, etc. The semantics of execution plans may be prescribed by the ANSI/ISO standard for SQL languages. According to this standard, the semantics of any update statement is the same as three separate phases of execution, with no overlap between phases. First, a read-only search of the database determines the records to be updated, inserted or deleted as well as the new column values. Second, records and columns are updated. Third, consistency constraints defined for the database are verified.

"An update to a record in a table also includes updates to index entries in indexes and other associative structures associated with the updated table. Changes to associative structures, in fact the associative structures themselves, are typically not visible to a user as they result from the procedural execution of the execution plan.

"An operator using record-at-a-time pipelining fully processes, i.e., produces output, each time a record satisfying the predicate of the query is located. An operator using set-at-a-time pipelining consumes all of its input and only then is output produced from the operator. Record-at-a-time processing may be more efficient in traditional systems for small cardinality changes. Large cardinality changes may be more efficient in the set-at-a-time approach because it can sort records and perform changes using sequential IO instead of random IO against traditional disk drives.

"There is a particular problem in the field of database updating known as the Halloween problem. The Halloween problem has been well known since it was first noticed on Halloween day, 1975 by researchers at IBM's San Jose research laboratories. The Halloween problem in database systems may be evident in data modification statements (inserts, updates, and deletes) generating incorrect results because the process of modifying the database state changes the behavior of the executing statement and induces it to modify the wrong set of records (either due to skipping records or due to modifying the same records multiple times).

"A typical example for the Halloween problem is the request (a SQL query) to 'give all employees with salaries greater than $30,000 a 5% raise'. If (i) these employees are found using an index on salaries, and (ii) index entries are scanned in increasing salary order, and (iii) the scan cannot distinguish index entries that have already been updated by this request from those that have not, and (iv) the index is updated immediately as index entries are found (record-at-a-time pipelining), then each qualifying employee will get an infinite number of raises. Thus, processing this request will not terminate.

"One simple solution to the Halloween problem is physical phase separation in which the identification of the set of records to modify and the actual modification of these records are run serially (one after the other) rather than concurrently. In one simple example, a blocking operator such as a spool is used to achieve physical phase separation. More complex solutions involve exploiting detailed knowledge of the behavior of the underlying query processor and storage engine to generate plans and/or to analyze and prove that selected plans will behave correctly without physical phase separation, without the use of a spool or other blocking operator, and in spite of running both phases concurrently.

"While there are several known approaches to avoiding the Halloween problem, such approaches often result in significant increases in overhead resources such as storage space resources or processing resources.

"The subject matter claimed herein is not limited to embodiments that solve any disadvantages or that operate only in environments such as those described above. Rather, this background is only provided to illustrate one exemplary technology area where some embodiments described herein may be practiced."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventors' summary information for this patent: "One example illustrated herein is directed to a method practiced in a computing environment. The method includes acts for mitigating problems related to the Halloween problem including where update operations potentially allow the record to be visited more than once during the operation. The method includes accessing an instance of a data store operation statement. The instance of the data store operation statement is executed. Executing the statement causes an update or delete to an old version of a data store record or creation of a data store record. Updating a data store record or creating a data store record results in a new version of the data store record. Deleting a data store record results in a deleted version of the data store record. The instance of the data store operation statement is correlated with the new version of the data store record or the deleted version of the data store record.

"This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

"Additional features and advantages will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the teachings herein. Features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. Features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter."

URL and more information on this patent, see: Freedman, Craig Steven; Cunningham, Conor John. Halloween Protection in a Multi-Version Database System. U.S. Patent Number 8818963, filed October 29, 2010, and published online on August 26, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8818963.PN.&OS=PN/8818963RS=PN/8818963

Keywords for this news article include: Information Technology, Information and Data Management, Microsoft Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters