*Selection on Bags / Product of Bags / Joins of Bags*

On January 27, 2014, In Relational Algebra by Admin

Views (1275)

### Selection on Bags

To apply a selection to a bag, we apply the selection condition to each tuple separately. As always with bags, we do not remove duplicate tuples in the result.**Example (a) :**If R is the bag

then the result of the bag-selection is

That is, all but the first tuple meets the selection condition. The last two tuples, which are duplicates in R, are each included in the result.

### Product of Bags

The rule for the Cartesian product of bags is the expected one. Each tuple of one relation is paired with each tuple of the other, regardless of whether it is a duplicate or not. As a result, if a tuple r appears in a relation R m times and tuple s appears n times in relation S, then in the product R x S, the tuple rs will appear mn times.**Example (b) :**Let R and S be the bags shown in Figure A. Then the product R x S consists of six tuples, as shown in Figure A-(c). Note that the normal convention regarding attribute names that we developed for set-relations applies equally well to bags. In this way, the attribute B, which belongs to both relations R and S, appears twice in the product, each time prefixed by one of the relation names.

### Joins of Bags

Joining bags also presents no surprises. We compare each tuple of one relation with each tuple of the other, decide whether or not this pair of tuples joins successfully, and if so we put the resulting tuple in the answer. When constructing the answer, we do not remove duplicate tuples.**Example (c) :**The natural join R ⋈ S of the relations R and S seen in Figure A is

That is, tuple (1, 2) of R joins with (2, 3) of S. Since there are two copies of (1, 2) in R and one copy of (2, 3) in S, there are two pairs of tuples that join to give the tuple (1, 2, 3). No other tuples from R and S join successfully.

As another example on the same relations R and S, the theta-join

produces the bag

The computation of the join is as follows. Tuple (1, 2) from R and (4, 5) from S meet the join condition. Since each appears twice in its relation, the number of times the joined tuple appears in the result is 2 x 2 or 4. The other possible join of tuples - (1, 2) from R with (2, 3) from S - fails to meet the join condition, so this combination does not appear in the result.

### Tags

- tuples
- product of bags
- joins of bags
- attribute
- theta-join
- relational algebra
- Scrolling Cursors
- Protecting Against Concurrent Updates
- Modifications by Cursor
- Cursors
- Triggers in SQL
- Schema-Level Constraints and Triggers
- Modification of Constraints
- Tuple-Based CHECK Constraints
- Keys Declared With UNIQUE
- Constraints and Triggers
- Interpreting Queries Involving Views
- Modifying Views
- View Definitions
- Introduction to Selection of Indexes
- Default Values / Indexes
- Simple Table Declarations
- Deletion / Updates
- Database Modifications
- Grouping / HAVING Clauses
- Full-Relation Operations
- Natural Joins / Outerjoins
- Correlated Subqueries
- Union, Intersection, and Difference of Queries
- Interpreting Multirelation Queries
- Tuple Variables
- Disambiguating Attributes
- Queries Involving More Than One Relation
- Null Values and Comparisons Involving NULL
- Selection in SQL
- Projection in SQL
- The Database Language SQL
- Additional Constraint Examples
- Referential Integrity Constraints
- Constraints on Relations
- Outerjoins
- Extending the Projection Operator
- Grouping
- Extended Operators of Relational Algebra
- Union, Intersection, and Difference of Bags
- Relational Operations on Bags
- A Linear Notation for Algebraic Expressions
- Dependent and Independent Operations
- Renaming
- Combining Operations to Form Queries
- Natural Joins / Theta-Joins
- Selection / Cartesian Product
- Set Operations on Relations
- An Algebra of Relational Operations
- Relational Algebra
- Information Integration Via Semistructured Data
- References
- Nested Relations
- The Object-Relational Model
- Representing ODL Relationships
- Representing Other Type Constructors
- Nonatomic Attributes in Classes
- Additional ODL Concepts
- Relationships in ODL / Inverse Relationships
- Reasoning About Multivalued Dependencies
- Definition of Multivalued Dependencies
- Multivalued Dependencies
- Boyce-Codd Normal Form
- Decomposing Relations
- Why the Closure Algorithm Works
- Trivial Functional Dependencies
- Rules About Functional Dependencies
- Keys of Relations
- Using Null Values to Combine Relations - Comparison of Approaches
- Converting Subclass Structures to Relations
- From E/R Diagrams to Relational Designs
- Relation Instances
- Equivalent Representations of a Relation
- Tuples / Domains
- Avoiding Redundancy
- Converting Multiway Relationships to Binary
- Multiway Relationships
- Database System Implementation
- Database Programming
- Database Design
- The Query Processor
- Multimedia Data
- Relational Database Systems