Lesson 1: Query Processing

1 Query Processing 1.1 Introduction In this lesson, we shall utilize some simple databases to illustrate the concepts of query processing. Class Exercise 1: Test your proficiency in designing, implementing, and using a database by recalling the skills gained during the previous course. The following are the steps involved in designing and implementing a database, given some requirement. i. ii. iii. iv. v. Requirements Analysis Conceptual Model Normalization ERD Database Schema Objective: Create a database based on a brief set of requirements provided. “In Meru University of Science and Technology, there are various schools (eg. SBE, SAFS etc.). Each school has one or more departments (eg. CS, IT, Nursing etc). Each department has its programs (eg. BCT, BIT, BCS, BEd. Etc). When a student is admitted into the University, he/she is enrolled into a program.” Use the above information to; a) Requirements analysis - Summarize the above case into (entities, relationships, cardinalities, and attributes) b) Translate the above requirements into a conceptual model c) Normalize the conceptual model in b (above) d) Translate the conceptual model into an ERD e) Translate the ERD to a physical model (Create a database) While making reference to the database schema generated after completing the above exercise, test your basic SQL proficiency by attempting to write SQL query commands to; i) List the names and email of all students ii) List the names and email of all students whose names begin with ‘MA’ iii) List the names and email of all students registered for ‘BBIT’ 1 iv) List the names and email of all students from IT department v) List the names and email of all students taking programs from IT and Nursing departments. vi) List the names, email of all students who have not enrolled to any program. vii) List the names of programs with no students enrolled. Class Exercise 2: Library database. The purpose of the database is to facilitate staff members to issue books to the library patrons. The three major entities (table) are:    Staff – staff members of the library patrons – registered users of the library. Books – Library inventory or items How are these entities related? In this problem we need to know which books are issued to which patrons and by whom (staff). Thus, the relationship “issues/issued” becomes an obvious and an important relationship in this simple problem. Normalizing the design, the relationship is represented using a new entity, “issues”. Finally, the resulting EntityRelationship Diagram is as follows; While making reference to the ERD above, test your basic SQL proficiency by attempting to write commands to; i. List the names and email of all patrons who have ever been issued with a book authored by ‘Stephen Mutua’; 2 ii. List the name of patrons, name of staff, and the title of all books issued on 202110-07. iii. List the names and email of staff who did not issue any book on 2021-10-07 1.2 What is Query Processing The activities involved in retrieving data from the database are called as query processing. The aims of query processing are to transform a query written in a high-level language typically SQL, into a correct and efficient execution strategy expressed in a low-level language (implementing relational algebra), and to execute the strategy to retrieve the required data. An important aspect of query processing is Query Optimization. The activity of choosing an efficient execution strategy for processing a query is called as query optimization. As there are many equivalent transformations of the same high-level query, the aim of query optimization is to choose the one that minimizes the resource usage. 1.3 How is a query is Executed? 1. The scanner identifies the language components (tokens) in the text of the query, while the parser checks the correctness of the query syntax. 2. The query is validated (by accessing the system catalog) to ascertain whether the attribute names and relation names are valid. 3. An internal representation (tree or graph) of the query is created. 4. The query is parsed and then presented to a query optimizer. 5. The optimizer generates alternative plans and chooses the plan with the least estimated cost. 1.4 Basic Query Operations A query basically consists of following operations, which can be analyzed separately.  Selection Operation -WHERE   Join Operation -JOIN Projection Operation -SELECT   Set Operations -SUBQUERY Cartesian product Selection Operation A query can have condition to filter the required data. For that selection it may use several ways to search for the data. The following are some of the ways to search: – File Scan – Index Scan File Scan 3 A number of search algorithms are possible for selecting the records from a file. The selection of records from a file is known as file scan, as the algorithm scans the records of a file to search for and retrieve records that satisfy the selection condition. Index Scan If the search algorithm uses an index to perform the search, then it is referred as Index Scan. – Linear Search: This is also known as Brute Force method. In this method, every record in the file is retrieved and tested as to whether its attribute values satisfy the selection condition. – Binary Search: If a selection condition involves an equality comparison on a key attribute on which the file is ordered, a binary search can be used. Binary search is more efficient than linear search. – Primary Index Single Record Retrieval: If a selection condition involves an equality comparison on a primary key attribute with a primary index, we can use the primary index to retrieve that record. – Secondary Index: This search method can be used to retrieve a single record if the indexing field has unique values (key field) or to retrieve multiple records if the indexing field is not a key. This can also be used for comparisons involving <, >, <= or >= Primary Index Multiple Records Retrieval: A search condition uses comparison condition <, >, etc. on a key field with primary index is known as Primary index multiple records retrieval. – Clustering Index: If the selection condition involves an equality comparison on a nonkey attribute with a clustering index, we can use that index to retrieve all the records satisfying the condition. Conjunctive Condition If the selection condition of the SELECT operation is a conjunctive condition (a condition that is made up of several simple conditions with the AND operator), then the DBMS can use the following additional methods to perform the selection. Conjunctive selection: If an attribute in any single simple condition in the conjunctive condition has an access path that permits use of binary search or an index search, use that condition to retrieve the records and then check if that record satisfies the remaining condition. Conjunctive selection using composite index: If two or more attributes are involved in equality conditions in the conjunctive condition and a composite index exists on the combined fields we can use the index. 4