System and method for database having relational node structure

• US 7,333,994 B2
• Filed: 12/18/2003
• Issued: 02/19/2008
• Est. Priority Date: 12/18/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Glover, Andrew, Dabrowski, Michael, Clement, Samuel
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Ahluwalia; Navneet K
• Application Number:
  US10/738,252
• Publication Number:
  US 20050138003A1
• Time in Patent Office: 1,524 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205
• US Class Current: 707/796
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and related techniques and data structures present a Web based or other client application or service with a relational node structure to access, store and manipulate XML-based or XML-compliant data. Unlike unmodified XML information for instance stored in document object model (DOM) format, the inventive platform may load a relational node structure encapsulating XML-compliant information in an organized structure having pointers to next peer, parent, child and other links to related or unrelated information. Searching, querying and other operations may therefore be made more efficient since an entire tree structure need not be exhaustively traversed to locate desired data, but instead sorted via those relational linkages. Client applications such as Web browsing, email, contacts managers, calendars and others may therefore operate on XML or XML-compliant data without the loading or performance disadvantages which conventional XML platforms may incur. The data populating the relational node structure may be obtained from XML or structured sources, and for instance be loaded from storage in response to a query generated via the query engine.

Claims

1. A database system, comprising:

an interface to a query engine;

a database layer; and

a relational node structure, communicating with the interface to the query engine and the database layer, the relational node structure comprising a set of nodes configured to store data from the database layer and encoding a set of pointers that provide direct relational linkages between child nodes in the set of nodes,

wherein the set of pointers provides a map of an interrelational structure of the child nodes thereby enabling search logic to bypass branches of the relational node structure when searching therein,

wherein the set of pointers encoded in the set of nodes extends at least in three dimensions including a child-to-parent node dimension, a next like peer node dimension, and a left-to-right peer node dimension, and data from the database layer is populated into at least one node within the set of nodes in response to processing a query from the query engine,

wherein the next like peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes residing at a similar level of the relational node structure having similar attributes therein, wherein the left-to-right peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes organized in an adjacent lateral structure,

wherein the next like peer node dimension and the left-to-right peer node dimension facilitate laterally searching across child nodes and directly retrieving data therefrom without further parsing the relational node structure, and

wherein the set of nodes within the relational node structure is configured to store extensible markup language (XML)-based information such that the query engine generates XML data therefrom.

2. A system according to claim 1, wherein the database layer comprises a structured database.

3. A system according to claim 1, wherein the relational node structure is stored in memory.

4. A system according to claim 1, wherein the query engine transmits a query to run against the relational node structure.

5. A system according to claim 1, wherein the query run against the relational node structure is executed via a binary search.

6. A method of processing data in a database system, comprising:

receiving a query generated via a query engine;

communicating the query to a relational node structure comprising a set of nodes configured to store data from a database layer and encoding a set of pointers that provide direct relational linkages between child nodes in the set of nodes,

wherein the set of pointers provides a map of an interrelational structure of the child nodes thereby enabling search logic to bypass branches of the relational node structure when searching therein,

wherein the set of pointers in encoded in the set of nodes extends at least in three dimensions including a child-to-parent node dimension, a next like peer node dimension, and a left-to-right peer node dimension,

wherein the next like peer node dimension and the left-to-right peer node dimension facilitate laterally searching across child nodes and directly retrieving data therefrom without further parsing the relational node structure,

wherein the next like peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes residing at a similar level of the relational node structure having similar attributes therein, wherein the left-to-right peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes organized in an adjacent lateral structure,

wherein the set of nodes within the relational node structure is configured to store extensible markup language (XML)-based information such that the query engine generates XML data therefrom; and

populating data from the database layer into at least one node within the set of nodes in response to processing the query generated via the query engine.

7. A method according to claim 6, wherein the query engine comprises an extensible markup language query engine.

8. A method according to claim 6, wherein the database layer comprises a structured database.

9. A method according to claim 6, wherein the relational node structure is stored in memory.

