Extending the semantics of the outer join operator for un-nesting queries to a data base
First Claim
1. A method of operating a digital computer 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 method comprising the steps of:
- a) 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) 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.
5 Assignments
0 Petitions
Accused Products
Abstract
The semantics of the outer join operator are extended to permit the application of different predicates to the join tuples and the anti-join tuples. For un-nesting of nested query blocks, the anti-join tuples, for example, are associated with a count value of zero instead of a count value of null. An inner query block is un-nested from an outer query block by converting the inner query to a first un-nested query generating a temporary relation and converting the outer query block to a second un-nested query receiving the precomputed temporary relation. When the nested inner query has an equi-join predicate joining a relation of the inner query to an outer query and a count aggregate, the query blocks are un-nested by removing the equi-join predicate from the inner query and placing a corresponding conjunctive (left) outerjoin predicate term in the predicate of the outer query, performing the count aggregate for each distinct value of the joining attribute of the relation of the inner query, and in the outer query applying different predicates to the joining and anti-joining tuples such that the predicate of the anti-joining tuples is evaluated assuming a count value of zero.
474 Citations
20 Claims
-
1. A method of operating a digital computer 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 method comprising the steps of:
-
a) 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) 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of operating a digital computer for executing an outer query including a nested inner 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 method comprising the steps of:
-
a) computing a third relation including values of said second relation by counting over groups of distinct values of said second relation to compute a count for each distinct value of said second relation; and b) applying said first predicate to combinations of values of said first relation and the distinct values of said second relation, and for combinations of values of said first relation and distinct values of said second relation which satisfy said first predicate, applying said second predicate to said first relation and the count of said third relation for each distinct value of said second relation, and for values of said first relation for which said first predicate is not satisfied in combination with any of said distinct values of said second relation, applying said second predicate to said first relation and a value of zero. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
-
-
18. 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. - View Dependent Claims (19, 20)
-
Specification