Queries Involving More Than One Relation

Queries Involving More Than One Relation

  • Introduction to combining two or more relations in SQL using operations like joins, products, unions, intersections, and differences.
  • Focus on how the select-from-where statement in SQL facilitates products and joins.
#1

read: Section 6.2: Queries Involving More Than One Relation (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Introduction to combining two or more relations in SQL using operations like joins, products, unions, intersections, and differences.
- Focus on how the select-from-where statement in SQL facilitates products and joins.

Much of the power of relational algebra stems from its capacity to combine relations through operations like joins, products, unions, intersections, and differences. SQL provides mechanisms for all of these operations. The set-theoretic operations—union, intersection, and difference—are available directly. The SELECT-FROM-WHERE statement is the primary construct for performing products and joins.

  • Products and Joins in SQL

    SQL creates a product of relations by listing them in the FROM clause. This operation conceptually forms the Cartesian product of the tuples from all listed relations. The WHERE clause then filters this product by applying conditions, which typically include both selection criteria and join conditions that link tuples from different relations.

    SELECT name
FROM Movies, MovieExec
WHERE title = 'Star Wars' AND Movies.producerC# = MovieExec.cert#;
Definition: Semantics of a Multirelation Query

An SQL query of the form:

SELECT A1, A2, ..., Ak
FROM R1, R2, ..., Rn
WHERE C;

is defined by the following relational algebra expression: \[ \pi_{A_1, A_2, \dots, A_k} (\sigma_C (R_1 \times R_2 \times \dots \times R_n)) \] Where: - \(R_1, R_2, \dots, R_n\) are the relations in the FROM clause. - \(\times\) is the Cartesian product operator. - \(\sigma_C\) is the selection operator with a condition \(C\) derived from the WHERE clause. - \(\pi_{A_1, \dots, A_k}\) is the projection operator for the attributes listed in the SELECT clause.

  • Disambiguating Attributes

    If two or more relations in the FROM clause share an attribute name, any reference to that attribute is ambiguous. To resolve this, SQL requires that the attribute name be prefixed with its relation name, using a dot as a separator (Relation.Attribute).

    SELECT MovieStar.name, MovieExec.name
FROM MovieStar, MovieExec
WHERE MovieStar.address = MovieExec.address;

  • Tuple Variables for Self-Joins

    A query may need to involve two or more tuples from the same relation simultaneously, as in a self-join. SQL handles this by allowing a relation in the FROM clause to be given an alias, which is referred to as a “tuple variable.” This permits distinct references to different tuples of the same relation within the query.

    SELECT Star1.name, Star2.name
FROM MovieStar Star1, MovieStar Star2
WHERE Star1.address = Star2.address AND Star1.name < Star2.name;

  • Set-Theoretic Operations

    SQL provides direct operators for the set operations of union, intersection, and difference, which are applied to the results of two queries. The relations resulting from these queries must be “union-compatible,” meaning they have the same number of attributes and the types of corresponding attributes are compatible.
    • UNION: Combines the results of two queries, forming their set union.
    • INTERSECT: Returns only the tuples that appear in the results of both queries.
    • EXCEPT: Returns tuples from the first query’s result that do not appear in the second’s.
    (SELECT name, address FROM MovieStar)
EXCEPT
(SELECT name, address FROM MovieExec);
  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:52:55
  • Duration: 30.410102128982544
  • Cummulative cost: $3.63e-02

Products and Joins in SQL

  • SQL’s method for coupling relations by listing them in the FROM clause.
  • The ability of SELECT and WHERE clauses to reference attributes from any relation listed in the FROM clause.
  • Using conditions in the WHERE clause to join tuples from different relations based on matching attribute values.
#2

read: Section 6.2.1: Products and Joins in SQL (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- SQL's method for coupling relations by listing them in the `FROM` clause.
- The ability of `SELECT` and `WHERE` clauses to reference attributes from any relation listed in the `FROM` clause.
- Using conditions in the `WHERE` clause to join tuples from different relations based on matching attribute values.

Products and Joins in SQL

In SQL, queries involving more than one relation are constructed by specifying multiple relations in the FROM clause. This structure provides a straightforward method for performing Cartesian products and, more commonly, joins. The semantics of such a query can be understood as first forming a product of all relations listed, then filtering the result based on conditions in the WHERE clause, and finally projecting the attributes specified in the SELECT clause.

Definition: Semantics of Multi-Relation Queries

A SQL query of the form:

SELECT A_1, A_2, ..., A_k
FROM R_1, R_2, ..., R_n
WHERE C;

is equivalent to the relational algebra expression: \[ \pi_{A_1, A_2, ..., A_k}(\sigma_C(R_1 \times R_2 \times \dots \times R_n)) \] where: - \(R_1, R_2, \dots, R_n\) are the relations listed in the FROM clause. - \(\times\) denotes the Cartesian product. - \(\sigma_C\) is the selection operation with the condition \(C\) from the WHERE clause. - \(\pi_{A_1, ..., A_k}\) is the projection operation on the attributes \(A_1, \dots, A_k\) from the SELECT list.

  • Coupling Relations

    Relations are coupled by listing them in the FROM clause, separated by commas. This operation conceptually generates the Cartesian product of the specified relations, creating a new, wider relation containing all possible combinations of tuples, one from each relation.

  • Attribute Referencing

    The SELECT and WHERE clauses can refer to any attribute of any relation listed in the FROM clause. If an attribute name is unique across all listed relations, it can be used directly. If the name is ambiguous (i.e., appears in more than one relation), it must be disambiguated by prefixing it with the relation name (e.g., Movies.title).

  • Join and Selection Conditions

    The WHERE clause is used to specify conditions that filter the tuples from the Cartesian product. This clause typically contains both selection conditions (e.g., title = 'Star Wars') and join conditions (e.g., producerC# = cert#). The join condition links tuples from different relations based on matching values in common attributes, effectively turning the Cartesian product into a meaningful join. For instance, to find the producer of Star Wars:

    SELECT name
FROM Movies, MovieExec
WHERE title = 'Star Wars' AND producerC# = cert#;

    Here, the condition producerC# = cert# ensures that a tuple from Movies is paired only with the corresponding tuple from MovieExec.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:53:18
  • Duration: 22.394252061843872
  • Cummulative cost: $2.25e-02

Disambiguating Attributes

  • Addressing the ambiguity that arises when multiple relations in a query share attribute names.
  • The SQL solution of prefixing an attribute with its relation name and a dot, such as Relation.Attribute.
#3

read: Section 6.2.2: Disambiguating Attributes (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Addressing the ambiguity that arises when multiple relations in a query share attribute names.
- The SQL solution of prefixing an attribute with its relation name and a dot, such as `Relation.Attribute`.

When formulating queries that involve several relations, an ambiguity may arise if two or more of these relations possess attributes with the same name. SQL provides a mechanism to resolve such conflicts.

Definition: Attribute Disambiguation

Let a query involve relations \(R_1, R_2, \dots, R_n\). If an attribute name \(A\) is present in more than one relation \(R_i\) and \(R_j\) (where \(i \neq j\)), a reference to \(A\) is ambiguous. SQL resolves this by allowing an attribute to be fully qualified by prefixing it with its relation name, using the notation R.A. This refers specifically to the attribute A of relation `R$.

  • The Source of Ambiguity

    When a query’s FROM clause lists multiple relations, the set of available attributes is the union of the attributes from all listed relations. If an attribute name appears in more than one of these relations, any unqualified reference to that name in the SELECT or WHERE clauses is ambiguous.

  • The SQL Solution: Dot Notation

    To resolve ambiguity, SQL employs a dot notation. An attribute A from a relation R is referenced as R.A. This qualification explicitly states the origin of the attribute, thereby disambiguating the reference.

  • Example of Disambiguation

    Consider two relations: MovieStar(name, address) and MovieExec(name, address). A query to find stars and executives living at the same address requires disambiguation for both name and address.

    SELECT MovieStar.name, MovieExec.name
FROM MovieStar, MovieExec
WHERE MovieStar.address = MovieExec.address;

  • Optional Qualification

    The Relation.Attribute syntax may be used even when no ambiguity exists. While only required for shared attribute names, it can be employed for any attribute to enhance the clarity of a query.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:53:32
  • Duration: 13.685984134674072
  • Cummulative cost: $1.40e-02

Tuple Variables

  • Handling queries that involve joining a relation with itself.
  • Defining aliases, known as tuple variables, for each instance of a relation in the FROM clause.
  • Using tuple variables to disambiguate attributes when referring to different tuples from the same relation.
#4

read: Section 6.2.3: Tuple Variables (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Handling queries that involve joining a relation with itself.
- Defining aliases, known as tuple variables, for each instance of a relation in the `FROM` clause.
- Using tuple variables to disambiguate attributes when referring to different tuples from the same relation.

When a query must involve two or more tuples from the same relation simultaneously, a mechanism is required to distinguish between the different roles these tuples play. SQL provides for this by allowing a relation in the FROM clause to be given one or more aliases, which we shall refer to as tuple variables.

Definition: Tuple Variable

A tuple variable is an alias for a relation specified in the FROM clause of an SQL query. If a relation \(R\) is used multiple times in a FROM clause, each occurrence must be given a distinct tuple variable, e.g., FROM R T1, R T2. The tuple variable then serves as a name for a specific tuple from that relation within the scope of the query, allowing for unambiguous reference to its attributes.

  • Self-Joins

    Tuple variables are necessary for queries that join a relation with itself. Such a query logically considers a Cartesian product of the relation with itself, and tuple variables are used to refer to the columns of the first and second instance of the relation in the product.

  • Declaration in the FROM Clause

    A tuple variable is defined for each occurrence of a relation in the FROM clause. The declaration syntax is RelationName AS Alias or more commonly RelationName Alias. The keyword AS is optional.

    For example, to consider pairs of tuples from the MovieStar relation, one writes:

    FROM MovieStar Star1, MovieStar Star2

    Here, Star1 and Star2 are tuple variables, each ranging over the tuples of MovieStar.

  • Attribute Disambiguation

    In the SELECT and WHERE clauses, attributes of a tuple are referenced by prefixing the attribute name with the corresponding tuple variable and a dot. This resolves the ambiguity that would otherwise arise when an attribute name appears in multiple relations (or multiple instances of the same relation) in the FROM clause.

    The following query finds pairs of movie stars who share an address.

    SELECT Star1.name, Star2.name
FROM MovieStar Star1, MovieStar Star2
WHERE Star1.address = Star2.address
  AND Star1.name < Star2.name;

    The WHERE clause condition Star1.address = Star2.address compares the address of the tuple bound to Star1 with that of the tuple bound to Star2. The condition Star1.name < Star2.name ensures that each pair is listed only once and that a star is not paired with himself.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:53:49
  • Duration: 17.18989896774292
  • Cummulative cost: $1.68e-02

Interpreting Multirelation Queries

  • Presentation of three equivalent ways to define the semantics of multirelation SQL queries.
  • The ‘Nested Loops’ approach: iterating through each tuple of each relation.
  • The ‘Parallel Assignment’ approach: considering all possible assignments of tuples to tuple variables simultaneously.
  • The ‘Conversion to Relational Algebra’ approach: translating the SQL query into a relational algebra expression involving Cartesian product, selection, and projection.
#5

read: Section 6.2.4: Interpreting Multirelation Queries (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Presentation of three equivalent ways to define the semantics of multirelation SQL queries.
- The 'Nested Loops' approach: iterating through each tuple of each relation.
- The 'Parallel Assignment' approach: considering all possible assignments of tuples to tuple variables simultaneously.
- The 'Conversion to Relational Algebra' approach: translating the SQL query into a relational algebra expression involving Cartesian product, selection, and projection.

There are three equivalent ways to define the semantics of a multirelation SQL query.

  • Nested Loops

    This procedural interpretation envisions a series of nested loops, one for each tuple variable declared in the FROM clause. The evaluation proceeds by iterating through every tuple of the outermost relation’s loop. For each of these, every tuple of the next relation is considered, and so on. In the innermost loop, for each complete combination of tuples, the WHERE clause condition is evaluated. If the condition is satisfied, the expressions in the SELECT clause are computed to produce a result tuple.

  • Parallel Assignment

    This approach is declarative and avoids specifying an iteration order. We consider, in parallel or in an arbitrary order, all possible assignments of tuples to the tuple variables. An assignment is a function that maps each tuple variable to a single tuple from its corresponding relation. For each assignment that makes the WHERE clause true, a result tuple is constructed from the expressions in the SELECT list and included in the query’s answer.

  • Conversion to Relational Algebra

    A multirelation SQL query can be translated directly into a relational algebra expression. This conversion follows a three-step process:
    1. Compute the Cartesian product of all relations listed in the FROM clause.
    2. Apply a selection operation (\(\sigma\)) to the resulting product, using the condition from the WHERE clause.
    3. Apply a projection operation (\(\pi\)) to the result of the selection, retaining only the attributes and computed values specified in the SELECT list.
Definition: Relational Algebra Semantics of SQL

An SQL query of the form:

SELECT L
FROM R₁, R₂, ..., Rₙ
WHERE C;

where \(L\) is a list of attributes, \(R_i\) are relations, and \(C\) is a condition, is formally defined by the relational algebra expression: \[ \pi_L(\sigma_C(R_1 \times R_2 \times \dots \times R_n)) \] - \(R_1 \times R_2 \times \dots \times R_n\) is the Cartesian product of the relations in the FROM clause. If tuple variables are used to alias a relation, each instance is treated as a distinct operand in the product, requiring attribute renaming. - \(\sigma_C\) is the selection operation corresponding to the WHERE clause. - \(\pi_L\) is the projection operation corresponding to the SELECT list.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:54:11
  • Duration: 21.66151714324951
  • Cummulative cost: $2.47e-02

Union, Intersection, and Difference of Queries

  • Introduction to SQL’s set operators for combining the results of queries: UNION, INTERSECT, and EXCEPT.
  • The requirement that queries combined with set operators must produce relations with the same list of attributes and types.
#6

read: Section 6.2.5: Union, Intersection, and Difference of Queries (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Introduction to SQL's set operators for combining the results of queries: `UNION`, `INTERSECT`, and `EXCEPT`.
- The requirement that queries combined with set operators must produce relations with the same list of attributes and types.

SQL provides operators to combine the results of queries in a manner analogous to the set operations of relational algebra. These operators allow for the construction of complex results by uniting, intersecting, or finding the difference between the tuple sets produced by simpler queries.

  • Set-Theoretic Operations

    SQL includes direct implementations of the primary set-theoretic operations from relational algebra. These operators are used to combine the results of two or more SELECT statements. The component queries are typically enclosed in parentheses.

  • UNION, INTERSECT, and EXCEPT

    The keywords for these operations are:
    • UNION: Computes the set union (\(R \cup S\)) of the results of two queries. It eliminates duplicate tuples from the combined result.
    • INTERSECT: Computes the set intersection (\(R \cap S\)) of the results of two queries, returning only tuples that appear in both results.
    • EXCEPT: Computes the set difference (\(R - S\)), returning tuples that appear in the result of the first query but not the second. Some SQL dialects use the keyword MINUS instead of EXCEPT.

  • Union Compatibility

    A critical requirement for using these set operators is that the relations produced by the queries must be union-compatible. This condition mandates that the relations have the same number of attributes, and the data types of corresponding attributes must be compatible.

Definition: SQL Set Operations

Let \(Q_1\) and \(Q_2\) be two SQL queries that produce relations \(R_1\) and \(R_2\), respectively. If \(R_1\) and \(R_2\) are union-compatible, meaning they possess the same list of attributes and corresponding attribute types, then the SQL set operations are defined as follows:

  • The expression (Q1) UNION (Q2) evaluates to the relation \(R_1 \cup R_2\).
  • The expression (Q1) INTERSECT (Q2) evaluates to the relation \(R_1 \cap R_2\).
  • The expression (Q1) EXCEPT (Q2) evaluates to the relation \(R_1 - R_2\).
  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-20 12:54:24
  • Duration: 12.568583011627197
  • Cummulative cost: $1.41e-02