Synchronization of SQL actions in a relational database system

Claim 3

The method of claim 1 wherein said sub-query is a poke sub-query that passes data from a first node to a second node of said one or more common-referencing pairs of nodes to ensure that said first node executes before said second node.

Claim 4

The method of claim 2 wherein said poke sub-query produces a record for consumption by said second node or an input representative thereof.

Claim 5

The method of claim 3 wherein said query graph reforming step (b) further includes inserting a SELECT node before said second node if said second node does not already have an input SELECT node that ranges exclusively over the table T that is commonly referenced by said first and second node.

Claim 6

The method of claim 2 wherein said poke sub-query produces exactly one record for consumption by said second node or an input representative thereof.

Claim 7

The method of claim 1 wherein said nodes {N i } include one or more read-nodes {R k } each representing a read operation on at least one of said tables {T} and one or more write-nodes {W j } each representing a write operation on at least one of said tables {T}, wherein k is a positive integer and wherein said evaluating step (a) comprises the steps of: (a.1) identifying in said query graph G all of said write-nodes {W j } and all of said read-nodes {R k } that represent a read or write operation for which said each table T each is an object.

Claim 8

The method of claim 6 wherein said each node N i has a representative node that receives a flow of records from a subgraph g i that embraces some preceding portion of said graph G such that said representative node for said each node N i is reachable on said data-flow path from any other preceding said node N j representative in said subgraph g i and wherein said query graph reforming step (b) comprises the steps of: (b.1) restricting said data-flow path for each said identified write-node W j which is its own representative node whose subgraph g j includes a node representing any said identified read-node R k , if any, to require execution of said subgraph g j before executing said each identified write-node W j ; (b.2) inserting a poke sub-query node for each said identified write-node W j having a representative node different from W j whose subgraph g j includes a node representing any other said identified read-node R k , if any, to require execution of said any other said identified read-node R k before executing said each identified write-node W j ; (b.3) restricting said data-flow path for each said identified write-node W j which is its own representative node and whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; (b.4) inserting a poke sub-query node for each said identified write-node W j having a representative node different from W j whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; and (b.5) inserting a poke sub-query node for each said identified read-node R k having a representative node whose subgraph g k includes a node representing any said identified write-node W j , if any, to require execution of said any identified write-node W j before executing said each identified read-node R k .

Claim 9

The method of claim 7 further comprising the step of: (e) assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 10

The method of claim 1 further comprising the step of: (e) assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 11

The method of claim 1, wherein said relational database system is a producer-driven system.

Claim 12

A query optimizer system in a relational database processing system having a plurality of base tables {T} for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i, j are positive integers, said system comprising: means for evaluating said query graph G for each said base table T each and identifying common-referencing pairs of said nodes; query graph reforming means for reforming said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of query execution plans for executing said query graph G MTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said query execution plan.

Claim 13

A query optimizer system in a relational database processing system having a plurality of base tables {T} for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i, j are positive integers, said system comprising: means for evaluating said query graph G for each said base table T each and identifying common-referencing pairs of said nodes; query graph reforming means for reforming said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of query execution plans for executing said query graph G MTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said query execution plan.

Claim 14

The query optimizer system of claim 11 wherein said sub-query is a poke sub-query that passes data from a first node to a second node of said one or more common-referencing pairs of nodes to ensure that said first node executes before said second node.

Claim 15

The query optimizer system of claim 12 wherein said poke sub-query produces a record for consumption by said second node or an input representative thereof.

Claim 16

The query optimizer system of claim 13 wherein said query graph reforming means further includes means for inserting a SELECT node before said second node if said second node does not already have an input SELECT node that ranges exclusively over the base table T that is commonly referenced by said first and second node.

Claim 17

The query optimizer system of claim 12, wherein said poke sub-query produces exactly one record for consumption by said second node or an input representative thereof.

Claim 18

The query optimizer system of claim 11 wherein said nodes {N i } include one or more read-nodes {R k } each representing a read operation on at least one of said base tables {T} and one or more write-nodes {W j } each representing a write operation on at least one of said base tables {T}, wherein k is a positive integer and wherein said base table review means comprises: means for identifying in said query graph G all of said write-nodes {W j } and all of said read-nodes {R k } that represent a read or write operation for which said each base table T each is an object.

Claim 19

