Relational database management system and method for storing, retrieving and modifying directed graph data structures

• US 5,201,046 A
• Filed: 06/22/1990
• Issued: 04/06/1993
• Est. Priority Date: 06/22/1990
• Status: Expired due to Term

• Current Assignee: Xidak Incorporated
• Original Assignee: Xidak Incorporated
• Inventors: Jirak, Gregory A., Goldberg, Robert N.
• Primary Examiner(s): Clark, David L.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US07/542,163
• Time in Patent Office: 1,019 Days
• Field of Search: 364/200, 364/300, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An improved database management system (DBMS) stores, retrieves and manipulates directed graph data structures in a relational database. Each directed graph data structure contains one or more records of data which are interconnected by pointers. Data is stored in the database in the form of two dimensional tables, also known as flat files. The improved DBMS defines a schema for each table in the database. The schema defines the name and data type of each column in a database table. In tables used to store directed graph data structures, at least one column will be defined as having a reference data type. Non-empty entries in that column are pointers to rows in a specified table. Directed graph data structures are stored in specified tables by storing each record of the directed graph in a distinct row of one of the specified tables, with references corresponding to interconnections between records being stored in reference data type columns. Portions of a directed graph are retrieved from the specified table, in accordance with a single specified query and then the query is automatically expanded by also retrieving additional portions of the tables which are referenced by the previously retrieved portions, thereby performing a transitive closure. The retrieved data is stored in a buffer as a list of rows, and then communicated to an application process. An interface program converts the list of rows stored in the buffer into a directed graph data structure.

Claims

1. A computer system for storing, retrieving and modifying data stored in a database, comprising:

a database server; and

a multiplicity of application processes coupled to said database server, each application process including;

an application program that utilizes directed graph data structures in a corresponding application specific data format;

each said directed graph data structure including one or more records of data interconnected by pointers, each record composed of one or more data elements having respective specified data types;

an application interface that translates directed graph data structures in said application specific data format into a predefined intermediate data format and translates directed graph data structures in said predefined intermediate data a format into said application specific data format; and

query generating means for generating and sending queries to said database server for storing, retrieving and updating specified directed graph data structures in said database;

said database server including;

schema defining means for defining a distinct schema for each of a plurality of tables in said database, each said database table having a plurality of rows and a specified number of columns, wherein each row of said table stores data values in each of said columns of said table;

said schema denoting a data type for each column of data values stored in said table, each denoted data type being selected from a set of predefined data types including a reference data type;

each non-empty data value stored in a reference data type column comprising a reference to a row of one of said tables in said database; and

directed graph storage means for storing and retrieving specified directed graph data structures in and from specified tables in said database in accordance with queries received from said application processes;

said directed graph storage means including;

graph storing means for receiving a data storage query that includes a specified directed graph data structure in said predefined intermediate data format and for storing each record of said received directed graph data structure in a distinct row of a respective one of said tables in said database, said graph storing means including means for storing said data elements of said each record in corresponding columns of said one respective table and means for storing references, each reference corresponding to one of said pointers that interconnect said each record to other records of said specified directed graph data structure, in corresponding ones of said reference data type columns of said one respective table; and

directed graph retrieving means for retrieving a specified directed graph data structure from said database in accordance with a single specified query received from one of said application processes, including means for retrieving in accordance with said specified query at least one specified row from at least one respective table in said database and then retrieving additional rows of data from respective tables in said database, said additional rows of data comprising rows of data that are referenced by references in other rows of data retrieved in accordance with said specified query, for converting said retrieved rows of data into a directed graph data structure in said predefined intermediate data format, and for transmitting said retrieved directed graph data structure to said one application process;

whereby a directed graph data structure having multiple records is retrieved by said database server in response to a single query from said one application process.

2. A computer system as in claim 1,

said schema defining means denoting in each said schema a table identifier for each reference data type column, said table identifier specifying which database table is referenced by references in that column;

each said table in said database having an associated primary key comprising an ordered list of columns of said table whose values identify a particular row of said table; and

each of said references comprising a primary key value of a row in the respective database table specified by the schema for the table in which each said reference is stored.

