Enumerating projections in SQL queries containing outer and full outer joins in the presence of inner joins

• US 5,855,019 A
• Filed: 07/31/1997
• Issued: 12/29/1998
• Est. Priority Date: 01/30/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bhargava, Gautam, Iyer, Balakrishna Raghavendra, Goel, Piyush
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/904,172
• Time in Patent Office: 516 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

The present invention discloses a method and apparatus for the enumeration of projections (i.e., "SELECT DISTINCT" operations) in SQL queries containing outer and full outer joins in the presence of inner joins without encountering any regression in performance. The present invention removes projections from a given user query by moving the projections to the top of an expression tree representation of the query, wherein the projection removal is performed using algebraic identities rather than rule-based transformations. The present invention also discloses several methods of enumerating different plans or schedules for projection operations and binary operations in the given user query. The present invention can significantly reduce the execution time of a query by selecting the optimal schedule for binary operations and projections between the binary operations. However, the present invention ensures that there is no regression in performance by comparing the cost of the query with the cost of enumerated plans or schedules, thereby ensuring that the optimizations or transformations do not introduce performance penalties.

Claims

1. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

2. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

3. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y,E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

4. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

5. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

6. A method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) applying an identity to the query, wherein the identity comprises;

##EQU5## and wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

p_xy is a predicate,

sch(p_xy) is a schema of p_xy,

(sch(p_xy)∩

R_X).OR right.X₁,

(sch(p_xy)∩

R_Y).OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

7. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

8. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

9. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

10. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

11. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

12. An apparatus for simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the apparatus comprising:

(a) a computer;

(b) means for accepting the query into the computer; and

(c) means for applying an identity to the query, wherein the identity comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

.sup.p.sbsp.xy e.sub.y)=δ

.sub.X.sbsb.1 (e.sub.x).sub.⊙

.sup.p.sbsp.xy δ

.sub.Y.sbsb.1 (e.sub.y)

and wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

p_xy is a predicate,

sch(p_xy) is a schema of p_xy,

(sch(p_xy)∩

R_X).OR right.X₁,

(sch(p_xy)∩

R_Y).OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

13. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

14. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.2 δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.2 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y, and Y₂ .OR right.Y₁,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

15. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.1.sub.Y.sbsb.1 δ

.sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

16. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

π

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

17. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) replacing a first expression in the query with a second expression, wherein the first expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2 δ

.sub.X.sbsb.1 (e.sub.x)⊙

δ

.sub.Y.sbsb.1 (e.sub.y)

and the second expression comprises;

space="preserve" listing-type="equation">π

.sub.X.sbsb.2.sub.Y.sbsb.1 δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

e.sub.Y)

wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X, and X₂ .OR right.X₁,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

π

_X (r) is a projection operation of relation r onto attributes X,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.

18. An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query in a computer, the query being performed by the computer to retrieve data from a database stored in a electronic storage device coupled to the computer, the method comprising the steps of:

(a) accepting the query into the computer; and

(b) applying an identity to the query, wherein the identity comprises;

space="preserve" listing-type="equation">δ

.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x ⊙

.sup.p.sbsp.xy e.sub.y)=δ

.sub.X.sbsb.1 (e.sub.x).sub.⊙

.sup.p.sbsp.xy δ

.sub.Y.sbsb.1 (e.sub.y)

and wherein;

e_X =(R_X, V_X, E_X) is a relation, where R_X is a non-empty set of real attributes, V_X is a non-empty set of virtual attributes, E_X, an extension of the relation, also denoted as ext(e_X), is a set of tuples, and X₁ .OR right.R_X,

e_Y =(R_Y, V_Y, E_Y) is a relation, where R_Y is a non-empty set of real attributes, V_Y is a non-empty set of virtual attributes, E_Y, an extension of the relation, also denoted as ext(e_Y), is a set of tuples, and Y₁ .OR right.R_Y,

p_xy is a predicate,

sch(p_xy) is a schema of p_xy,

(sch(p_xy)∩

R_X).OR right.X₁,

(sch(p_xy)∩

R_Y).OR right.Y₁,

δ

_X (r) is a distinct projection operation of relation r onto attributes X, and

⊙

ε

{, ←

, →

, ←

→

}, wherein represents a join operation, ←

→

represents a full outer join operation, ←

represents a left outer join operation, and →

represents a right outer join operation.