Transcript pascal-r

Some High Level Language
Constructs for Data of Type
Relation
By Joachim W. Schmidt
Hamburg University,
ACM Trans. on Database Systems, 77
Language Data Types
TYPE
employeeRecord =
record
employeeNumber, employeeStatus: integer,
employeeName: string;
Ordered set of
end;
records of the
employeeRelation =
same type
relation <employeeNumber> of
employeeRecord;
Ordered subset of the
VAR
record fields that
employee: employeeRecord;
uniquely identify a
record in a relation
employees: employeeRelation;
Altering Relations Operations
• Suppose that R1 and R2 are of the same type.
R1, R2: Relation<SomeKey> of SomeRecord;
• R1 :+ R2
– R1 ← R1 U R2 (Records in R1 take precedence)
• R1 :- R2
– R1 ← R1 \ R2
• R1 :& R2
– Replacing in R1 all the records whose key occur in a record of
R2
• R1 := R2
– R1 ← R2 Relation assignment
Elementary Retrieval Operation
• rel↑
– Implicitly declared buffer to contain retrieval operation
result
– Baggage from Pascal brain damaged files…
• low(rel)
– Assigns to rel↑ the record with the lowest key value
• next(rel)
– Assigns to rel↑ the record with the next key
• aor(rel)
– Boolean function that returns true when all of the
records have been iterated (all of relation)
Repetition Statement - foreach
iterates over a relation in an arbitrary order
Implicit declaration of
begin
control variable E with
type employeeRecord
result := [];
foreach E
Range
relation
in employees
do
if E.employeeStatus = 2 then
result += [E]
end
statement
Nested foreach
type
lectureRec = record
emplyeeNum, courseNum, time : integer;
dayOfWeek, room : string end;
lectureRel = relation <emplyeeNum, courseNum, dayOfWeek>
of lectureRec;
var
timeTable : lectureRel;
begin
result := [];
foreach E in employees do
foreach L in timeTable do
if (E.employeeNum = L.employeeNum)
and (L.dayOfWeek = ‘Friday’)
then result :+ [E];
end.
Quantified Predicates
• Motivation: a condition applied to an entire relation.
• Syntax:
<quantifier> ::= some | all
< logical expression > ::= … | <quantifier> <control record variable>
in <range relation variable>
(<logical expression>)
Predicates can be nested
• The user does not have to add implicit exit
• Implementation can parallelize the record processing
Using Predicates
begin
foreach E in employees do
if
some L in timeTable
((E.employeeNum = L.employeeNum)
and (L.dayOfWeek = 'friday'))
then
result :+ [E]
end
Nested Predicates Example
type
courseRec = record courseNum, courseLvl : integer,
courseName : string end;
courseRel = relation <courseNum> of courseRec;
var
courses : courseRel;
begin
result := [];
foreach E in employees do
if all L in timeTable
((E.employeeNum != L.employeeNum) or
some C in courses
((L.courseNum = C.courseNum)
and
(C.courseLvl = 1)))
then result :+ [E];
end
Sub relations
• Just like “SELECT *” in SQL…
• Motivation:
– All the above examples had constructed a relation by:
• Iterating over the source relation sequentially
• Testing a condition
• Adding each record that satisfies the condition
– It can be simplified and optimized by using a
construction of sub relation
• Introducing the ‘each’ construct for relations
Using ‘each’ Construct
Control
variable
begin
result1 := [each E in employees:
E.employeeStatus = 2];
Range
relation
Logical
expression
result2 := [each E in employees:
some L in timeTable
((E.employeeNum = L.employeeNum) and
(L.dayOfWeek = 'Friday')))];
end.
General Relation Constructor
• Previous ‘each’ construct was limited to one
relation only
• The general form can construct a relation from
several other relations
– Several relations are tested together, each has its
own control variable
– The result relation fields can be taken from any of
those relation fields
– The logical expression to add records to the result
relation can be made of fields from any relation
Using General Relation Constructor
type
publicationRec = record title: string,
year, employeeNum: integer end;
publicationRel = relation <title, emplyeeNum> of
publicationRec
var
Target
publications: publicationRel;
component
begin
list
result := [each (E.employeeName, P.title, P.year)
for E, P
in employees,publications:
Range
relation
list
(P.employeeNum = E.employeeNum) and
some L in timeTable
(E.employeeNum = L.employeeNum)]
end.
Control
variable list
Logical exp
Advantages
• Very high level language constructs
– The user does not program a procedure but
gives a declaration of the required result
properties only
• Highly readable
– The entire code for achieving the result
relation is at one place
• Can be implemented efficiently
Implementation
• These constructs were implemented in
PASCAL compiler
– Compiler was modified to accept the syntax
– Run time library was added to handle the
execution of the new constructs
– Database counts as an external variable
• Similar to PASCAL files
• Can be connected to via a parameter in the
program header
Database in PASCAL-R
program DBSample(DB)
type
…
var
DB:database employees:empRel,
timeTable:lectureRec,… end
begin with DB do
…
end.
Relational Algebra Operations
in PASCAL-R
•
Selection (σ) - Selects a subset of rows
– [each Row in Relation: condition]
•
Cartesian-product (X) Allows us to combine two relations.
– [each (R1cols, R2cols) for R1rec, R2rec in R1, R2:
true]
•
Projection (π) - Deletes unwanted columns from relation.
– [each (resultColumns) for someRecord in
someRelation: true]
•
Set-difference (-) Tuples in R1, but not in R2.
–
•
R1 :- R2
Union (Y) Tuples in R1 or in R2.
–
R1 :+ R2
Conclusions
• The expressive power of the proposed
constructs is satisfactory
• It did not look into some of the database
traditional problems
– Simultaneous access
– Data integrity
• Type checking is possible, but requires the
database schema to be known at compile
time and remain unchanged in runtime
Later Publication in This Area
• Programming languages extension to support
database manipulations
– ASTRAL, extension of SIMULA (I978)
– Modula/R (1983)
• New programming languages designed to
support database manipulations
– PLAIN (1979), RIGEL (1979), Adaplex (1983)
• PASCAL-R development
– DBPL - A successor to Pascal/R and Modula/R
(Schmidt ,1988)