Database Systems I Relational Algebra

上传人:gb****c 文档编号:243022364 上传时间:2024-09-14 格式:PPT 页数:38 大小:295KB
返回 下载 相关 举报
Database Systems I Relational Algebra_第1页
第1页 / 共38页
Database Systems I Relational Algebra_第2页
第2页 / 共38页
Database Systems I Relational Algebra_第3页
第3页 / 共38页
点击查看更多>>
资源描述
Click to edit Master title style,CMPT 354, Simon Fraser University, Fall 2008, Martin Ester,38,Click to edit Master text styles,Second Level,Third Level,Database Systems I Relational Algebra,Relational Query Languages,Query languages:,Allow manipulation and,retrieval of data,from a database.,Relational model supports simple, powerful query languages:,Strong formal foundation based on logic.,High level, abstract formulation of queries.,Easy to program.,Allows the DBS to do much optimization.,DBS can choose, e.g., most efficient sorting algorithm or the order of basic operations.,Relational Query Languages,Query Languages,!=,programming languages!,QLs not expected to be “Turing complete”.,QLs not intended to be used for complex calculations.,QLs support easy, efficient access to large data sets.,E.g., in a QL cannot,determine whether the number of tuples of a table is even or odd,create a visualization of the results of a query,ask the user for additional input.,Formal Query Languages,Two mathematical query languages form the basis for “real” languages (e.g. SQL), and for implementation:,Relational Algebra (RA),:,More,procedural, very useful for representing execution plans, relatively close to SQL.,Relational Calculus (RC),:,Lets users describe what they want, rather than how to compute it. (,Non-procedural,declarative,.),Understanding these formal query languages is important for understanding SQL and query processing.,Relational Algebra,An algebra consists of,operators,and,operands,. Operands can be either variables or constants.,In the algebra of arithmetic, atomic operands are variables such as x or y and constants such as 15. Operators are the usual arithmetic operators such as +, -, *.,Expressions,are formed by applying operators to atomic operands or other expressions.,For example,15x + 15,(x + 15) * y,Relational Algebra,Algebraic expressions can be re-ordered according to commutativity or associativity laws without changing their resulting value.,E.g.,15 + 20 = 20 + 15,(x * y) * z = x * (y * z),Parentheses group operators and define precedence of operators, e.g.,(x + 15) * y,x + (15 *y),Relational Algebra,In relational algebra,operands,are relations / tables, and an expression evaluates to a relation / set of tuples.,The relational algebra,operators,are,set operations,operations removing rows (selection) or columns (projection) from a relation,operations combining two relations into a new one (Cartesian product, join),a renaming operation, which changes the name of the relation or of its attributes.,Preliminaries,A query is applied to,relation instances, and the result of a query is also a relation instance.,Schemas,of input,relations for a query are,fixed,(but query will run regardless of instance!),The,schema for the,result,of a given query is also,fixed,! Determined by definition of input relations and query language constructs.,Positional vs. named-attribute notation:,Positional notation easier for formal definitions.,Named-attribute notation more readable.,Example Instances,R1,S1,S2,“Sailors” and “Reserves” relations for our examples.,Well use positional or named attribute notation, assume that names of attributes in query results are inherited from names of attributes in query input relations.,Relational Algebra Operations,Basic operations,Selection,( ) Selects a subset of,rows,from relation.,Projection,( ) Deletes unwanted,columns,from relation.,Cartesian product,( ),Combine,two relations,.,Set-difference,( ) Tuples in relation 1, but,not in,relation 2.,Union,( ) Tuples in relation 1,or,in relation 2.,Relational Algebra Operations,Renaming of relations / attributes.,Additional operations:,Intersection, join, division.,Not essential, can be implemented using the five basic operations.,But (very!) useful.,Since each operation returns a relation,operations,can be,composed,i.e. output of one operation can be input of the next operation.,Algebra is closed!,Renaming,Renames relations / attributes, without changing the relation instance.,relation R is renamed to S, attributes are renamed A1, . . ., An,Rename only some attributes,using the positional notation to reference attributes,No renaming of attributes,Projection,One input relation.,Deletes attributes that are not in,projection list,.,Schema,of result contains exactly the attributes in the projection list, with the same names that they had in the (only) input relation.,Projection operation has to eliminate,duplicates, since relations are sets.,Duplicate elimination is expensive.,Therefore, commercial DBMS typically dont do duplicate elimination unless the user explicitly asks for it.,Projection,S2,Selection,One input relation.,Selects all tuples that satisfy,selection condition,.,No duplicates in result! (Why?),Schema,of result identical to schema of (only) input relation.,Selection conditions:,simple conditions,comparing attribute values (variables) and / or constants or,complex conditions,that combine simple conditions using logical connectives AND and OR.,Selection,S2,Union, Intersection, Set-Difference,All of these set operations take two input relations, which must be,union-compatible,:,Same sets of attributes.,Corresponding attributes have same type.,What is the,schema,of result?,Cartesian Product,Also referred to as,cross-product,or,product,.,Two input relations.,Each tuple of the one relation is paired with each tuple of the other relation.,Result schema,has one attribute per attribute of both input relations, with attribute names inherited if possible.,In the result, there may be two attributes with the same name, e.g. both S1 and R1 have an attribute called,sid,.,Then, apply the,renaming operation, e.g.,Cartesian Product,R1,S1,Join,Similar to Cartesian product with same result schema.,Each tuple of the one relation is paired with each tuple of the other relation if the two tuples satisfy the,join condition,.,Theta-Join,:,Join,Equi-Join,:,A special case of Theta-join where the condition,c,contains only,equalities,.,Result schema,similar to Cartesian product, but only one copy of attributes for which equality is specified.,Natural Join,: Equi-join on,all,common attributes.,Division,Not supported as a primitive operation, but useful for expressing queries like:,Find sailors who have reserved,all,boats,.,Let,A,have 2 attributes,x,and,y,;,B,have only attribute,y,:,A/B,=,i.e., A/B contains all x tuples (sailors) such that for,every,y tuple (boat) in B, there is an xy tuple (reservation) in A.,In general,x,and,y,can be any lists of attributes;,y,is the list of attributes in,B, and,x,y,is the list of attributes of,A,.,Division,A,B1,B2,B3,A/B1,A/B2,A/B3,Division,Division is not an essential operation; can be implemented using the five basic operations.,Also true of joins, but joins are so common that systems implement joins specially.,Idea,:,For,A/B, compute all,x,values in,A,that are not disqualified by some,y,value in,B,.,x,value in,A,is,disqualified,if by attaching,y,value from,B, we obtain an,xy,tuple that is not in,A,.,Disqualified,x,values:,A/B:,all disqualified,x,values,Find names of sailors whove reserved boat #103.,Solution 1:,Solution 2:,Solution 3:,Example Queries,Find names of sailors whove reserved a red boat.,Information about boat color only available in Boats; so need an extra join:,A more efficient solution:,A query optimizer can find the second solution given the first one.,Example Queries,Find sailors whove reserved a red,or,a green boat.,Can identify all red or green boats, then find sailors whove reserved one of these boats:,Can also define Tempboats using union! (How?),What happens if OR is replaced by AND in this query?,Example Queries,Find sailors whove reserved a red,and,a green boat.,Previous approach wont work! Must identify sailors whove reserved red boats, sailors whove reserved green boats, then find the intersection,(note that,sid,is a key for Sailors),:,Example Queries,Find the names of sailors whove reserved,all,boats.,Uses division; schemas of the input relations must be carefully chosen:,To find sailors whove reserved all Interlake boats:,Example Queries,Query Optimization,A user of a commercial DBMS formulates SQL queries.,The query optimizer translates this query into an,equivalent,RA query, i.e. an RA query with the same result.,In order to optimize the efficiency of query processing, the query optimizer can re-order the individual operations within the RA query.,Re-ordering has to preserve the query semantics and is based on RA equivalences.,Query Optimization,Why can re-ordering improve the efficiency?,Different orders can imply different sizes of the intermediate results.,The smaller the intermediate results, the more efficient.,Example:,much (!) more efficient than,Relational Algebra Equivalences,The most important RA equivalences are commutative and associative laws.,A,commutative law,about some operation states that the order of (two) arguments does not matter.,An,associative law,about some (binary) operation states that (more than two) arguments can be grouped either from the left or from the right.,If an operation is both commutative and associative, then any number of arguments can be (re-)ordered in an arbitrary manner.,Relational Algebra Equivalences,The following (binary) RA operations are commutative and associative:,For example, we have:,Proof method: show that each tuple produced by the expression on the left is also produced by the expression on the right and vice versa.,(R S) (S R),(Commutative),R (S T) (R S) T,(Associative),Relational Algebra Equivalences,Selections are crucial from the point of view of query optimization, because they typically reduce the size of intermediate results by a significant factor.,Laws for selections only:,(Splitting),(Commutative),Relational Algebra Equivalences,Laws for the combination of selections and other operations:,if R has all attributes mentioned in c,if S has all attributes mentioned in c,The above laws can be applied to “push selections down” as much as possible in an expression, i.e. performing selections as early as possible.,Relational Algebra Equivalences,A projection commutes with a selection that only uses attributes retained by the projection.,Selection between attributes of the two arguments of a Cartesian product converts Cartesian product to a join.,Similarly, if a projection follows a join R S, we can push it by retaining only attributes of R (and S) that are needed for the join or are kept by the projection.,Summary,The relational model has formal query languages that are easy to use and allow efficient optimization by the DBS.,Relational algebra (RA) is more procedural; used as internal representation for SQL query evaluation plans.,Five basic RA operations: selection, projection, Cartesian product, union, set-difference.,Additional operations as shorthand for important cases: intersection, join, division.,These operations can be implemented using the basic operations.,Summary,Several ways of expressing a given query; a query optimizer chooses the most efficient version.,Query optimization exploits RA equivalencies to re-order the operations within an RA expression.,Optimization criterion is to minimize the size of intermediate relations.,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 图纸专区 > 大学资料


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!