10. A method according to claim 6, further comprising running the query against the relational node structure.

11. A method according to claim 10, wherein the running of the query run against the relational node structure comprises executing a binary search.

12. A data structure storable in computer memory, comprising:

a relational node structure, the relational node structure comprising—

a set of nodes configured to store data from a database layer, and

a set of pointers that provide direct relational linkages between child nodes in the set of nodes,

wherein the set of pointers provides a map of an interrelational structure of the child nodes thereby enabling search logic to bypass branches of the relational node structure when searching therein,

wherein the set of pointers extends at least in three dimensions including a child-to-parent node dimension, a next like peer node dimension, and a left-to-right peer node dimension, and data from the, database layer is populated into at least one node within the set of nodes in response to processing a query from a query engine,

wherein the next like peer node dimension and the left-to-right peer node dimension facilitate laterally searching across child nodes and directly retrieving data therefrom without further parsing the relational node structure,

wherein the next like peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes residing at a similar level of the relational node structure having similar attributes therein, wherein the left-to-right peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes organized in an adjacent lateral structure, and

wherein the set of nodes within the relational node structure is configured to store extensible markup language (XML)-based information such that the query engine generates XML data therefrom.

13. A data structure according to claim 12, wherein the relational node structure is operable to be interrogated via the query engine.

14. A data structure according to claim 13, wherein the query engine comprises an extensible markup language query engine.

15. A data structure according to claim 12, wherein the database layer comprises a structured database.

16. A database system, comprising:

interface means to a query engine means;

database means; and

relational node means, communicating with the interface means and the database means, the relational node means comprising a set of nodes configured to store data from the database means and encoding a set of pointers that provide direct relational linkages between child nodes in the set of nodes,

wherein the set of pointers provides a map of an interrelational structure of the child nodes thereby enabling search logic to bypass branches of the relational node structure when searching therein,

wherein the set of pointers encoded in the set of nodes extends at least in three dimensions including a child-to-parent node dimension, a next like peer node dimension, and a left-to-right peer node dimension, and data from the database means is populated into at least one node within the set of nodes in response to processing a query from the query engine means,

wherein the next like peer node dimension and the left-to-right peer node dimension facilitate laterally searching across child nodes and directly retrieving data therefrom without further parsing the relational node structure,

wherein the next like peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes residing at a similar level of the relational node structure having similar attributes therein, wherein the left-to-right peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes organized in an adjacent lateral structure, and

wherein the set of nodes within the relational node structure is configured to store extensible markup language (XML)-based information such that the query engine generates XML data therefrom.

17. A system according to claim 16, wherein the query engine means comprises an extensible markup language query engine.

18. A transmissible query result, the query result being generated according to a method of:

receiving a query generated via a query engine; and

communicating the query to a relational node structure comprising a set of nodes configured to store data from a database layer and encoding a set of pointers that provide direct relational linkages between child nodes in the set of nodes,

wherein the set of pointers provides a map of an interrelational structure of the child nodes thereby enabling search logic to bypass branches of the relational node structure when searching therein,

wherein the set of pointers encoded in the set of nodes extends at least in three dimensions including a child-to-parent node dimension, a next like peer node dimension, and a left-to-right peer node dimension,

wherein the next like peer node dimension and the left-to-right peer node dimension facilitate laterally searching across child nodes and directly retrieving data therefrom without further parsing the relational node structure,

wherein the next like peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes residing at a similar level of the relational node structure having similar attributes therein, wherein the left-to-right peer node dimension is a type of pointer of the set of pointers that provides a direct relational linkage between the child nodes organized in an adjacent lateral structure, and

wherein the set of nodes within the relational node structure is configured to store extensible markup language (XML)-based information such that the query engine generates XML data therefrom;

populating data from the database layer into at least one node within the set of nodes in response to processing the query generated via the query engine; and

executing the query against the relational node structure to generate a query result.

19. A query result according to claim 18, wherein the query engine comprises an extensible markup language query engine.

20. A query result method according to claim 18, wherein the relational node structure is stored in memory.