Flashcards
SCC 201 - Access Routines
Cards in this deck (26)
- 1Describe the linear search (brute force) access routine?S1 Linear search: retrieve every record in the file and test the attribute values satisfy the selection condition.
- 2Describe the binary search access routine?S2 Binary search : condition involves
equality comparison with key attribute by
which the file is ordered. - 3Describe the primary index/hashing routine?S3 Primary index / hashing: condition
involves equality comparison with search
field attribute. - 4S4 Primary index retrieves multiple records if what?S4 Primary index : retrieve multiple records; if the condition involves
>, >=, < , <= on the search field (i.e. Age > 36) then find record satisfying equality condition (i.e. Age = 36) and then retrieve all subsequent records in the
(ordered) file. - 5State the access path for clustering index?Clustering index on search field
- 6Describe the S5 clustering index?equality
comparison on a non-key attribute (i.e. it
can occur more than once). - 7Describe the S6 secondary index (B+ tree)?equality and others; multiple records.
– This operates in much the same way as S4.
– Use the index to find the required record(s) in the main file. - 8Define the effect of operators <, > , <= , >=< Find first occurrence of value. Retrieve all preceding records.
> Find last occurrence of value. Retrieve all subsequent records.
<= Find last occurrence of value. Retrieve it, and all preceding records.
>= Find first occurrence of value. Retrieve it, and all subsequent records - 9What could the leaf node be pointing to in a B+ tree?The pointers from the leaf nodes in this
example could be pointing to the record
within a main file block (as shown in the
diagram) or to a block that contains the
record. - 10Boolean expressions involving the AND operator of the general format:(simple condition) AND (simple condition) AND ..
- 11Can you describe S7?If we can use one of the methods S2-S6 for an attribute in one of the simple conditions, do so; examine the records
thus retrieved to see if they meet the other conditions.
• This is like using an access routine to generate a sub-set of records which we can then examine, one after the other (brute force). - 12Can you describe S8 Composite index?if two or more attributes involved in
equality conditions also appear in a composite index, use the index directly.
• See the appendix for a brief description of composite index. - 13Can you describe S8 Intersection of record pointers?if secondary indices are available on all the
fields involved in equality conditions and
the indices include record pointers (i.e.
inverted files) -- retrieve a set of record
pointers from each index involved and
take the intersection. - 14Query optimisation for select is needed with what and what access path should be chosen?Query optimisation for select is needed
with conjunctive conditions when different simple conditions offer an access path.
• The access path that results in the fewest record retrievals should be chosen. - 15Little can be done to optimise what type of conditions?• Little can be done to optimise; if any one
of the simple conditions involve an
attribute with no access path, we must use
brute force - 16What can disjunctive conditions be known as?OR
- 17Can you describe J1 Nested (inner-outer) loop (brute force) ?for every record t in R (outer loop), retrieve
every record s from S (inner loop) and test
join condition t[A] = s[B] - 18Can you describe J2 access structure?if an index / hash exists for one of the two join attributes, say B of S, retrieve every record t in R, one at a time, and then use the access structure to
retrieve all the matching records s from S that satisfy s[B] = t[A].
• J2 eliminates one of the loops. - 19How the J2 join example work?look at slides 34
- 20Can you describe J3 Sort-merge?if the records of R and S are ordered
by the join attributes A and B respectively, we can scan the files in the order of the join attributes.
• This is the most efficient join algorithm; the records of each file are scanned only once. - 21Can you describe the J4 hash-join?the records (or record pointers) of R
and S are hashed to the same hash file using the same hash function on the attributes R[A] and S[B] as
hash keys.
A single pass through each file fills up the hash buckets. Each bucket is then examined for records from R and S that match to produce the join result. - 22If includes a key of R then what?If includes a key of R then the result has the same number of tuples as R but only the attributes given in .
- 23If doesn't include a key of R, what happens?If not, then we must detect duplicate tuples and eliminate them. Two possible techniques are :
– sort the result and then eliminate duplicates (which will now be consecutive tuples)
– hashing : hash each projected tuple, check it against those already in the bucket, and discard if a double. - 24What is a composite index based on?A composite (or concatenated) index is one based on more than one attribute. It can be clustering or not.
- 25Advantages of composite index rather than single-attribute indexing?Consider the query “how many people are there with last name ‘Smith’ and first name ‘John’”?
– A query on all attributes of a composite index will likely return far fewer records than a query on only some of
those attributes. - 26How are telephone directories organised?They are organised using composite attributes?
Information
- Description
- Flashcards on SCC 201 - Access Routines, created by Ayo Olutobi on 12/04/2017.
- Created by
- Ayo Olutobi
- Views
- 3
- Rating