Implementing Tutorial D in Ingres 2006

Description

¨TECHNISCHE UNIVERSITAT ILMENAU
Institut fur¨ Praktische Informatik und Medieninformatik
Fakultat¨ fur¨ und Automatisierung
Fachgebiet Datenbanken und Informationssysteme
Studienarbeit
ImplementingTutorialDinIngres2006
vorgelegt von
Michael Strobel
Matrikel-Nr. 36975
Betreuer:
Prof. Dr.–Ing. Kai-Uwe Sattler
Ilmenau, den 28. Juli 2008Contents
1 Introduction 1
2 Tutorial D 2
2.1 Types, Variables and Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.1 Generating Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.2 Defining Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.3 Assigning Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Query Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.4 Rename . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Ingres 2006 10
3.1 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Node Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

Sujets

• M&M's
• Yi Jing
• P.S.F. Records
• Nouveau Centre
• N-uplet
• Operator (extension)

Informations

• Publié par: Oddu
• Nombre de lectures: 156
• Langue: English

Extrait

¨ TECHNISCHE UNIVERSITAT ILMENAU Institutf ¨ urPraktischeInformatikundMedieninformatik Fakult ¨ atfu ¨ rInformatikundAutomatisierung Fachgebiet Datenbanken und Informationssysteme

Studienarbeit

Implementing Tutorial D in Ingres 2006

vorgelegt von

Michael Strobel Matrikel-Nr. 36975

Betreuer:

Prof. Dr.–Ing. Kai-Uwe Sattler

Ilmenau, den 28. Juli 2008

Contents

1 Introduction 2 Tutorial D 2.1 Types, Variables and Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Generating Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Defining Variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Assigning Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Query Operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Projection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Selection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Join. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Rename. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ingres 2006 3.1 Query Processing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Query Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Tree Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Node Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Implementation 4.1 Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Rules and Actions. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Scanner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Scanner subroutine. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Integration of parser and scanner in the backend. . . . . . . . . . . . . . . . . 4.4 Modification of the Terminal Monitor. . . . . . . . . . . . . . . . . . . . . . 4.5 Adaption of the build process. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Conclusion and Future Work References

i

1 2 2 2 2 5 7 7 7 8 8 10 10 10 10 12 17 17 17 18 38 38 46 64 65 67 69 70

1 Introduction

SQL has become the de-facto standard among relational query languages for relational databases over the years, but it has also a lot of issues, as the missing of certain constructs and operators, the to some extend cumbersome and inconsistent syntax, or the differences between it’s and the relational model. This work considers a prototype implementation of Tutorial D, a proposal of a relational query language which should avoid this issues, in the Ingres 2006 DBMS.

1

2 Tutorial D

Tutorial D is a proposal of a relational query language that meets a set of specifications for the design of a relational database management system and relational query languages, called D, based upon C. J. Date’s and Hugh Darwen’s theoretical considerations in this field. Both, Tu- torial D and D, is issued in [DD06on Tutorial D is issued in []. Additional information Dat05]. Background on Tutorial D for the implementation, focusing on types, variables and values in Tutorial D and on query operators in comparison to SQL, is provided in this chapter.

2.1 Types, Variables and Values

Tutorial D makes a clear distinction between types, variables and values. SQL doesn’t make such a clear distinction. For example the term table is often used ambiguous. It refers to relation values on the one hand and relation variables on the other hand. In common case the meaning can be derived from the context, but this ambiguity certainly may cause some confusion. In the remainder of this work the term relation stands for relation values and the term relation variable is used for relation variables.

2.1.1 Generating Types As common in relational database systems Tutorial D provides a number of built-in or system defined types and supports user defined types. System defined types areinteger- singed integer numbers,rational- singed rational numbers,characterorchar- varying-length character strings,boolean- truth values. A fixed-length character strings type as in SQL is not part of the system defined types. User defined types may be constructed either by defining a name and a possible representation to obtain a new scalar type, which is not discussed further in this work, or by using type generators, operators that take types and return another type, to obtain new scalar or non-scalar types. Of special interest for relational database systems are the tuple type generator and the relation type generator, as they return tuple types and relation types. They are invoked by the keywordstupleandrelation, followed by a list attribute names and types corresponding to the attributes, which define the returned tuple type or relation type.

2.1.2 Defining Variables In the following examples the definition of variables in Tutorial D, in comparison to SQL, is considered. Tutorial D allows the definition of scalar variables, tuple variables and relation vari- ables, whereas scalar variables have scalar types, tuple variables have tuple types and relation variables relation types.

2

2 Tutorial D

