Lectura 7

Lectura 7

1. CHAPTER 11 Indexing and Hashing

   • Basic Concepts Ordered indices. Based on a sorted ordering of the values. Hash indices. Based on a uniform distribution of values across a range of buckets. The bucket to which a value is assigned is determined by a function, called a hash function.
     • • Deletion time: The time it takes to delete a data item. This value includes the time it takes to find the item to be deleted, as well as the time it takes to update the index structure. • Space overhead: The additional space occupied by an index structure. Provided that the amount of additional space is moderate, it is usually worthwhile to sacrifice the space to achieve improved performance.
   • Ordered Indices To gain fast random access to records in a file, we can use an index structure. Each index structure is associated with a particular search key.
     • Dense and Sparse Indices An index entry,orindex record, consists of a search-key value and pointers to one or more records with that value as their search-key value.
   • Index Update Regardless of what form of index is used, every index must be updated whenever a record is either inserted into or deleted from the file. Further, in case a record in the file is updated, any index whose search-key attribute is affected by the update must also be updated
     • Insertion. First, the system performs a lookup using the search-key value that appears in the record to be inserted
     • Deletion. To delete a record, the system first looks up the record to be deleted.
   • Secondary Indices Secondary indices must be dense, with an index entry for every search-key value, and a pointer to every record in the file.
   • B + -Tree Index Files The main disadvantage of the index-sequential file organization is that perfor- mance degrades as the file grows, both for index lookups and for sequential scans
   • tree indices on the file. We solve the degradation problem for storing the actual records by using the leaf level of the B + -tree to organize the blocks containing the actual records. We use the B + -tree structure not only as an index, but also as an organizer for records in a file. In a B + -tree file organization,theleaf nodes of the tree store records, instead of storing pointers to records
     • B-Tree Index Files B-tree indices are similar to B The primary distinction between the two approaches is that a B-tree eliminates the redundant storage of search-key values. In the B
   • Static Hashing One disadvantage of sequential file organization is that we must access an index structure to locate data, or must use binary search, and that results in more I/O operations. File organizations based on the technique of hashing allow us to avoid accessing an index structure. Hashing also provides a way of constructing indices.
     • The distribution is uniform. That is, the hash function assigns each bucket the same number of search-key values from the set of all possible search-key values.
     • The distribution is random. That is, in the average case, each bucket will have nearly the same number of values assigned to it, regardless of the actual distribution of search-key values.
     • Hash Indices Hashing can be used not only for file organization, but also for index-structure creation. A hash index organizes the search keys, with their associated pointers, into a hash file structure.
   • Dynamic Hashing Choose a hash function based on the current file size. This option will result in performance degradation as the database grows. Choose a hash function based on the anticipated size of the file at some point in the future. Periodically reorganize the hash structure in response to file growth.
     • Data Structure Extendable hashing copes with changes in database size by splitting and coalescing buckets as the database grows and shrinks. As a result, space efficiency is retained.
   • To make a choice of file organization and indexing techniques for a relation, the implementor or the database designer must consider the following issues: Is the cost of periodic reorganization of the index or hash organization acceptable? What is the relative frequency of insertion and deletion? Is it desirable to optimize average access time at the expense of increasing the worst-case access time? What types of queries are users likely to pose?
   • Bitmap Indices Bitmap indices are a specialized type of index designed for easy querying on multiple keys, although each bitmap index is built on a single key.

