CS计算机代考程序代写 2021/4/28 Selection Overview

2021/4/28 Selection Overview
Selection Overview
Varieties of Selection Implementing Select Efciently
>>
COMP9315 21T1 ♢ Selection ♢ [0/6]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
1/8

2021/4/28 Selection Overview
❖ Varieties of Selection Selection: select * from R where C
lters a subset of tuples from one relation R based on a condition C on the attribute values
We consider three distinct styles of selection: 1-d(onedimensional) (conditionusesonly1attribute) n-d(multi-dimensional) (conditionuses>1attribute) similarity (approximatematching,withranking)
Each style has several possible le-structures/techniques.
COMP9315 21T1 ♢ Selection ♢ [1/6]
∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
2/8

2021/4/28 Selection Overview
<< ∧ >>
❖ Varieties of Selection (cont) Selection returns a subset of tuples from a table
rq = number of tuples that match query q
bq = number of pages containing tuples that match query q
Inthediagram,rq=8, bq=5
COMP9315 21T1 ♢ Selection ♢ [2/6]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
3/8

2021/4/28 Selection Overview
❖ Varieties of Selection (cont) Different categories of selection queries:
one…querieswithatmost1result… 0≤rq≤1, 0≤bq≤ 1
typically, equality test on primary key attribute, e.g.
select * from R where id = 1234
pmr…partialmatchretrieval… 0≤rq≤r, 0≤bq≤b+bov
conjunction of equality tests on multiple attributes, e.g. select * from R where age=65 (1-d)
select * from R where age=65 and gender=’m’ (n- d)
COMP9315 21T1 ♢ Selection ♢ [3/6]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
4/8

2021/4/28 Selection Overview
❖ Varieties of Selection (cont) More categories of selection queries:
rng…rangequeries… 0≤rq≤r, 0≤bq≤b+bov conjunction of inequalities, on one or more attributes,
e.g.
select * from R where age≥18 and age≤21 (1-d)
select * from R where 18≤age≤21 and 160≤height≤190 (n-d)
pat…pattern-basedqueries… 0≤rq≤r, 0≤bq≤b+bov string-based matching using like or regular
expressions
select * from R where name like ‘%oo%’ select * from R where name ~ ‘^Smi’
COMP9315 21T1 ♢ Selection ♢ [4/6]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
5/8

2021/4/28 Selection Overview
❖ Varieties of Selection (cont) More categories of selection queries:
sim…similaritymatching…intheory,rq=r …everything matches to some degree
uses “similarity” measure (0 ≤ sim ≤ 1, 0=different, 1=identical)
select * from Images where similar to SampleImage
results are ranked by sim value, from most to least similar
can become a lter via
threshold … only items where sim ≥ min similarity top-k … k items with highest similarities
We focus on one, pmr and rng queries, but will discuss others
COMP9315 21T1 ♢ Selection ♢ [5/6]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html
6/8

2021/4/28 Selection Overview
❖ Implementing Select Efciently Two basic approaches:
physical arrangement of tuples
sorting (searchstrategy)
hashing (static,dynamic,n-dimensional) additional indexing information
indexles (primary,secondary,trees) signatures (superimposed,disjoint)
Our analysis assumes 1 input buffer available for each relation.
If more buffers are available, most methods benet.
COMP9315 21T1 ♢ Selection ♢ [6/6]
<< ∧ https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html 7/8 2021/4/28 Selection Overview Produced: 6 Mar 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/selection/slides.html 8/8