Page 208 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 12: Query Processing and Optimization

(b) Secondary index, comparison: For the queries of the type that use comparison on Notes
secondary index value a value, then the index can be used to find first index entry
which is greater than that value, scan index sequentially from there till the end and
also keep finding the pointers to records.
For the type query just scan leaf pages of index, also keep finding pointers to
records, till first entry is found satisfying the condition.
In either case, retrieving records that are pointed to, may require an I/O for each record.

Notes Linear file scans may be cheaper if many records are to be fetched.

12.2.3 Implementation of Complex Selections

Conjunction: Conjunction is basically a set of AND conditions.

1. Conjunctive selection using one index: In such a case, select any algorithm given earlier on
one or more conditions. If possible, test other conditions on these tuples after fetching
them into memory buffer.
2. Conjunctive selection using multiple-key index: Use appropriate composite (multiple-
key) index if they are available.

3. Conjunctive selection by intersection of identifiers requires indices with record pointers.
Use corresponding index for each condition, and take the intersection of all the obtained
sets of record pointers. Then fetch records from file if, some conditions do not have
appropriate indices, test them after fetching the tuple from the memory buffer.

Task Discuss the uses of hash key.

12.2.4 Disjunction

Specifies a set of OR conditions.
Disjunctive selection by union of identifiers is applicable if all conditions have available indices,
otherwise use linear scan. Use corresponding index for each condition, take the union of all the
obtained sets of record pointers, and eliminate duplicates, then fetch data from the file.

12.2.5 Negation

Use linear scan on file. However, if very few records are available in the result and an index is
applicable on attribute, which is being negated, then find the satisfying records using index and
fetch them from the file.

12.3 Sorting

Now we need to take a look at sorting techniques that can be used for calculating costing. There
are various methods that can be used in the following ways:
1. Use an existing applicable ordered index (e.g., B+ tree) to read the relation in sorted order.

LOVELY PROFESSIONAL UNIVERSITY 201