The query optimizer system of claim 16 wherein said each node N i has a representative node that receives a flow of records from a subgraph g i that embraces some preceding portion of said graph G such that said representative node for said each node N i is reachable on said data-flow path from any other preceding said node N j representative in said subgraph g i and wherein said data-flow restriction means comprises: first read-before-write means for restricting said data-flow path for each said identified write-node W j having a representative node whose subgraph g j includes a node representing any said identified read-node R k , if any, to require execution of said subgraph g j before executing said each identified write-node W j ; second read-before-write means for inserting a poke sub-query node for each said identified write-node W j having a representative node different from W j whose subgraph g j includes a node representing any other said identified read-node R k , if any, to require execution of said any other said identified read-node R k before executing said each identified write-node W j ; first write-before-write means for restricting said data-flow path for each said identified write-node W j which is its own representative node and whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; second write-before-write means for inserting a poke sub-query for each said identified write-node W j having a representative node different from W j whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; and write-before-read means for inserting a poke sub-query node for each said identified read-node R k having a representative node whose subgraph g k includes a node representing any said identified write-node W j , if any, to require execution of said any identified write-node W j before executing said each identified read-node R k .

Claim 20

The query optimizer system of claim 17 wherein said data-flow restriction means further comprises: sequencing means for assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 21

The query optimizer system of claim 11 wherein said query graph reforming means comprises: sequencing means for assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 22

The query optimizer system of claim 11, wherein the relational database system is a producer-driven system.

Claim 23

A database processing system comprising: a data store for storing a plurality of base tables {T}; logical processing means for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i, j are positive integers; means for evaluating said query graph G for each said base table T each to identify common-referencing pairs of said nodes for which said each base table T each is the object; query graph reforming means for reforming said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of query execution plans for executing said query graph G MTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said query execution plan.

Claim 24

A database processing system comprising: a data store for storing a plurality of base tables {T}; logical processing means for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i, j are positive integers; means for evaluating said query graph G for each said base table T each to identify common-referencing pairs of said nodes for which said each base table T each is the object; query graph reforming means for reforming said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of query execution plans for executing said query graph G MTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said query execution plan.

Claim 25

The database processing system of claim 21 wherein said sub-query is a poke sub-query that passes data from a first node to a second node of said one or more common-referencing pairs of nodes to ensure that said first node executes before said second node.

Claim 26

The database processing system of claim 21 wherein said poke sub-query produces one record at a time for consumption by said second node or an input representative thereof.

Claim 27

The database processing system of claim 23 wherein said query graph reforming means further includes means for inserting a SELECT node before said second node if said second node does not already have an input SELECT node that ranges exclusively over the base table T that is commonly referenced by said first and second node.

Claim 28

The database processing system of claim 21 wherein said poke sub-query produces exactly one record for consumption by said second node or an input representative thereof.

Claim 29

The database processing system of claim 21 wherein said nodes {N i } include one or more read-nodes {R k } each representing a read operation on at least one of said base tables {T} and one or more write-nodes {W j } each representing a write operation on at least one of said base tables {T}, wherein k is a positive integer and wherein said base table review means comprises: means for identifying in said query graph G all of said write-nodes {W j } and all of said read-nodes {R k } that represent a read or write operation for which said each base table T each is an object.

Claim 30

The database processing system of claim 26 wherein said each node N i has a representative node that receives a flow of records from a subgraph g i that embraces some preceding portion of said graph G such that said representative node for said each node N i is reachable on said data-flow path from any other preceding said node N j representative in said subgraph g i and wherein said data-flow restriction means comprises: first read-before-write means for restricting said data-flow path for each said identified write-node W j having a representative node whose subgraph g j includes a node representing any said identified read-node R k , if any, to require execution of said subgraph g j before executing said each identified write-node W j ; second read-before-write means for inserting a poke sub-query node for each said identified write-node W j having a representative node different from W j whose subgraph g j includes a node representing any other said identified read-node R k , if any, to require execution of said any other said identified read-node R k before executing said each identified write-node W j ; first write-before-write means for restricting said data-flow path for each said identified write-node W j which is its own representative node and whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; second write-before-write means for inserting a poke sub-query for each said identified write-node W j having a representative node whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; and write-before-read means for inserting a poke sub-query for each said identified read-node R k having a representative node whose subgraph g k includes a node representing any said identified write-node W j , if any, to require execution of said any identified write-node W j before executing said each identified read-node R k .

Claim 31

The database processing system of claim 27 wherein said data-flow restriction means further comprises: sequencing means for assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 32

The database processing system of claim 21 wherein said query graph reforming means comprises: sequencing means for assigning a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 33

The database processing system of claim 21, wherein the logical processing means includes a producer-driven computing system.

Claim 34

A computer program product, for use with a relational database processing system having a stored database including a plurality of base tables {T} for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i and j are positive integers, said computer program product comprising: a recording medium; means, recorded on said recording medium, for causing said system to evaluate said query graph G for each said base table T each to identify common-referencing pairs of said nodes for which said each base table T each is the object; means, recorded on said recording medium, for causing said system to reform said query graph G to reform said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; means, recorded on said recording medium, for causing said system to generate a plurality of plans for executing said query graph G MTI ; and means, recorded on said recording medium, for causing said system to evaluate the execution cost of each said query execution plan and selecting said optimal query execution plan.

