Methods and system for storing and accessing embedded information in object-relational databases

• US 6,016,497 A
• Filed: 12/24/1997
• Issued: 01/18/2000
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Suver, Christopher Allen
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US08/998,334
• Time in Patent Office: 755 Days
• Field of Search: 707/103, 707/101, 707/4, 707/10, 707/3, 707/2, 707/202, 707/204, 707/102, 345/346, 345/356, 364/246, 364/282, 706/45, 706/47, 706/60
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• 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
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A system and computer-implemented methods for accessing and storing information embedded in a column of a database row, especially useful for complex data, that is, data which is logically multi-valued or hierarchical. Embedded data is not stored in a separate table but is stored directly in a complex column comprising embedded data a subtables. A row of data is physically stored in a tagged, variable-length object-relational format, which allows the data to be stored as atomic data values or embedded as collections of data values, data structures, or collections of data structures. The structures can have further levels of embedding, i.e. more collections and/or structures. Embedded data may further include typed data embedded in multiple tables and columns. The query language for accessing the data includes a series of extensions that provide additional access paths to the data. Searches can access data within tables and sub-tables, and can access data by user defined type (UDT) in a single table or across multiple tables.

Claims

1. A method for storing and accessing information in an object-relational database stored in a computer system, the object-relational database comprising one or more tables, the tables each having a table name and comprising one or more rows of information, the method comprising the computer-implemented steps of:

storing a plurality of data elements in a row of information, the row comprising one or more columns, the columns each having a column name, at least one of the columns being an embedded-data column for storing a plurality of the data elements;

receiving a database command for accessing a selected data element, the database command comprising a selected table name and an extension corresponding to a selected column name representing the embedded-data column; and

in response to receiving the database command, accessing a table represented by the selected table name;

in response to accessing the table, accessing the embedded-data column represented by the selected column name; and

in response to accessing the embedded-data column, accessing the selected data element,

whereby a plurality of data elements may be stored in the embedded-data column and, by way of the extension to the database command, may subsequently be accessed from the embedded-data column as if the embedded-data column were a separate table.

2. The method of claim 1, wherein the database command is received in a format generally defined as "TableName.ColumnName".

3. The method of claim 1, wherein the database command may be in any clause of a standard SQL statement.

4. The method of claim 1, wherein the object-relational database further comprises a dictionary;

wherein the dictionary comprises table names and column names; and

wherein the method further comprises the step of, in response to receiving the database command, accessing the dictionary to associate the selected column name with selected table name.

5. The method of claim 1, wherein accessing the embedded-data column represented by the selected column name comprises the steps of:

retrieving a row of information from a physical memory storage device in the computer system;

storing the retrieved row of information in a memory device in the computer system;

parsing the retrieved row of information stored in the memory device to determine which columns have data elements; and

creating an in-memory data structure that represents the contents of the retrieved row of information.

6. The method of claim 5 wherein accessing the selected data element comprises traversing the in-memory data structure to access the selected data element in the embedded-data column.

7. The method of claim 1, wherein each of the columns further comprise a column data type identifier being selected from the group consisting of an atomic value column data type identifier and an embedded-data column data type identifier, the atomic value column data type identifier identifying an atomic value column for storing one of the data elements, and the embedded-data column data type identifier identifying an embedded-data column for storing a further embedded-data column or an additional atomic value column.

8. The method of claim 7, wherein the atomic value column data type identifier indicates that the identified atomic value column stores a single data element.

9. The method of claim 8, wherein the single data element is delimited by at least one atomic value delimiter character.

10. The method of claim 7, wherein an embedded-data column data type identifier indicates that the identified embedded-data column stores a collection of data elements.

11. The method of claim 10, wherein the collection of data elements is delimited by at least one atomic value delimiter character.

12. The method of claim 7, wherein an embedded-data column data type identifier indicates that the identified embedded-data column stores a structure of data elements, the structure of data elements having a corresponding column name and comprising one or more subrows of information, the subrows of information each comprising one or more subcolumns, the subcolumns each having an associated subcolumn name and comprising one or more data elements.

