3/1/11$1$Rela)onal$Algebra$CISC437/637,$Lecture$#6$Ben$Cartere=e$1$Copyright$©$Ben$Cartere=e$Rela)onal$Query$Languages$• A$query$language$allows$manipula)on$and$retrieval$of$data$from$a$database$• The$rela)onal$model$supports$simple$but$powerful$query$languages$– Formal$founda)on$based$on$logic$– Allows$for$a$great$deal$of$op)miza)on$• A$query$language$is$not$a$programming$language$– Not$TuringOcomplete,$not$intended$for$complex$calcula)ons$– Supports$easy,$efficient$access$to$data$2$Copyright$©$Ben$Cartere=e$3/1/11$2$Formal$Query$Languages$• Two$mathema)cal$formalisms:$– Rela%onal(algebra,$based$on$operators$over$rela)ons$– Rela%onal(calculus,$based$on$declara)ve$statements$about$data$• The$algebra$more$directly$supports$computa)on$– A$rela)onal$algebra$query$implies$a$sequence$of$steps$that$can$be$taken$to$execute$it$• SQL$is$an$implementa)on$of$rela)onal$algebra$Copyright$©$Ben$Cartere=e$ 3$Preliminaries$• A$query$is$applied$to$rela%on(instances,$and$the$result$of$a$query$is$a$rela)on$instance$– Schemas$of$input$rela)ons$are$fixed$– Schemas$of$output$rela)ons$are$also$fixed,$though$may$be$different$from$input$rela)on$schemas$• Posi)onal$versus$namedOfield$nota)on:$– Posi)onal$nota)on$is$easier$for$formal$defini)ons;$namedOfield$easier$to$read$– SQL$supports$both$Copyright$©$Ben$Cartere=e$ 4$3/1/11$3$Rela)onal$Algebra$• Basic$operators:$– Selec%on:$$σ(R)$–$select$a$subset$of$records$from$rela)on$R$– Projec%on:((π(R)$–$drop$unwanted$fields$from$rela)on$R$– Cross4product:($R1$×$R2$–$concatenate$each$record$in$R1$with$each$record$in$R2$– Set4difference:($R1$–$R2$–$return$records$in$R1$that$are$not$in$R2$– Union:($R1$∪$R2$–$return$records$in$either$R1$or$R2$• Algebra$is$all$about$composing$operators$– Every$operator$takes$rela)ons$as$input$and$returns$rela)ons$– Algebra$is$closed$under$these$operators$Copyright$©$Ben$Cartere=e$ 5$Rela)onal$Algebra$• More$operators:$– Intersec%on:($R1$∩$R2$–$return$records$in$both$R1$and$R2$– Join:((R1$⋈$R2$–$combine$informa)on$from$rela)ons$R1$and$R2$– Division:((R1/R2$–$return$records$in$R1$that$“match”$every(record$in$R2$in$a$subset$of$fields$– Renaming:((ρ(R(F),$E)$–$the$rela)on$returned$by$expression$E$is$named$R$and$its$fields$are$renamed$according$to$mapping$F$– Aggregate(func%ons:$$Gf(R)$–$calculate$aggrega)ng$func)on$f$on$rela)on$R(Copyright$©$Ben$Cartere=e$ 6$3/1/11$4$Selec)on$&$Projec)on$• Selec)on$returns$all$records$matching$a$logical$selec%on(condi%on(p$– σp(R)$is$a$rela)on$consis)ng$only$of$records$in$R$for$which$p$is$true$– Schema$of$σp(R)$is$the$same$as$schema$of$R$• Projec)on$returns$a$rela)on$with$only$the$fields$indicated$– πx(R)$is$a$rela)on$with$only$the$fields$of$R$specified$in$the$list$x$– Schema$of$πx(R)$is$a$subset$of$the$schema$of$R$– Records$in$πx(R)$same$as$records$in$R,$but$duplicates$are$dropped$Copyright$©$Ben$Cartere=e$ 7$Projec)on$&$Sel ec)on$• Generalized(projec%on$allows$selec)ng$arithme)c$func)ons$of$fields$– πF(R),$where$F$is$an$arithme)c$(uses$+,$−,$×,$÷)$func)on$of$one$or$more$fields$and$constant$values$• Selec)on$and$projec)on$operators$can$be$composed$– πx(σp(R))$returns$a$rela)on$with$records$in$R$for$which$p$is$true,$and$with$only$fields$specified$in$x$$Copyright$©$Ben$Cartere=e$ 8$3/1/11$5$Set$Operators$• Union,$intersec)on,$and$setOdifference$• These$take$two$rela)ons$R1$and$R2$and$return$a$new$rela)on $$• R1$and$R2$must$be$union6compa%ble$– Same$number$of$fields$– Corresponding$fields$must$have$same$domain$• The$schema$of$the$new$rela)on$is$defined$to$be$the$schema$of$R1$Copyright$©$Ben$Cartere=e$ 9$CrossOProduct$• CrossOproduct$R1$×$R2$pairs$each$record$in$R1$with$each$record$in$R2$to$create$a$new$rela)on$of$concatenated$records$• Schema$is$defined$to$be$the$concatena)on$of$R1$and$R2’s$schemas$– If$both$have$a$field$with$the$same$name,$refer$to$that$field$by$number$– Or$rename$it$using$the$ρ$operator$Copyright$©$Ben$Cartere=e$ 10$3/1/11$6$Joins$• Combine$two$rela)ons$R1$and$R2$in$such$a$way$that$all$records$match$some$logical$condi)on$p$– R1$⋈p$R2$≡$σp(R1$×$R2)$• Schema$is$the$same$as$the$crossOproduct$schema$(except$in$special$cases)$– Equijoin:$$p$is$an$equality$condi)on$• Schema$drops$duplicate$fields$that$are$part$of$equality$– Natural$join:$$p$is$a$conjunc)on$of$equality$condi)ons$on$all$fields$with$the$same$names$$Copyright$©$Ben$Cartere=e$