A relation variable might stand for a base relation or a virtual relation, also known as a view. The definition of a variable for a base relation is introduced by the keywordvar, followed by the name of the variable, followed by the keywordrealorbaseand completed by the type of the variable or followed by the keywordinitand completed by an initial value, whereas it is also allowed to state type and initial value combined. The definition of a variable for a virtual relation is introduced by the keywordvar, followed by the name of the variable, followed by the keywordvirtualorviewby a relation expression that mentions at leastand completed one existing relation variable. In both cases a list of candidate keys, which is introduced by the keywordkey, may be included at the very end of the definition. The first example shows how a definition of base relation variable may look like in Tutorial D. As mentioned before in Tutorial D the key following the unqualified keywordkeyis a candidate key and not a primary key, as Tutorial D does not support primary keys as such. According to the meaning of a key as candidate key multiple keys may be stated, but they also may be omitted completely. J Example 2.1.1 IDefining a relation variable for a base relation in Tutorial D: varPizzas real relation{ Namecharacter(25) , D i ameterinteger, Pricerational } key{ Name }

J Example 2.1.2 IDefining a relation variable for a base relation in SQL: create tablezaizP(s Namechar(25) , D i ameterinteger, Price real , primary key( Name ) );

The second example shows how an initial value may be provided for a relational variable def- inition in Tutorial D. Though not shown in the example, Tutorial D also permits stating tuples them selfs by using tuples selectors to provide an initial value, instead of a stating query for the initialization. Actually an arbitrary relational expression may be stated there, but more on relational expressions later. J Example 2.1.3 IDefining a relation variable for a base relation in Tutorial D and assigning an initial value: varS m a l l P i z z a s init( PizzaswhereD i ameter < 20) varS m a l l P i z z a s real relation{

3

2 Tutorial D

Namecharacter(25) , D i ameterinteger, Pricerational } key{ Name } init( PizzaswhereD i ameter < 20)

J Example 2.1.4 IDefining a relation variable for a base relation in SQL and assingning an initial value: create tableS m a l l P i z z a sas select* fromPizzas where < 20;D i ameter

In the next example a view is defined in Tutorial D J Example 2.1.5 Ia virtual relation in Tutorial D:Defining a relation variable for varS m a l l P i z z a s virtual( PizzaswhereD i ameter < 20) key{ Name }

J Example 2.1.6 IDefining a relation variable for a virtual relation in SQL: create viewS m a l l P i z z a sas select* fromPizzas where < 20;D i ameter

The definition of tuple variables or scalar variables is very similar. It is introduced by the keywordvarof the variable, followed by the type of the variable or an, followed by the name initial value, which is introduced by the keywordinit, and again it is also allowed to state type and initial value combined combined altogether. J Example 2.1.7 IDefining a tuple variable in Tutorial D: varPizza tuple{ Namecharacter(25) , D i ameterinteger, Pricerational }

J Example 2.1.8 IDefining a scalar variable Tutorial D: varD i ameterinteger

4

2 Tutorial D

2.1.3 Assigning Values The concept of variables, types and values is not very useful without operations or operators. At least the assignment operation and the comparison operation must be available. Tutorial D supports the direct assignment by the assignment operator:=of values to variables. SQL actu- ally has no assignment operator in sense of direct assignment. Instead it hasINSERT,UPDATE andDELETEoperators, which are also available in Tutorial D. On the left side of the assignment operator is the target variable and on the right side of the as- signment operator is a expression that must evaluate to a value of the type of the target variable. In the examples below the assignment of an relation to an relation variable is shown one time by a query on an existing relation and another time by constructing the relation using relation selectors and tuple selectors. Afterward is shown what could be done to execute an assign- ment operation in SQL. Obviously it is possible to do an assignment operation in SQL by using DELETE and INSERT, but it’s a bit more complicated and neither that compact nor that elegant as in Tutorial D. J Example 2.1.9 IAssignment in Tutorial D: S m a l l P i z z a := PizzawhereD i ameter = 1 S m a l l P i z z a :=relation{ tuple Magerita ’( Name i a m e t e r D , ’ , 1 , Price 2.0) tuple 1 , Price 2.5) , , ’ i a m e t e r D( Name Rustica ’ tuple Price 2.5) , 1 ’ , D i a m e t e r( Name ’ Capritosa }

J Example 2.1.10 ISimulation of an assignment in SQL: begin oftransaction; delete fromS m a l l P i z z a ; insert intoS m a l l P i z z a select* fromPizza where = 1;D i ameter commit; begin oftransaction; delete fromS m a l l P i z z a ; insert intoS m a l l P i z z a values Diamet( ’ Mag erita ’ , 1 e r , Price 2.0) , ( ’ Rustica ’ , Diamet e r 1 , Price 2.5) , ( ’ C a p r i t o s a ’ , Diam e t e r 1 , Price 2.5); commit;

Inserting tuples in a relation of a relation variable The insert operation on relations is introduced by theinsertkeyword, followed by target the relation variable, followed by the a expression which evaluates to a relation containing the

