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

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.2 .delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.2 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, Y.sub.1 .OR right.R.sub.Y, and Y.sub.2 .OR right.Y.sub.1,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.1.sub.Y.sbsb.1 .delta..sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.y)
• wherein:
• e.sub.X =(R.sub.X V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y,E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.X .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• p.sub.xy is a predicate,
• sch(p.sub.xy) is a schema of p.sub.xy,
• (sch(p.sub.xy).andgate.R.sub.X).OR right.X.sub.1,
• (sch(p.sub.xy).andgate.R.sub.Y).OR right.Y.sub.1,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, Y.sub.1 .OR right.R.sub.Y, and Y.sub.2 .OR right.Y.sub.1,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.2 .delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.2 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, Y.sub.1 .OR right.R.sub.Y, and Y.sub.2 .OR right.Y.sub.1,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.1.sub.Y.sbsb.1 .delta..sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot..sup.p.sbsp.xy e.sub.y)=.delta..sub.X.sbsb.1 (e.sub.x).sub..circle-w/dot..sup.p.sbsp.xy .delta..sub.Y.sbsb.1 (e.sub.y)
• and wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• p.sub.xy is a predicate,
• sch(p.sub.xy) is a schema of p.sub.xy,
• (sch(p.sub.xy).andgate.R.sub.X).OR right.X.sub.1,
• (sch(p.sub.xy).andgate.R.sub.Y).OR right.Y.sub.1,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y, and Y.sub.2 .OR right.Y.sub.1,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.2 .delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.2 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y, and Y.sub.2 .OR right.Y.sub.1,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.1.sub.Y.sbsb.1 .delta..sub.V.sbsb.x.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..pi..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.V.sbsb.y.sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .pi..sub.X.sbsb.2 .delta..sub.X.sbsb.1 (e.sub.x).circle-w/dot..delta..sub.Y.sbsb.1 (e.sub.y)
• and the second expression comprises:
• .pi..sub.X.sbsb.2.sub.Y.sbsb.1 .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot.e.sub.Y)
• wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X, and X.sub.2 .OR right.X.sub.1,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• .pi..sub.X (r) is a projection operation of relation r onto attributes X,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.

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:
• .delta..sub.X.sbsb.1.sub.Y.sbsb.1 (e.sub.x .circle-w/dot..sup.p.sbsp.xy e.sub.y)=.delta..sub.X.sbsb.1 (e.sub.x).sub..circle-w/dot..sup.p.sbsp.xy .delta..sub.Y.sbsb.1 (e.sub.y)
• and wherein:
• e.sub.X =(R.sub.X, V.sub.X, E.sub.X) is a relation, where R.sub.X is a non-empty set of real attributes, V.sub.X is a non-empty set of virtual attributes, E.sub.X, an extension of the relation, also denoted as ext(e.sub.X), is a set of tuples, and X.sub.1 .OR right.R.sub.X,
• e.sub.Y =(R.sub.Y, V.sub.Y, E.sub.Y) is a relation, where R.sub.Y is a non-empty set of real attributes, V.sub.Y is a non-empty set of virtual attributes, E.sub.Y, an extension of the relation, also denoted as ext(e.sub.Y), is a set of tuples, and Y.sub.1 .OR right.R.sub.Y,
• p.sub.xy is a predicate,
• sch(p.sub.xy) is a schema of p.sub.xy,
• (sch(p.sub.xy).andgate.R.sub.X).OR right.X.sub.1,
• (sch(p.sub.xy).andgate.R.sub.Y).OR right.Y.sub.1,
• .delta..sub.X (r) is a distinct projection operation of relation r onto attributes X, and
• .circle-w/dot..epsilon.{, .rarw., .fwdarw., .rarw..fwdarw.}, wherein represents a join operation, .rarw..fwdarw. represents a full outer join operation, .rarw. represents a left outer join operation, and .fwdarw. represents a right outer join operation.