Claim 35

A computer program product, for use with a relational database processing system having a stored database including a plurality of base tables {T} for processing queries represented by query graphs {G} wherein each said query graph G includes a plurality of nodes {N i } each representing a relational operation, wherein each said node N i receives from each of one or more other said nodes {N j } a flow of records represented by a directed data-flow arc A ji forming part of a data-flow path and wherein i and j are positive integers, said computer program product comprising: a recording medium; means, recorded on said recording medium, for causing said system to evaluate said query graph G for each said base table T each to identify common-referencing pairs of said nodes for which said each base table T each is the object; means, recorded on said recording medium, for causing said system to reform said query graph G to reform said query graph G by either (i) restricting said data-flow path between the nodes of one or more of said common-referencing pairs of nodes or (ii) inserting a sub-query node between the nodes of one or more of said common-referencing pairs of nodes, or by separately performing both (i) and (ii) on respective ones of said common-referencing pairs of nodes to sequence the execution of each said common-referencing pair of nodes to produce a query graph G MTI that enforces database integrity during table mutation; means, recorded on said recording medium, for causing said system to generate a plurality of plans for executing said query graph G MTI ; and means, recorded on said recording medium, for causing said system to evaluate the execution cost of each said query execution plan and selecting said optimal query execution plan.

Claim 36

The computer program product of claim 31 wherein said sub-query is a poke sub-query that passes data from a first node to a second node of said one or more common-referencing pairs of nodes to ensure that said first node executes before said second node.

Claim 37

The computer program product of claim 32 wherein said poke sub-query produces one record at a time for consumption by said second node or an input representative thereof.

Claim 38

The computer program product of claim 33 wherein said query graph reforming means further includes means, recorded on said recording medium, for directing at least one of said logical processing units to insert a SELECT node before said second node if said second node does not already have an input SELECT node that ranges exclusively over the base table T that is commonly referenced by said first and second node.

Claim 39

The computer program product of claim 32, wherein said poke sub-query produces exactly one record for consumption by said second node or an input representative thereof.

Claim 40

The computer program product of claim 31 wherein said nodes {N i } include one or more read-nodes {R k } each representing a read operation on at least one of said base tables {T} and one or more write-nodes {W j } each representing a write operation on at least one of said base tables {T} and wherein k is a positive integer, said computer program product further comprising: means, recorded on said recording medium, for causing said system identify in said query graph G all of said write-nodes {W j } and all of said read-nodes {R k } that represent a read or write operation for which said each base table T each is an object.

Claim 41

The computer program product of claim 29 wherein said each node N i has a representative node that receives a flow of records from a subgraph g i that embraces some preceding portion of said graph G such that said representative node for said each node N i is reachable on said data-flow path from any other preceding said node N j representative in said subgraph g i , said computer program product further comprising: means, recorded on said recording medium, for causing said system to restrict said data-flow path for each said identified write-node W j having a representative node whose subgraph g j includes a node representing any said identified read-node R k , if any, to require execution of said subgraph g j before executing said each identified write-node W j ; means, recorded on said recording medium, for causing said system to insert a poke sub-query node for each said identified write-node W j having a representative node different from W j whose subgraph g i includes a nose representing any other said identified read-node R k , if any, to require execution of said any other said identifier read-node R k before executing said each identified write-node W j ; means, recorded on said recording medium, for causing said system to restrict said data-flow path for each said identified write-node W j which is its own representative node and whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; means, recorded on said recording medium, for causing said system to insert a poke sub-query node for each said identified write-node W j having a representative node whose subgraph g j includes a node representing any other said identified write-node W i ≠W j , if any, to require execution of said any other said identified write-node W i ≠W j before executing said each identified write-node W j ; and means, recorded on said recording medium, for causing said system to insert a poke sub-query for each said identified read-node R k having a representative node whose subgraph g k includes a node representing any said identified write-node W j , if any, to require execution of said any identified write-node W j before executing said each identified read-node R k .

Claim 42

The computer program product of claim 37 further comprising: means, recorded on said recording medium, for directing at least one of said logical processing units to assign a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 43

The computer program product of claim 31 further comprising: means, recorded on said recording medium, for directing at least one of said logical processing units to assign a SEQUENCE node constraint to a first said node N i receiving a flow of records on at least two said data-flow arcs {A ji } from other said nodes {N j }, wherein said SEQUENCE node constraint forces each of said at least two data-flow arcs {A ji } to complete said flow of records upon initiation before starting said flow of records in another of said at least two data-flow arcs {A ji }.

Claim 44

The computer program product of claim 31, wherein the relational database system is a producer-driven system.