Week 5 : Query Processing

Question 1

What are the query processing steps

Answer 1

query decomposition - scanning, parsing, validation

query optimization - choosing a suitable execution strategy to retrieve the query result from the internal database file

query code generation - used to execute the strategy

runtime database processing - runs complied of interpreted code to give the query result and generates error messages for runtime errors.

Question 2

What are query trees?

Answer 2

A diagram that contains leaf nodes (input relations) and internal nodes (relational algebra operations).

Question 3

What is a Query Optimizer?

Answer 3

The optimizer tries to produce the best execution plan possible for a SQL statement.

Question 4

What is access cost?

Answer 4

The time taken to retrieve the required data from a disk and depends on the method used for accessing the records in the file.

Question 5

What is a Linear Search?

Answer 5

A sequential searching algorithm.

Question 6

What is an Index Search?

Answer 6

A data structure that provides quick a look up of data in column.

Question 7

What is a B+ tree?

Answer 7

A self balancing tree structure that contains root, internal and leaf nodes and organizes data for efficient searching, insertion and deletion.

Question 8

What are the advantages of an Index Search?

Answer 8

• improves search time

-the DBMS automatically creates an index on the PK of each table

• the user can specify additional index using ‘CREATE INDEX’

Question 9

What are the disadvantages of an index search?

Answer 9

-the dbms does work to maintain indexes

• the systems has to insert/delete rows in all indexes

-it slows down inserts, updates and deletes

Question 10

What happens in a nested loop join?

Answer 10

It loops through the rows in one table then scans the second table to find matching rows. It’s efficient for small, unsorted tables.

Question 11

What happens in an Index Join?

Answer 11

The query processor uses an index on the column that joins tables in increase search speed. (key-value)

Question 12

What is a hash join?

Answer 12

This requires one pass through the file. It two phases are

build - the server builds an in-memory hash table where rows from one of the inputs are stored and creates a hash table key

probe - the server searches for matching rows in the hash table.

Question 13

What are the advantages of a hash table?

Answer 13

• effective for large volumes of data with unsorted inputs and no useful indexes

-useful when there are no suitable join indices

• a smaller files uses the build phases/filter to reduce the number of rows

Question 14

What are the disadvantages of a hash join?

Answer 14

they require a significant amount of memory

Question 15

What is a merge join?

Answer 15

It combines data from two tables that have been sorted on a specific join key.

Question 16

What are the steps of a merge join?

Answer 16

-sort the input tables

• merge operation
• comparison and matching
• repeat and advance
• result generation

Question 17

What is Hashing?

Answer 17

A technique used to provide rapid data access to data records based on a unique identifier called a hash key/ hash code.

Question 18

How does hashing work?

Answer 18

A new data record is inserted into the database and it’s key is passed through the hash function, which produces a hash value.