5

2 Tutorial D tuples, for insertion in the relation of the target relation variable. Of cause the both relations must be of the same type. J Example 2.1.11 IInsert in Tutorial D: insertS m a l l P i z z a Pizza whereD i ameter = 1 J Example 2.1.12 IInsert in SQL: insert intoS m a l l P i z z a select* fromPizza where = 1D i ameter Updating tuples in a relation of a relation variable The update operation on relations is introduced by theupdatekeyword, followed by target the relation variable, followed by an optional qualification clause introduced bywherefollowed by an boolean expression which is evaluated for each tuple in the relation of the target relation variable, followed by a list of attribute value assignments meant to do per tuple. If the optional boolean expression is stated the corresponding tuples, attributes are updated only if it evaluates to true. J Example 2.1.13 IUpdate in in Tutorial D: updatePizza wherePrice < 2 ( Price := Price * 1.5) J Example 2.1.14 IUpdate in in SQL: updatePizza setPrice = Price * 1 ,5 wherePrice < 2 Deleting tuples in a relation of a relation variable The delete operation on relations is introduced by thedeletekeyword, followed by target the relation variable, followed by an optional qualification clause introduced bywherefollowed by an boolean expression which is evaluated for each tuple in the relation of the target relation variable. If the optional boolean expression is stated, the corresponding tuples are deleted only if it evaluates to true. J Example 2.1.15 IDelete in in Tutorial D: deletePizza wherePrice < 2

6

J Example 2.1.16 IDelete in in SQL: delete fromPizza wherePrice < 2 2.2 Query Operators

2 Tutorial D

2.2.1 Projection A projection is a unary operation on a relation, written asπ a 1 ,,a n (R), wherea 1 , ,a n is a set of attribute names. The result of such projection is defined as the set, that is obtained when all tuples inRare restricted to the seta 1 , ,a n . Relational algebra π Name,Surname (EMPLOY EES)

In Tutorial D the a projection may be applied to any expression that evaluates to an relation by appending an attribute reference list in braces. The tuples in the relation are restricted to the attributes in the list. Alternative the keywordall butmay stated at the beginning of the list, and the tuples in the relation are restricted to their attributes not in the list. This is more compact then the corresponding SQL statement and less confusing. Why is the projection in SQL done by mention the columns after the word select? Okay, the SQL statement is derived from a English sentence. Tutorial D E M P L O Y E E S { Name , Salary } E M P L O Y E E S {all but }D e p a r t m e n t

SQL selectyrale,SaNam fromE M P L O Y E E S 2.2.2 Selection A selection is a unary operation on a relation, written asσ φ (R), whereφis a propositional formula consisting of atoms and the logical operators∧(and),∨(or) and¬(negation). The result contains all tuples fromR, for whichφholds. Relational algebra σ Salary>5000 (EMPLOY ESS) In Tutorial D the selection may be applied to any expression that evaluates to an relation by appending the keywordwhere, followed by an boolean expression which is evaluated for each

7

2 Tutorial D

tuple. If the boolean expression evaluates to true the corresponding tuple are removed from the result, pretty similar to SQL. Tutorial D E M P L O Y E E SwhereSalary > 5000

SQL select* fromE M P L O Y E E S whereSalary > 5000 2.2.3 Join The natural join is a binary operator on relations, that is written as (R./S), whereRandSthe are relations. The result of the natural join is the set of all combinations of tuples inRandS, that are equal on their common attribute names. In caseRandShave no common attribute name the natural join degenerates to a cartesian product. Relational algebra EMPLOY EE✶MANAGERS There are two kinds of join operators in Tutorial D performing a natural join. A dyadic and a n-adic join. The dyadic join is denoted by the keywordjoinin infix notation and takes two expressions that evaluate to a relation each. The n-adic join is denoted by the keywordjoin inprefixnotation,followedbyanlistofexpressionsthatevaluatetorelationsinbraces.To perform a natural join on relations containing no common attribute names, the rename operator, which is discussed next, has to be invoked. Tutorial D E M P L O Y E E S join MANA G E R S join { EMPLOYEES , M A N A G E R S }

SQL select* fromE M P L O Y E E Snatural joinM A NAGERS select* fromSRMAS,GENAPLEMEEOY where = M A N A G E R S . D e p a r t m e n tE M P L O Y E E S . D e p a r t m e n t 2.2.4 Rename A rename is a unary operation on a relation, written asρ ab (R), where the result is identical to R except that the attribute named b is named a in the result. It is simply used to rename the attribute of a relation.

8

Relational algebra

Tutorial D

SQL

2 Tutorial D

ρ EmpNameName (EMPLOY ESS)

E M P L O Y E E S rename ( Name as EmpName )

selectNameasEmpName , fromE M P L O Y E E S ;

...

9