2. CHAPTER 12 Query Processing

   • Query processing refers to the range of activities involved in extracting data from a database. The activities include translation of queries in high-level database
   • Measures of Query Cost There are multiple possible evaluation plans for a query, and it is important to be able to compare the alternatives in terms of their (estimated) cost, and choose the best plan.
     • 1. The response time depends on the contents of the buffer when the query begins execution 2. In a system with multiple disks, the response time depends on how accesses are distributed among disks, which is hard to estimate without detailed
   • Selection Operation In query processing, the file scan is the lowest-level operator to access data. File scans are search algorithms that locate and retrieve records that fulfill a selection condition.
     • A2 (primary index, equality on key).Foranequalitycomparisononakey attribute with a primary index, we can use the index to retrieve a single record that satisfies the corresponding equality condition.
     • A3 (primary index, equality on nonkey). We can retrieve multiple records by using a primary index when the selection condition specifies an equality comparison on a nonkey attribute
     • A4 (secondary index, equality). Selections specifying an equality condition can use a secondary index. This strategy can retrieve a single record if the equality condition is on a key; multiple records may be retrieved if the indexing field is not a key.
   • Sorting Sorting of data plays an important role in database systems for two reasons. First, SQL queries can specify that the output be sorted. Second, and equally important for query processing, several of the relational operations, such as joins, can be implemented efficiently if the input relations are first sorted.
   • Join Operation If the join attributes in a natural join or an equi-join form a key on the inner relation, then for each outer relation tuple the inner loop can terminate as soon as the first match is found.
     • We can scan the inner loop alternately forward and backward. This scanning method orders the requests for disk blocks so that the data remaining in the buffer from the previous scan can be reused, thus reducing the number of disk accesses needed.
       • Hash Join Like the merge-join algorithm, the hash-join algorithm can be used to implement natural joins and equi-joins. In the hash-join algorithm, a hash function h is used to partition tuples of both relations.
       • Hybrid Hash Join The hybrid hash-join algorithm performs another optimization; it is useful when memory sizes are relatively large, but not all of the build relation fits in memory.
   • Other Operations Other relational operations and extended relational operations— such as duplicate elimination, projection, set operations, outer join, and aggregation
     • Duplicate Elimination We can implement duplicate elimination easily by sorting. Identical tuples will appear adjacent to each other as a result of sorting, and all but one copy can be removed.
       • Projection We can implement projection easily by performing projection on each tuple, which gives a relation that could have duplicate records, and then removing duplicate records.
         • Set Operations We can implement the union, intersection,andset-difference operations by first sorting both relations, and then scanning once through each of the sorted relations to produce the result.
   • Evaluation of Expressions The obvious way to evaluate an expression is simply to evaluate one operation at a time, in an appropriate order. The result of each evaluation is materialized in a temporary relation for subsequent use. A disadvantage to this approach is the need to construct the temporary relations, which (unless they are small)
     • Implementation of Pipelining We can implement a pipeline by constructing a single, complex operation that combines the operations that constitute the pipeline.
       • 1. In a demand-driven pipeline, the system makes repeated requests for tuples from the operation at the top of the pipeline. Each time that an operation receives a request for tuples, it computes the next tuple (or tuples) to be returned, and then returns that tuple.
       • 2. In a producer-driven pipeline, operations do not wait for requests to pro- duce tuples, but instead generate the tuples eagerly

3. Nombre: Juan Manuel Figueroa Solís Carnet: 201139700 Universidad: I.T.C.R Curso: IC4302 Bases de Datos 2 Título: Lectura 6 Fecha: 23 /09 /21 Profesor:Erick Hernández Bonilla Grupo: 40

4. CHAPTER 13 Query Optimization

   • Query optimization is the process of selecting the most efficient query-evaluation plan from among the many strategies usually possible for processing a given query, especially if the query is complex.
   • Transformation of Relational Expressions A query can be expressed in several different ways, with different costs of evaluation. In this section, rather than take the relational expression as given, we consider alternative, equivalent expressions.
     • Join Ordering A good ordering of join operations is important for reducing the size of temporary results; hence, most query optimizers pay a lot of attention to the join order.
   • Estimating Statistics of Expression Results The cost of an operation depends on the size and other statistics of its inputs. Given an expression such as a ✶ (b ✶ c) to estimate the cost of joining a with (b ✶ c), we need to have estimates of statistics such as the size of b ✶ c.
     • Selection Size Estimation The size estimate of the result of a selection operation depends on the selection predicate.
       • Join Size Estimation Estimating the size of a natural join is somewhat more complicated than estimating the size of a selection or of a Cartesian product. Let r (R)ands(S)be relations.
         • If R ∩ S =∅— that is, the relations have no attribute in common—then r ✶ s is the same as r × s, and we can use our estimation technique for Cartesian products.
         • If R ∩ S is a key for R, then we know that a tuple of s will join with at most one tuple from r . Therefore, the number of tuples in r ✶ s is no greater than the number of tuples in s.
         • The most difficult case is when R ∩ S is a key for neither R nor S.Inthis case, we assume, as we did for selections, that each value appears with equal probability.
   • Selection Size Estimation The size estimate of the result of a selection operation depends on the selection predicate.
   • Choice of Evaluation Plans Generation of expressions is only part of the query-optimization process, since each operation in the expression can be implemented with different algorithms.
     • Cost-Based Optimization with Equivalence Rules The join order optimization technique we just saw handles the most common class of queries, which perform an inner join of a set of relations.
       • Optimizing Nested Subqueries** SQL conceptually treats nested subqueries in the where clause as functions that take parameters and return either a single value or a set of values (possibly a
   • Materialized Views** When a view is defined, normally the database stores only the query defining the view. In contrast, a materialized view is a view whose contents are computed and stored.
     • The set operation intersection is maintained as follows: Given materialized view v = r ∩ s, when a tuple is inserted in r we check if it is present in s,andifsowe add it to v.
   • Advanced Topics in Query Optimization** There are a number of opportunities for optimizing queries, beyond those whave seen so far.
     • Join Minimization When queries are generated through views, sometimes more relations are joined than are needed for computation of the query
       • Multiquery Optimization and Shared Scans When a batch of queries are submitted together, a query optimizer can potentially exploit common subexpressions between the different queries, evaluating them once and reusing them where required.
   • Given a query, there are generally a variety of methods for computing the answer. It is the responsibility of the system to transform the query as entered by the user into an equivalent query that can be computed more efficiently.

Images and files in the map