3. A computer system as in claim 1, wherein each directed graph data structure in said intermediate data format includes rows of data values, each row of data values corresponding to a respective record of a corresponding directed graph data structure in one said application specific data format, said rows of data values including row pointers interconnecting said rows of data values, each row pointer corresponding to a respective pointer in said corresponding directed graph data structure in one said application specific data format.

4. A computer system as in claim 1,

said query generating means including means for including in said generated queries specified criteria for limiting retrieval of said additional rows of data.

5. A computer system as in claim 1,

said query generating means including means for including retrieval limiting criteria in ones of said generated queries, said retrieval limiting criteria denoting a maximum depth, said maximum depth comprising a maximum number of pointers used in sequence to interconnect one or more top-level records of said specified directed graph data structure with other records of said specified directed graph data structure;

and

said directed graph retrieving means including means for limiting retrieval of said additional rows of data, when retrieving a specified directed graph data structure in accordance with a query including retrieval limiting criteria, to those of said additional rows of data that are connected to said specified at least one row of data by a sequence of references no greater in number than said maximum number denoted by said retrieval limiting criteria.

6. A computer system for storing, retrieving and modifying data stored in a database, comprising:

a database server;

a multiplicity of application processes coupled to said database server, each application process including;

an application program that utilizes directed graph data structures in a corresponding application specific data format;

each said directed graph data structure including one or more records of data interconnected by pointers, each record composed of one or more data elements having respective specified data types;

query generating means for sending queries to said database server for storing, retrieving said updating specified directed graph structures in said database; and

at least one application interface that translates directed graph data structures in one respective application specific data format into a predefined intermediate data format and translates directed graph data structures in said predefined intermediate data format into said one respective application specific data format;

said at least one application interface coupling said database server to a respective at least one of said application processes;

said database server including;

schema defining means for defining a distinct schema for each of a plurality of tables in said database, each said database table having a plurality of rows and a specified number of columns, wherein each row of said table stores data values in each of said columns of said table;

said schema denoting a data type for each column of data values stored in said table, each denoted data type being selected from a set of predefined data types including a reference data type;

each non-empty data value stored in a reference data type column comprising a reference to a row of one of said tables in said database; and

directed graph storage means for storing and retrieving specified directed graph data structures in and from specified tables in said database in accordance with queries received from said application processes;

said directed graph storage means including;

graph storing means for receiving a data storage query that includes a specified directed graph data structure in said predefined intermediate data format and for storing each record of said received directed graph data structure in a distinct row of a respective one of said tables in said database, said graph storing means including means for storing said data elements of said each record in corresponding columns of said one respective table and means for storing references, each reference corresponding to one of said pointers that interconnect said each record to other records of said specified directed graph data structure, in corresponding ones of said reference data type columns of said one respective table; and

directed graph retrieving means for retrieving a specified directed graph from said database in accordance with a single specified query received from one of said application processes, including means for retrieving in accordance with said specified query at least one specified row from at least one respective table in said database and then retrieving additional rows of data from respective tables in said database, said additional rows of data comprising rows of data that are referenced by references in other rows of data retrieved in accordance with said specified query, for converting said retrieved rows of data into a directed graph data structure in said predefined intermediate data a format, and for transmitting said retrieved directed graph data structure to said one application process;

whereby a directed graph having multiple records is retrieved by said database server in response to a signal query from said one application process.

7. A computer system as in claim 6,

said schema defining means denoting in each said schema a table identifier for each reference data type column, said table identifier specifying which database table is referenced by references in that column;

each said table in said database having an associated primary key comprising an ordered list of columns of said table whose values identify a particular row of said table; and

each of said references comprising a primary key value of a row in the respective database table specified by the schema for the table in which each said reference is stored.

8. A computer system as in claim 6, wherein each directed graph data structure in said intermediate data format includes rows of data values, each row of data values corresponding to a respective record of a corresponding directed graph data structure in one said application specific data format, said rows of data values including row pointers interconnecting said rows of data values, each row pointer corresponding to a respective pointer in said corresponding directed graph data structure in one said application specific data format.

9. A computer system as in claim 6,

said query generating means including means for including in said generated queries specified criteria for limiting retrieval of said additional rows of data.

10. A computer system as in claim 6,

said query generating means including means for including retrieval limiting criteria in ones of said generated queries, said retrieval limiting criteria denoting a maximum depth, said maximum depth comprising a maximum number of pointers used in sequence to interconnect one or more top-level records of said specified directed graph data structure with other records of said specified directed graph data structure;

