*An Algebra of Relational Operations*

On December 04, 2013, In Relational Algebra by Admin

Views (1476)

In order to start our study of operations on relations, we shall learn about a special algebra, called "relational algebra", that comprises some simple but powerful ways to construct new relations from given relations. When the given relations are stored data, then the constructed relations can be answers to queries about this data.

The development of an algebra for relations has a history, which we shall follow roughly in our presentation. In the beginning, relational algebra was proposed by T. Codd as an algebra on sets of tuples (i.e., relations) that could be used to express usual queries about those relations. It consisted of five operations on sets: union, set difference, and Cartesian product, with which you might already be familiar, and two unusual operations - selection and projection. To these, several operations that can be described in terms of these were added: varieties of "join" are the most important.

When DBMS's that used the relational model were first developed, their query languages largely implemented the relational algebra. Though, for efficiency purposes, these systems regarded relations as bags, not sets. That is, unless the user asked unambiguously that duplicate tuples be condensed into one (i.e., that "duplicates be eliminated"), relations were allowed to include duplicates. Therefore, in "Relational Operations on Bags", we shall study the same relational operations on bags and see the changes necessary.

Another change to the algebra that was necessitated by commercial implementations of the relational model is that many other operations are required. Most important is a way of performing aggregation, e.g., finding the average value of some column of a relation. We shall study these additional operations in "Extended Operators of Relational Algebra".

### Basics of Relational Algebra

An algebra, generally, comprises operators and atomic operands. For example, in the algebra of arithmetic, the atomic operands are variables like x and constants like 15. The operators are the usual arithmetic ones: addition. subtraction, multiplication, and division. Any algebra allows us to build expressions by applying operators to atomic operands and/or other expressions of the algebra. Generally, parentheses are required to group operators and their operands. For example, in arithmetic we have expressions such as (x + y) * z or ((x+7) / (y-3)) + z .Relational algebra is another instance of an algebra. Its atomic operands are:

1. Variables that stand for relations.

2. Constants, which are finite relations.

As we mentioned, in the classical relational algebra, all operands and the results of expressions are sets. The operations of the traditional relational algebra fall into four broad classes:

a) The usual set operations - union, intersection, and difference - applied to relations.

b) Operations that remove parts of a relation: "selection" removes some rows (tuples), and "projection" removes some columns.

c) Operations that combine the tuples of two relations, including "Cartesian product", which pairs the tuples of two relations in all possible ways, and many kinds of "join" operations, which selectively pair tuples from two relations.

d) An operation called "renaming" that does not affect the tuples of a relation, but changes the relation schema, i.e., the names of the attributes and/or the name of the relation itself.

We shall usually refer to expressions of relational algebra as queries. While we don't yet have the symbols required to show many of the expressions of relational algebra, you should be familiar with the operations of group (a), and thus recognize (R U S) as an example of an expression of relational algebra. R and S are atomic operands standing for relations, whose sets of tuples are unknown. This query asks for the union of whatever tuples are in the relations named R and S.

### Tags

- relational algebra
- tuples
- operators
- attributes
- queries
- Scrolling Cursors
- Protecting Against Concurrent Updates
- Modifications by Cursor
- Cursors
- Instead-Of Triggers
- Triggers in SQL
- Schema-Level Constraints and Triggers
- Tuple-Based CHECK Constraints
- Constraints on Attributes and Tuples
- Declaring Foreign-Key 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
- Defining a Relation Schema in SQL
- Deletion / Updates
- Database Modifications
- Grouping / HAVING Clauses
- Full-Relation Operations
- Natural Joins / Outerjoins
- Subqueries in FROM Clauses
- Conditions Involving Tuples
- 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
- Extending the Projection Operator
- Grouping
- Extended Operators of Relational Algebra
- Selection on Bags / Product of Bags / Joins of Bags
- 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
- Selection / Cartesian Product
- Set Operations on Relations
- Relational Algebra
- Attribute Lists
- Information Integration Via Semistructured Data
- Semistructured Data Representation
- Object-Oriented Versus Object-Relational
- Nested Relations
- The Object-Relational Model
- What If There Is No Key
- Representing ODL Relationships
- Representing Other Type Constructors
- Representing Set-Valued Attributes
- Nonatomic Attributes in Classes
- Declaring Keys in ODL
- Subclasses in ODL / Multiple Inheritance in ODL
- Types in ODL
- Methods in ODL
- Multiplicity of Relationships
- Relationships in ODL / Inverse Relationships
- Attributes in ODL
- Introduction to ODL
- The Type System
- Decomposition into Fourth Normal Form
- Reasoning About Multivalued Dependencies
- Definition of Multivalued Dependencies
- Multivalued Dependencies
- Third Normal Form
- Boyce-Codd Normal Form
- Decomposing Relations
- Projecting Functional Dependencies
- Closing Sets of Functional Dependencies
- The Transitive Rule
- Why the Closure Algorithm Works
- Computing the Closure of Attributes
- Trivial Functional Dependencies
- The Splitting/Combining Rule
- Rules About Functional Dependencies
- Keys of Relations
- Using Null Values to Combine Relations - Comparison of Approaches
- An Object-Oriented Approach
- Converting Subclass Structures to Relations
- Handling Weak Entity Sets
- Combining Relations
- From E/R Relationships to Relations
- From Entity Sets to Relations
- From E/R Diagrams to Relational Designs
- Relation Instances
- Equivalent Representations of a Relation
- Tuples / Domains
- Attributes / Schemas
- The Relational Data Model
- Summary of The Entity-Relationship Data Model
- Weak Entity Set Notation
- Requirements for Weak Entity Sets
- Representing Keys in the E/R Model
- Keys in the E/R Model
- The Modeling of Constraints
- Picking the Right Kind of Element
- Design Principles
- Subclasses in the E/R Model
- Converting Multiway Relationships to Binary
- Attributes on Relationships
- Multiway Relationships
- Elements of the E/R Model
- Database System Implementation
- Database Programming
- Database Design
- The Query Processor
- Information Integration
- Multimedia Data
- Relational Database Systems
- Banking Systems
- Airline Reservations Systems