13. The method of claim 12, wherein the structure of data elements is delimited by at least one predetermined structure delimiter character.

14. The method of claim 12, further comprising the step of automatically assigning a unique row identifier to each row in any table or structure.

15. The method of claim 14, further comprising the step of relating a first table to a second table by storing as a data element in the second table the row identifier associated with a selected row in the first table.

16. The method of claim 15, wherein a reference in the first table to data elements in the second table is made by storing the row identifier of a data element from the second table as a data element in a column in the first table.

17. The method of claim 16, wherein an embedded-data column in the first table stores a collection of data elements comprising a plurality of object identifiers of data elements from the second table.

18. The method of claim 1, wherein each row of information in the table is identified by a row identifier and delimited by at least one predetermined row delimiter character.

19. The method of claim 1, wherein each column is delimited by at least one predetermined column delimiter character.

20. A computer-readable medium having stored thereon computer-executable instructions for performing the method steps of claim 1.

21. A method for accessing a selected data element stored in an object-relational database stored in a computer system, the object-relational database comprising one or more tables, the tables each having a table name and comprising one or more rows of information, the rows of information each having a row identifier and comprising one or more columns, the columns each having a column name and comprising embedded-data elements or atomic data elements, the method comprising the computer-implemented steps of:

receiving a database command for accessing a selected data element, the command comprising at least a table name and an extension corresponding to a column name, the column name representing an embedded-data column for storing embedded data elements;

in response to receiving the database command, accessing a table represented by the table name;

in response to accessing the table, accessing the embedded-data column represented by the column name in the database command; and

in response to accessing the embedded-data column, accessing the selected data element.

22. The method of claim 21, wherein the object-relational database further comprises a dictionary;

wherein the dictionary comprises table names and column names; and

where the method further comprises the step of, in response to receiving the database command, accessing the dictionary to associate column names with table names.

23. The method of claim 21, wherein the database command is received in a format generally defined as "TableName.ColumnName".

24. The method of claim 21, wherein the database command may be in any clause of a standard SQL statement.

25. The method of claim 21, wherein the embedded-data elements comprise a collection, the collection comprising a plurality of atomic data elements or structures of data elements.

26. The method of claim 21, wherein the embedded-data elements comprise a structure, the structure having a corresponding column name and comprising one or more subrows of information, the subrows of information each having a row identifier and comprising one or more subcolumns, the subcolumns each having an associated column name and comprising embedded-data elements or atomic data elements.

27. The method of claim 21, wherein accessing the embedded-data column comprises the steps of:

retrieving a row of information from a physical memory storage device in the computer system;

storing the retrieved row of information in a memory device in the computer system;

parsing the retrieved row of information stored in the memory device to determine which columns have data elements; and

creating an in-memory data structure that represents the contents of the retrieved row of information.

28. The method of claim 27 wherein accessing the selected data element comprises traversing the in-memory data structure to access the selected data element in the embedded-data column.

29. The method of claim 21, wherein the database command further comprises a second extension corresponding to a second column name representing a second embedded-data column, the second embedded-data column being embedded within the embedded-data column;

and

wherein the method comprises;

in response to receiving the database command, accessing the table corresponding to the table name,

in response to accessing the table, accessing the embedded-data column represented by the column name in the database command,

in response to accessing the embedded-data column, accessing the second embedded-data column represented by the second column name in the database command, and

in response to accessing the second embedded-data column, accessing the selected data element.

30. The method of claim 21, wherein the database command may comprise an unlimited number of extensions, each representing a more deeply nested embedded-data column.

31. A computer-readable medium having stored thereon computer-executable instructions for performing the method steps of claim 21.

32. A method for storing and accessing a user defined type of data (UDT) in an object-relational database stored in a computer system, the object-relational database comprising one or more tables, the tables each comprising a table name and one or more rows, the rows each comprising one or more embedded data columns, the embedded data columns each having a type name and comprising a plurality of data elements, the method comprising the steps of:

