Extending the semantics of the outer join operator for un-nesting queries to a data base

Claim 3

The method as claimed in claim 1, wherein said inner query and said outer query are expressed in a query language including alphanumeric names for said first and second relations and alphanumeric symbols for operators in said first and second predicates.

Claim 4

The method as claimed in claim 2, wherein said inner query includes a select statement including the words "SELECT" and "COUNT" and said first predicate is included in a where statement including the word "WHERE".

Claim 5

The method as claimed in claim 2, further comprising the step of parsing said inner and outer query to form a linked data structure including a first node representing said inner query and a second node representing said outer query.

Claim 6

The method as claimed in claim 4, wherein said steps of converting generate another linked data structure including a third node defining said first un-nested query and a fourth node defining said second un-nested query.

Claim 7

The method as claimed in claim 5, wherein said another linked data structure includes a series of nodes defining a sequence of join and outer-join operations including a consecutive series of m joins, and wherein the first i joins are evaluated at a time first for i=1, then for i=2, then for i=3, . . . , and finally for i=m.

Claim 8

The method as claimed in claim 6, wherein said evaluating generates a respective linked data structure for each value of i representing an alternative query plan.

Claim 9

The method as claimed in claim 4, wherein said linked data structure is hierarchical and includes a multiplicity of nodes descendant from a root node, and said steps of converting are performed upon parent-child pairs of nodes when the child nodes are leaf nodes in said linked data structure.

Claim 10

The method as claimed in claim 1, further comprising the step of executing said second un-nested query by indexing said results of said first un-nested query with a first index and indexing values of said first relation with a second index, and for each value of said first relation that is indexed by said second index, sequencing said first index and iteratively testing said first predicate with said each value of said first relation and one of said results indexed by said first index, and when said testing finds that said first predicate is true, testing said second predicate with said each value of said first relation and the indexed one of said results and terminating said testing of said first predicate with said each value of said first relation, and when said testing has tested said first predicate for said each value of said first relation and all of said results without ever finding that said first predicate is true, applying said second predicate to said each value of said first relation and a value of zero.

Claim 13

The method as claimed in claim 10, wherein said inner query and said outer query are expressed in a query language including alphanumeric names for said first and second relations and alphanumeric symbols for operators in said first and second predicates.

Claim 14

The method as claimed in claim 11, wherein said inner query includes a select statement including the words "SELECT" and "COUNT", and said first predicate is included in a where statement including the word "WHERE".

Claim 15

The method as claimed in claim 11, further comprising the step of parsing said inner and outer query to form a linked data structure including a first node representing said inner query and a second node representing said outer query.

Claim 16

The method as claimed in claim 13, further comprising the step of converting said linked data structure into another linked data structure including a third node defining a first un-nested query for generating said third relation and a fourth node defining a second un-nested query for receiving said third relation, and wherein said step (a) of computing is performed by executing said first un-nested query and said step (b) of applying is performed by executing said second un-nested query.

Claim 17

The method as claimed in claim 14, wherein said another linked data structure includes a series of nodes defining a sequence of join and outer-join operations including a consecutive series of m joins, and wherein the first i joins are evaluated at a time first for i=1, then for i=2, then for i=3, . . . , and finally for i=m.

Claim 18

The method as claimed in claim 14, wherein said linked data structure formed by said parsing is hierarchical and includes a multiplicity of nodes descendant from a root node, and said step of converting is performed upon parent-child pairs of nodes when the child nodes are leaf nodes in said linked data structure formed by said parsing.

Claim 19

The method as claimed in claim 10, wherein said step (b) of applying includes indexing said third relation with a first index and indexing all values of said first relation with a second index, and for each value of said first relation, sequencing said first index and iteratively testing said first predicate with said each value of said first relation and one of said values of said second relation indexed by said first index, and when said testing finds that said first predicate is true, testing said second predicate with said each value of said first relation and the count for the indexed one of said values of said second relation and terminating said testing of said first predicate with said each value of said first relation, and when said testing has tested said first predicate for said each value of said first relation and all of said values of said second relation from said third relation without ever finding that said first predicate is true, applying said second predicate to said each value of said first relation and a value of zero.

Claim 20

A database system comprising, in combination: a memory having stored in it a relational database; an input device for receiving a query from a user requesting data from said relational database; an output device for transmitting to the user data from said relational database; and a query processing system including means for parsing said query to generate a query graph in said memory representing said query, means for generating an optimized query from said query graph; and means for executing said optimized query; wherein said means for generating an optimized query includes means for un-nesting an inner query from an outer query, said inner query referencing a first relation also referenced in said outer query, said inner query including a first predicate joining said first relation to a second relation, said inner query also including a count aggregate, said outer query having a second predicate referencing said first relation and said inner query, said means for generating including: a) means for converting said inner query to a first un-nested query by removing said first predicate and modifying said count aggregate function to count over groups of distinct values of said second relation; and b) means for converting said outer query to a second un-nested query receiving results of said inner query by modifying said second predicate so that said second predicate is applied to said first relation and said results for values of said first relation which are joined to said results by said first predicate and so that said second predicate is applied to said first relation and a value of zero for values of said first relation which are not joined to any of said results by said first predicate.

Claim 21

A database system comprising, in combination: a memory having stored in it a relational database; an input device for receiving a query from a user requesting data from said relational database; an output device for transmitting to the user data from said relational database; and a query processing system including means for parsing said query to generate a query graph in said memory representing said query, means for generating an optimized query from said query graph; and means for executing said optimized query; wherein said means for generating an optimized query includes means for un-nesting an inner query from an outer query, said inner query referencing a first relation also referenced in said outer query, said inner query including a first predicate joining said first relation to a second relation, said inner query also including a count aggregate, said outer query having a second predicate referencing said first relation and said inner query, said means for generating including: a) means for converting said inner query to a first un-nested query by removing said first predicate and modifying said count aggregate function to count over groups of distinct values of said second relation; and b) means for converting said outer query to a second un-nested query receiving results of said inner query by modifying said second predicate so that said second predicate is applied to said first relation and said results for values of said first relation which are joined to said results by said first predicate and so that said second predicate is applied to said first relation and a value of zero for values of said first relation which are not joined to any of said results by said first predicate.

Claim 22

The relational database system as claimed in claim 18, wherein said means for executing said optimized query includes means for executing said second un-nested query by indexing said results of said first un-nested query with a first index and indexing all values of said first relation with a second index, and for each value of said first relation that is indexed by said second index, sequencing said first index and iteratively testing said first predicate with said each value of said first relation and one of said results indexed by said first index, and when said testing finds that said first predicate is true, testing said second predicate with said each value of said first relation and the indexed one of said results and terminating said testing of said first predicate with said each value of said first relation, and when said testing has tested said first predicate for said each value of said first relation and all of said results without ever finding that said first predicate is true, applying said second predicate to said each value of said first relation and a value of zero.

Claim 23

The method as claimed in claim 18, wherein said means for parsing includes means for parsing a series of a multiplicity of nested queries to generate a query graph including a multiplicity of linked nodes, said means for un-nesting includes means for generating another query graph including a series of a multiplicity of linked nodes representing un-nested queries each having either a join or an outer-join operation and together defining a sequence of join and outer-join operations including a consecutive series of m joins, and wherein said means for optimizing further includes means for generating a plurality of alternative query graphs by evaluating the first i joins at a time first for i=1, then for i=2, then for i=3, . . . , and finally for i=m.