### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DATABASE SYSTEM DESIGN CSCE 520

GPA 3.61

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 40 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 520 at University of South Carolina - Columbia taught by Lm Stephens in Fall. Since its upload, it has received 21 views. For similar materials see /class/229578/csce-520-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for DATABASE SYSTEM DESIGN

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Relational Algebra Basic Operations Algebra of Bags What is an Algebra OMathematical system consisting of o 0peran0 s variables or values from which new values can be constructed o 0perat0rs symbols denoting procedures that construct new values from given values What is Relational Algebra OAn algebra whose operands are relations or variables that represent relations OOperators are designed to do the most common things that we need to do with relations in a database o The result is an algebra that can be used as a Way language for relations Core Relational Algebra OUnion intersection and difference o Usual set operations but both operands must have the same relation schema OSelection picking certain rows OProjection picking certain columns OProducts and joins compositions of relations ORenaming of relations and attributes Selection 9R1 O39CR2 o C is a condition as in if statements that refers to attributes of R2 o R1 is all those tuples of R2 that satisfy C Example Selection Relation Sells bar beer price Joe s Bud 250 Joe s Miller 275 Sue s Bud 250 Sue s Miller 300 JoeMenu O39barz JoesSells bar beer price Joe s Bud 250 Joe s Miller 275 Projection 9R1 1TLR2 o L is a list of attributes from the schema of R2 o R1 is constructed by looking at each tuple of R2 extracting the attributes on list L in the order specified and creating from those components a tuple for R1 o Eliminate duplicate tuples if any Example Projection Relation Sells bar beer price Joe s Bud 250 Joe s Miller 275 Sue s Bud 250 Sue s Miller 300 Prices beerlprice ells beer price Bud 250 Miller 275 Miller 300 Extended Projection 9 Using the same 1T L operator we allow the list L to contain arbitrary expressions involving attributes 1 Arithmetic on attributes eg AB gtC 2 Duplicate occurrences of the same attribute Example Extended Projection RA 1 3 B 2 4 TrA B gtCAA R IUJ 10 Product 9R3 R1 X R2 o Pair each tuple t1 of R1 with each tuple t2 of R2 o Concatenation t1t2 is a tuple of R3 o Schema of R3 is the attributes of R1 and then R2 in order o But beware attribute A of the same name in R1 and R2 use R1A ancl R2A 11 Example R3 R1 X R2 60006000 579579 R1B R2B c 222444 A1111333 arm R BZ4 C680 R1 R2 12 ThetaJoin 9R3 R1 NCRZ o Take the product R1 X R2 o Then apply CC to the result OAS for 039 C can be any booleanvalued condition 0 Historic versions of this operator allowed only A 6 B where 6 is lt etc hence the name thetajoin 13 Example Theta Join Sells bar beer price Bars name addr Joe s Bud 250 Joe s Maple St Joe s Miller 275 Sue s River Rd Sue s Bud 250 Sue s Coors 300 BarInfO sells NSellsbar Barsname Bars BarInfo bar beer price name addr Joe s Bud 250 Joe s Maple St Joe s Miller 275 Joe s Maple St Sue s Bud 250 Sue s River Rd Sue s Coors 300 Sue s River Rd 14 Natural Join 0A useful join variant natural join connects two relations by 0 Equating attributes of the same name and o Projecting out one copy of each pair of equated attributes ODenoted R3 R1 M R2 15 Example Natural Join Sells bar beer price Bars bar addr Joe s Bud 250 Joe s Maple St Joe s Miller 275 Sue s River Rd Sue s Bud 250 Sue s Coors 300 BarInfo Sells gt4 Bars Note Barsname has become Barsbar to make the natural join work BarInfo bar beer price addr Joe s Bud 250 Maple St Joe s Milller 275 Maple St Sue s Bud 250 River Rd Sue s Coors 300 River Rd 16 Renaming OThe p operator gives a new schema to a relation 9R1 pR1A1IAR2 makes R1 be a relation with attributes A1An and the same tuples as R2 OSimplified notation R1A1An R2 17 Example Renaming Bars name addr Joe s Maple St Sue s River Rd Rbar addr Bars R bar addr Joe s Maple St Sue s River Rd 18 Building Complex Expressions 9 Combine operators with parentheses and precedence rules 9 Three notations just as in arithmetic 1 Sequences of assignment statements 2 Expressions with several operators 3 Expression trees 19 Sequences of Assignments OCreate temporary relation names ORenaming can be implied by giving relations a list of attributes OExample R3 R1 MCRZ can be written R4 R1 X R2 R3 O39CR4 20 Expressions in a Single Assignment 9 Example the thetajoin R3 R1 MCRZ can be written R3 O39CR1 X R2 9 Precedence of relational operators 1 039 1T p highest 2 X N 3 m 4 U 21 Expression Trees OLeaves are operands either variables standing for relations or particular constant relations OInterior nodes are operators applied to their child or children 22 Example Tree for a Query OUsing the relations Barsname addr ancl Sellsbar beer price find the names of all the bars that are either on Maple St or sell Bud for less than 3 23 As a Tree U p Rname name 1Tbar Oaddr Maple St Upricelt3 AND beer Bud Bars Sells 24 Example SelfJoin OUsing Sellsbar beer price find the bars that sell two different beers at the same price OStrategy by renaming define a copy of Sells called Sbar beer1 price The natural join of Sells and S consists of quadruples bar beer beer1 price such that the bar sells both beers at this price 25 The Tree bar 0beer beerl M pSbar beerl price Sells Sells 26 Schemas for Results OUnion intersection and difference the schemas of the two operands must be the same so use that schema for the result OSelection schema of the result is the same as the schema of the operand OProjection list of attributes tells us the schema 27 Schemas for Results 2 OProduct schema is the attributes of both relations o Use RA etc to distinguish two attributes named A OThetajoin same as product ONatural join union of the attributes of the two relations ORenaming the operator tells the schema 28 Relational Algebra on Bags 9A bag or maltSet is like a set but an element may appear more than once OExample 1213 is a bag OExample 123 is also a bag that happens to be a set 29 Why Bags OSQL the most important query language for relational databases is actually a bag language OSome operations like projection are more efficient on bags than sets 30 Operations on Bags OSelection applies to each tuple so its effect on bags is like its effect on sets OProjection also applies to each tuple but as a bag operator we do not eliminate duplicates OProducts and joins are done on each pair of tuples so duplicates in bags have no effect on how we operate 31 R Example Bag Selection I IU39II IJgt NONNUJ O4Blt 5 R A B 32 Example Bag Projection R A B 1 2 5 6 1 2 1TAR m 33 Example Bag Product 34 400400400 38 373737 RB 226622 115511 C400 337 S 8262 A1151 R RXS Example Bag ThetaJoin 40000400 33 37737 RB 22622 11511 C400 337 S 8262 A1151 R R N RBltSB S 35 Bag Union OAn element appears in the union of two bags the sum of the number of times it appears in each bag OExample 121 U 11231 111I1I1I2I2I3 36 Bag Intersection OAn element appears in the intersection of two bags the minimum of the number of times it appears in either OExample 1211 1213 112 37 Bag Difference OAn element appears in the difference A B of bags as many times as it appears in A minus the number of times it appears in B o But never less than 0 times OExample 1211 123 11 38 Beware Bag Laws Set Laws OSome but not all algebraic laws that hold for sets also hold for bags OExample the commutative law for union R US SUR does hold for bags o Since addition is commutative adding the number of times X appears in R and 5 doesn t depend on the order of R and 5 39 Example A Law That Fails OSet union is idempotent meaning that 5 U5 5 OHowever for bags if xappears n times in 5 then it appears 2n times in 5 U5 OThus SUS 5 in general eg 1 U 1 11 1 40

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.