[SOLVED] CS SQL database Relational Operations

Relational Operations

>>
Relational Operations

DBMS Architecture (revisited)

Relational Operations

Cost Models

Query Types

COMP9315 21T1 Relational Operations [0/11]

>>
DBMS Architecture (revisited)

Implementation of relational operations in DBMS:

COMP9315 21T1 Relational Operations [1/11]

<< >>
Relational Operations

DBMS core = relational engine, with implementations of

selection, projection, join, set operations

scanning, sorting, grouping, aggregation,

In this part of the course:
examine methods for implementing each operation

develop cost models for each implementation

characterise when each method is most effective

Terminology reminder:
tuple = collection of data values under some schema record

page = block = collection of tuples + management data = i/o unit

relation = table file = collection of tuples

COMP9315 21T1 Relational Operations [2/11]

<< >>
Relational Operations (cont)

In order to implement relational operations the low-levels of the system provides:

Relation openRel(db,name)
get handle on relation name in database db

Page request_page(rel,pid)
get page pid from relation rel, return buffer containing page

Record get_record(buf,tid)
return record tid from page buf

Tuple mkTuple(rel,rec)
convert record rec to a tuple, based on rel schema

COMP9315 21T1 Relational Operations [3/11]

<< >>
Relational Operations (cont)

Example of using low-level functions

// scan a relation Emps
Page p;// current page
Tuple t; // current tuple
Relation r = relOpen(db,Emps);
for (int i = 0; i < nPages(r); i++) { p = request_page(rel,i); for (int j = 0; j < nRecs(p); j++)t = mkTuple(r, get_record(p,j));… process tuple t … } }COMP9315 21T1 Relational Operations [4/11]<< >>
Relational Operations (cont)

Two dimensions of variation:

which relational operation (e.g. Sel, Proj, Join, Sort, )

which access-method (e.g. file struct: heap, indexed, hashed, )

Each query method involves an operator and a file structure:
e.g. primary-key selection on hashed file

e.g. primary-key selection on indexed file

e.g. join on ordered heap files (sort-merge join)

e.g. join on hashed files (hash join)

e.g. two-dimensional range query on R-tree indexed file

We are interested in cost of query methods (and insert/delete operations)

COMP9315 21T1 Relational Operations [5/11]

<< >>
Relational Operations (cont)

SQL vs DBMS engine

select from R where C
find relevant tuples (satisfying C) in file(s) of R

insert into R values()
place new tuple in some page of a file of R

delete from R where C
find relevant tuples and remove from file(s) of R

update R set where C
find relevant tuples in file(s) of R and change them

COMP9315 21T1 Relational Operations [6/11]

<< >>
Cost Models

An important aspect of this course is

analysis of cost of various query methods

Cost can be measured in terms of
Time Cost: total time taken to execute method, or

Page Cost: number of pages read and/or written

Primary assumptions in our cost models:
memory (RAM) is small, fast, byte-at-a-time

disk storage is very large, slow, page-at-a-time

COMP9315 21T1 Relational Operations [7/11]

<< >>
Cost Models (cont)

Since time cost is affected by many factors

speed of i/o devices(fast/slow disk, SSD)

load on machine

we do not consider time cost in our analyses.

For comparing methods, page cost is better

identifies workload imposed by method

BUT is clearly affected by buffering

Estimating costs with multiple concurrent ops and buffering is difficult!!

Addtional assumption: every page request leads to some i/o

COMP9315 21T1 Relational Operations [8/11]

<< >>
Cost Models (cont)

In developing cost models, we also assume:

a relation is a set of r tuples, with average tuple size R bytes

the tuples are stored in b data pages on disk

each page has size B bytes and contains up to c tuples

the tuples which answer query q are contained in bq pages

data is transferred diskmemory in whole pages

cost of diskmemory transfer Tr/w is very high

COMP9315 21T1 Relational Operations [9/11]

<< >>
Cost Models (cont)

Our cost models are rough (based on assumptions)

But do give an O(x) feel for how expensive operations are.

Example rough estimation: how many piano tuners in Sydney?

Sydney has 4 000 000 people

Average household size 3 1 300 000 households

Lets say that 1 in 10 households owns a piano

Therefore there are 130 000 pianos

Say people get their piano tuned every 2 years (on average)

Say a tuner can do 2/day, 250 working-days/year

Therefore 1 tuner can do 500 pianos per year

Therefore Sydney would need 130000/2/500 = 130 tuners

Actual number of tuners in Yellow Pages = 120

Example borrowed from Alan Fekete at Sydney University.

COMP9315 21T1 Relational Operations [10/11]

<< Query Types TypeSQLRelAlga.k.a.Scanselect * from RR-Projselect x,y from RProj[x,y]R-Sortselect * from Rorder by x Sort[x]RordSel1select * from Rwhere id = k Sel[id=k]RoneSelnselect * from Rwhere a = k Sel[a=k]R-Join1select * from R,Swhere R.id = S.r R Join[id=r] S- Different query classes exhibit different query processing behaviours.COMP9315 21T1 Relational Operations [11/11]Produced: 27 Feb 2021