storing a UDT in one or more selected tables, the UDT being stored in an embedded-data column in each of the selected tables, a UDT-name being the type name for the embedded-data column in each of the selected tables;

receiving a database command for accessing a selected data element, the database command comprising at least the UDT name;

in response to receiving the database command, searching every table in the object-relational database to identify the selected tables storing the UDT;

in response to identifying the selected tables, accessing each of the selected tables to identify an associated type name associated with the UDT name;

in each of the selected tables, in response to identifying the associated type name, accessing the embedded-data column corresponding to the UDT name; and

in each of the selected tables, in response to accessing the embedded data column, accessing the selected data element,

whereby a UDT may be stored in selected tables in the object-relational database and subsequently accessed without specifying the table names for the selected tables in the database command.

33. The method of claim 32, wherein the object-relational database further comprises a dictionary;

wherein the dictionary comprises table names and type names; and

wherein the method further comprises the step of, in response to receiving the database command, accessing the dictionary to associate the UDT name with table names.

34. The method of claim 32, wherein the database command comprises a UDT name and one or more selected table names;

and

wherein the method further comprises, in response to receiving the database command, searching only the tables in the object-relational database corresponding to the selected table names.

35. The method of claim 32, wherein accessing the embedded-data column comprises the steps of:

retrieving a row of information from a physical memory storage device in the computer system;

storing the retrieved row of information in a (random access) memory device in the computer system;

parsing the retrieved row of information stored in the (random access) memory device to determine which columns have data elements; and

creating an in-memory data structure that represents the contents of the retrieved row of information.

36. The method of claim 35, wherein accessing the selected data element comprises traversing the in-memory data structure to access the selected data element in the embedded-data column.

37. A computer-readable medium having stored thereon computer-executable instructions for performing the method steps of claim 32.

38. A system for storing and accessing information in an object-relational database, the object-relational database comprising one or more tables, the tables each having a table name and comprising one or more rows of information, the rows of information each comprising one or more columns of data elements, the system comprising:

a memory device for storing a plurality of data elements in a row of information, the row comprising a plurality of columns, the columns each having a column name and comprising at least one of the data elements;

a dictionary comprising table names and column names;

a processor (CPU) for receiving a database command for accessing a selected data element, the database command comprising a selected table name and an extension corresponding to a selected column name, the selected column name corresponding to an embedded-data column, the embedded-data column being one of the columns operative for storing a plurality of the data elements; and

in response to receiving the database command, the processor being operative to;

access the dictionary to associate the selected column name and the selected table name with a corresponding table and a corresponding embedded-data column,

access the corresponding table corresponding to the selected table name,

in response to accessing the corresponding table, accessing the embedded-data column corresponding to the selected column name,

in response to accessing the embedded-data column, accessing the selected data element,

whereby a plurality of data elements may be stored in a single embedded-data column of an object relational database and, by way of an extension to a database command, may subsequently be accessed from the embedded data column as if the embedded-data column were a table.

39. A system for storing and accessing a user defined type of data (UDT) in an object-relational database stored in a computer system, the object-relational database comprising one or more tables, the tables each comprising a table name and one or more rows, the rows each comprising one or more embedded data columns, the embedded data columns each having an column name and comprising a plurality of data elements, the system comprising:

a memory device for storing a UDT in one or more selected tables, the UDT being stored in an embedded-data column in each of the selected tables, a UDT-name being the type name for the embedded-data column in each of the selected tables;

a dictionary comprising type names and table names;

a processor for receiving a database command for accessing a selected data element, the database command comprising at least the UDT name; and

in response to receiving the database command, the processor being operative to;

access the dictionary to identify the selected tables storing the UDT,

in response to identifying the selected tables, access each of the selected tables to identify an associated type name associated with the UDT name,

in each of the selected tables, in response to identifying the associated type name, access the embedded-data column corresponding to the UDT name, and

in each of the selected tables, in response to accessing the embedded data column, access the selected data element,

whereby a UDT may be stored in selected tables in the object-relational database and subsequently accessed without specifying the table names for the selected tables in the database command.