and

said directed graph retrieving means including means for limiting retrieval of said additional rows of data, when retrieving a specified directed graph data structure in accordance with a query including retrieval limiting criteria, to those of said additional rows of data that are connected to said specified at least one row of data by a sequence of references no greater in number than said maximum number denoted by said retrieval limiting criteria.

11. In a computer system, a control process of storing and retrieving directed graph data structures in a data table in a computer system;

said computer system having a multiplicity of application processes coupled to a database server that responds to queries from said application processes by storing, retrieving and updating data in said database;

the steps of the control process comprising;

in each application process, executing an application program that utilizes directed graph data structures in a corresponding application specified data format;

each said directed graph data structure including one or more records of data interconnected by pointers, each record composed of one or more data elements having respective specified data types;

each application process generating and sending queries to said database reserver for storing, retrieving and updating specified directed graph structures in said database;

when transmitting directed graph data structures from any one of said application processes to said database server, translating said transmitted directed graph data structures from the application specific data format utilized by said one of said application processes into a predefined intermediate data format,

when transmitting directed graph data structures from said database server to any one of said application processes, translating said transmitted directed graph data structures from said predefined intermediate data format into the application specific data format utilized by said one of said application processes;

in said database server, defining a distinct schema for each of a plurality of tables in said database, each said database table having a plurality of rows and a specified number of columns, wherein each row of said database table stores data values in each of said columns of said database table;

said schema denoting a data type for each column of data values stored in said database table, each denoted data type being selected from a set of predefined data types including a reference data type;

type;

each non-empty data value stored in a reference data type column comprising a reference to a row of one of said tables in said database;

in said database server, storing and retrieving specified directed graph data structures in and from specified tables in said database in accordance with queries received from one of said application processes;

said storing and retrieving steps including;

receiving from one of said application processes a data storage query that includes a specified directed graph data structure in said predefined intermediate data format, and storing each record of said received directed graph data structure in a distinct row of a respective one of said database tables, said record storing step including storing said data elements of said each record in corresponding columns of said one respective database table and storing references, each reference corresponding to one of said pointers that interconnect said each record to other records of said specified directed graph data structure, in corresponding ones of said reference data type columns of said one respective database table; and

retrieving a specified directed graph data structure from said database in accordance with a single specified query received from one of said application processes, including retrieving in accordance with said specified query at least one specified row from at least one respective database table and then retrieving additional rows of data from respective ones of said database tables, said additional rows of data comprising rows of data that are referenced by references in other rows of data retrieved in accordance with said specified query, converting said retrieved rows of data into a directed graph data structure in said predefined intermediate data format, and transmitting said retrieved directed graph data structure to said one application process.

12. The control process of claim 11,

said schema defining step including denoting in each said schema a table identifier for each reference data type column, said table identifier specifying which database table is referenced by references in that column;

each said table in said database having an associated primary key comprising an ordered list of columns of said table whose values identify a particular row of said table; and

each of said references comprising a primary key value of a row in the respective database table specified by the schema for the table in which each said reference is stored.

13. The control process of claim 11, wherein each directed graph data structure in said intermediate data format includes rows of data values, each row of data values corresponding to a respective record of a corresponding directed graph data structure in the application specific data format utilized by one of said application processes, said rows of data values including row pointers interconnecting said rows of data values, each row pointer corresponding to a respective pointer in said corresponding directed graph data structure in said application specific data format.

14. The control process of claim 11,

said query generating step including the step of including in ones of said generated queries specified criteria for limiting retrieval of said additional rows of data.

15. The control process of claim 11,

said query generating means including means for including retrieval limiting criteria in ones of said generated queries, said retrieval limiting criteria denoting a maximum depth, said maximum depth comprising a maximum number of pointers used in sequence to interconnect one or more top-level records of said specified directed graph data structure with other records of said specified directed graph data structure;

and

said step of retrieving a specified directed graph data structure including limiting retrieval of said additional rows of data, when retrieving a specified directed graph data structure in accordance with a query including retrieval limiting criteria, to those of said additional rows of data that are connected to said specified at least one row of data by a sequence of references no greater in number than said maximum number denoted by said retrieval limiting criteria.