Steven Bailey

US Patent:

7120637, Oct 10, 2006

Filed:

May 30, 2003

Appl. No.:

10/448584

Inventors:

Steven J. Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/30

US Classification:

707100, 707 1, 707 3, 707102, 711170

Abstract:

A b-tree having information stored therein is utilized to facilitate positional access of elements stored in the leaves of the b-tree. The b-tree is structured such that for each non-leaf level value, a count is located to its immediate left and a value is located to its immediate right. These left and right counts indicate the number of leaf level values located in the leaves of the sub-trees to the immediate left and right of the value. The left and right counts are used to determine the path to take when descending the b-tree in search of a specific position. The counts can also be utilized to determine the total number of values in the leaf level of the b-tree.

US Patent:

7296043, Nov 13, 2007

Filed:

May 30, 2003

Appl. No.:

10/448847

Inventors:

Steven J. Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 12/00
G06F 17/30
G06F 7/00
G06F 17/00

US Classification:

707205, 707101, 707 2

Abstract:

Shrinking a database file is performed by manipulating pages within the file such that all empty pages reside at the end of the file. Non-empty pages from the end of the file are written to empty pages at the start of the file. Repeating this process, the correct number of times, results in all of the empty pages residing at the end of the file. Once this is achieved, the file is truncated such that the space consumed by all empty and discardable pages is returned to the file system. Truncating the file involves traversing the file backwards from the end of the file until the first non-empty page is found. The file is truncated after the last non-empty page.

US Patent:

7389308, Jun 17, 2008

Filed:

May 30, 2003

Appl. No.:

10/448585

Inventors:

Steven J. Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/30

US Classification:

707200, 707202, 707203, 707205

Abstract:

Shadow paging is a technique used to achieve atomic and durable transactions, and provides the ability to manipulate pages in a database. During a transaction, the pages affected by the transaction are copied from the database file into a workspace, such as volatile memory, and modified in that workspace. When a transaction is committed, all of the pages that were modified by the transaction are written from the workspace to unused pages in the database file. During execution of the transaction, the state of the database exposed to the user is that in which the database existed prior to the transaction, since the database file still contains the original versions of the modified pages, as they existed before being copied into the workspace. If a user accesses the database before the transaction is complete, or upon recovery of a failure, it will appear as though the transaction has not occurred.

US Patent:

7631010, Dec 8, 2009

Filed:

Apr 16, 2004

Appl. No.:

10/826509

Inventors:

Steven Bailey - Sammamish WA, US
David J Nettleton - Seattle WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/00

US Classification:

707103Y, 707200

Abstract:

Systems and methodologies are provided for enforcing a set of conditions such that prior to a commit stage of a transaction, a space availability for a particular page can be typically assured (e. g. , that transactions operating on various copies of the page do not consume all of storage space on that page), and reorganization of data around the page is mitigated (e. g. , that a transaction need not move data around the page for purpose of merging various copies. ) A page aggregator and a heap manager can facilitate operations of concurrent transactions at a subpage level (e. g. , a row level), during such modifications of a data base by multiple users.

US Patent:

7650360, Jan 19, 2010

Filed:

Apr 16, 2004

Appl. No.:

10/826517

Inventors:

Steven Bailey - Sammamish WA, US
David J Nettleton - Seattle WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/00

US Classification:

7071041, 710200

Abstract:

Systems and methodologies are provided in a lock hierarchy arrangement wherein upon release of all child locks associated with a parent lock, then such parent lock is also released. The present invention supplies each lock with sufficient information to determine its own life time. Such framework enables a higher degree of transaction concurrency in a database, and mitigates an over locking thereof, thus conserving system resources.

US Patent:

7657556, Feb 2, 2010

Filed:

Jan 26, 2006

Appl. No.:

11/341182

Inventors:

Steven J. Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G07F 17/30

US Classification:

707102, 707100, 707101, 707103 R, 7071041

Abstract:

A b-tree having information stored therein is utilized to facilitate positional access of elements stored in the leaves of the b-tree. The b-tree is structured such that for each non-leaf level value, a count is located to its immediate left and a value is located to its immediate right. These left and right counts indicate the number of leaf level values located in the leaves of the sub-trees to the immediate left and right of the value. The left and right counts are used to determine the path to take when descending the b-tree in search of a specific position. The counts can also be utilized to determine the total number of values in the leaf level of the b-tree.

US Patent:

7707195, Apr 27, 2010

Filed:

Jun 29, 2004

Appl. No.:

10/879664

Inventors:

David J. Nettleton - Seattle WA, US
Steven Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/30

US Classification:

707704

Abstract:

Systems and methodologies are provided that employ an allocation lock, which permits only a single transaction to acquire space on a particular page at any one time. The allocation lock of the present invention facilitates operations of concurrent transactions at a subpage level (e. g. , a row level), and in conjunction with a heap manager can enforce a set of conditions such that prior to a commit stage of a transaction, a space availability for a particular page can be typically assured (e. g. , that transactions operating on various copies of the page do not consume all of storage space on that page), and reorganization of data around the page is mitigated (e. g. , that a transaction need not move data around the page for purpose of merging various copies. ).

US Patent:

7979408, Jul 12, 2011

Filed:

Apr 1, 2010

Appl. No.:

12/752816

Inventors:

David J. Nettleton - Seattle WA, US
Steven Bailey - Sammamish WA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 7/00

US Classification:

707704, 707613

Abstract:

Systems and methodologies are provided that employ an allocation lock, which permits only a single transaction to acquire space on a particular page at any one time. The allocation lock of the present invention facilitates operations of concurrent transactions at a subpage level (e. g. , a row level), and in conjunction with a heap manager can enforce a set of conditions such that prior to a commit stage of a transaction, a space availability for a particular page can be typically assured (e. g. , that transactions operating on various copies of the page do not consume all of storage space on that page), and reorganization of data around the page is mitigated (e. g. , that a transaction need not move data around the page for purpose of merging various copies. ).