Unit3 - Subjective Questions

Aggregate functions perform a calculation on a set of values and return a single scalar value. The five basic aggregate functions are:

• COUNT(): Returns the number of rows or non-NULL values in a specified column.
• SUM(): Returns the sum of all values in a numeric column.
• AVG(): Returns the average value of a numeric column.
• MIN(): Returns the minimum value in a given column.
• MAX(): Returns the maximum value in a given column.

Effect of GROUP BY:
When used without a GROUP BY clause, an aggregate function calculates the result for the entire table. However, when combined with a GROUP BY clause, the table is divided into groups based on the values in the specified column(s). The aggregate function is then applied to each group individually, returning a single value per group rather than a single value for the entire table.

Both WHERE and HAVING are used to filter records, but they operate at different stages of query execution.

• WHERE Clause:
  • Filters rows before any grouping occurs.
  • Cannot contain aggregate functions (e.g., WHERE SUM(salary) > 50000 is invalid).
  • Applied to individual rows.
• HAVING Clause:
  • Filters groups after the GROUP BY clause has been applied.
  • Can and usually does contain aggregate functions.
  • Applied to groups of rows.

Example:
sql
SELECT department_id, SUM(salary)
FROM employees
WHERE status = 'Active'
GROUP BY department_id
HAVING SUM(salary) > 100000;

Here, WHERE filters for active employees first, then GROUP BY groups them by department, and finally HAVING filters out departments where the total salary is not greater than 100,000.

Outer joins extend the functionality of Inner Joins by returning not only the matched rows but also the unmatched rows from one or both tables. The missing values from the other table are filled with NULL.

1. LEFT OUTER JOIN (or LEFT JOIN):

• Returns all records from the left table, and the matched records from the right table.
• If there is no match, the result will contain NULL for the right table's columns.
• Syntax: SELECT columns FROM table1 LEFT JOIN table2 ON table1.id = table2.id;

2. RIGHT OUTER JOIN (or RIGHT JOIN):

• Returns all records from the right table, and the matched records from the left table.
• If there is no match, the result will contain NULL for the left table's columns.
• Syntax: SELECT columns FROM table1 RIGHT JOIN table2 ON table1.id = table2.id;

3. FULL OUTER JOIN (or FULL JOIN):

• Returns all records when there is a match in either the left or the right table.
• It essentially combines the results of both LEFT and RIGHT joins. Unmatched rows from both tables will appear in the result set with NULLs in the corresponding columns.
• Syntax: SELECT columns FROM table1 FULL OUTER JOIN table2 ON table1.id = table2.id;

Here are the differences between the three join types:

• INNER JOIN:
  • Returns only the rows that have matching values in both tables based on an explicit join condition specified in the ON clause.
  • It requires a condition to evaluate equality or other comparisons.
• NATURAL JOIN:
  • An implicit join based on all columns in the two tables that have the same name and compatible data types.
  • It automatically equates these columns and does not require (or allow) an ON clause.
  • It only keeps one copy of the matched columns in the result.
• CROSS JOIN:
  • Returns the Cartesian product of the two tables.
  • Each row from the first table is combined with every row from the second table.
  • It does not use a join condition (no ON clause). If Table A has rows and Table B has rows, the result has rows.

Set operators are used to combine the result sets of two or more SELECT statements into a single result set.

• UNION: Combines the results of two queries and removes duplicate rows.
• INTERSECT: Returns only the distinct rows that are output by both queries.
• EXCEPT (or MINUS): Returns distinct rows from the first query that are not present in the second query's result set.

Conditions for Union-Compatibility:
For two query results to be combined using set operators, they must be union-compatible, which requires:

1. Same number of columns: Both SELECT statements must return the same number of columns.
2. Compatible data types: The corresponding columns in both SELECT statements must have compatible data types in the same order.

Differences:

• UNION: Combines the result sets of two queries and removes any duplicate rows from the final output. It guarantees distinct records.
• UNION ALL: Combines the result sets of two queries but retains all duplicate rows. It simply appends the results of the second query to the first.

Performance:
UNION ALL is generally faster than UNION. This is because UNION performs an internal sorting or hashing operation on the combined dataset to identify and remove duplicates. UNION ALL skips this duplicate-removal overhead entirely, making query execution significantly less resource-intensive. Therefore, if it is known that the queries will not return duplicates, or if duplicates are acceptable, UNION ALL is preferred.

Definition:
A View is a virtual table based on the result-set of an SQL statement. It contains rows and columns just like a real table, but it does not store data physically (except in materialized views). The fields in a view are fields from one or more real tables in the database.

Advantages of using Views:

1. Security: Views can restrict user access to specific rows or columns of a table, hiding sensitive data.
2. Simplicity: Complex queries involving multiple joins, subqueries, and calculations can be saved as a view. Users can then query the view simply, as if it were a single table.
3. Data Abstraction/Independence: Views shield applications from changes in the underlying table structures. If a table schema changes, the view can be modified to maintain the same interface for the application.
4. Consistency: Calculations and business logic (e.g., total_price = qty * price) can be encapsulated in a view, ensuring all users see consistent computed data.

Updatable View:
An updatable view is a view through which INSERT, UPDATE, or DELETE operations can be performed on the underlying base tables. Not all views are updatable; if a view is read-only, DML operations on it will fail.

Conditions for an Updatable View:
For a view to be updatable, the database must be able to unambiguously trace any modification back to a specific row in a specific base table. Standard conditions generally include:

1. Single Base Table: The view should ideally be defined on a single base table (though some RDBMS allow updates on multi-table views if modifications target only one base table).
2. Primary Key Included: The view must include the primary key of the base table to allow unambiguous row identification.
3. No Aggregation: The view's SELECT statement cannot contain aggregate functions (e.g., SUM, AVG, MAX).
4. No Grouping: The view cannot contain GROUP BY or HAVING clauses.
5. No Set Operators: The view cannot use set operators like UNION, INTERSECT, or EXCEPT.
6. No Distinct: The view cannot contain the DISTINCT keyword.
7. Derived Columns: Columns derived from expressions (e.g., salary * 1.1) cannot be updated.

Uncorrelated Subquery (Nested Subquery):

• Definition: An uncorrelated subquery is an inner query that can run independently of the outer query. It executes first, and its result is passed to the outer query.
• Execution: Evaluated only once for the entire outer query.
• Example: Find employees whose salary is greater than the average salary of all employees.
  sql
  SELECT name, salary FROM Employee
  WHERE salary > (SELECT AVG(salary) FROM Employee);

Correlated Subquery:

• Definition: A correlated subquery is an inner query that references columns from the outer query. It cannot run independently.
• Execution: Evaluated repeatedly—once for each row processed by the outer query.

• Example: Find employees whose salary is greater than the average salary of their own department.
  sql
  SELECT name, salary, dept_id
  FROM Employee e1
  WHERE salary > (SELECT AVG(salary)
  FROM Employee e2
  WHERE e1.dept_id = e2.dept_id);

  Here, e1.dept_id connects the inner query to the current row of the outer query.

Subqueries can be used in the FROM clause to generate a temporary derived table (or inline view) that the main query can then query against. This is particularly useful when you need to perform aggregations or complex filtering first, and then apply further logic (like joins or more grouping) on those intermediate results.

When using a subquery in the FROM clause, it is mandatory (in most DBMS like SQL Server, PostgreSQL, and MySQL) to assign an alias to the derived table.

Example:
Suppose we want to find the average of the total salaries paid per department.
sql
SELECT AVG(TotalDeptSalary) AS AvgDepartmentSalary
FROM (
SELECT department_id, SUM(salary) AS TotalDeptSalary
FROM employees
GROUP BY department_id
) AS DeptSalaries;

Here, the subquery calculates the sum of salaries for each department. The outer query treats this result set as a table named DeptSalaries and calculates the average over those aggregated sums.

1. Selection ():

• Definition: The selection operator is used to select rows (tuples) from a relation that satisfy a given propositional logic predicate. It acts as a horizontal filter.
• Notation: , where is the predicate/condition and is the relation.
• Example: To find all employees in department 10 from the Employee relation:
  

2. Projection ():

• Definition: The projection operator is used to select specific columns (attributes) from a relation, discarding the rest. It acts as a vertical filter. By default, projection removes duplicate tuples in relational algebra.
• Notation: , where are attribute names.
• Example: To retrieve only the names and salaries of all employees:
  

Cartesian Product ():

• Also known as cross product, it combines tuples from two relations. If relation has tuples and has tuples, yields a relation with tuples.
• Notation: .
• It concatenates every tuple of with every tuple of .

Natural Join ():

• It combines two relations over all their common attributes (attributes with the same name). It equates the common attributes and then projects the result to remove duplicate columns.
• Notation: .
• If no common attributes exist, it behaves like a Cartesian product.

Natural Join vs. Theta Join ():

• Theta Join () allows arbitrary comparison conditions (e.g., ) between specific attributes of two tables. For example: .
• Natural Join strictly uses an equality () condition on all attributes that have the same name in both relations, and it automatically removes the redundant column from the result. Theta join retains all columns from both relations.

1. Set Difference ():

• Definition: Yields a relation containing all tuples that appear in relation but do not appear in relation .
• Condition: and must be union-compatible (same number of attributes, compatible domains).
• Example: If contains all employees and contains managers, yields all employees who are not managers.

2. Division ():

• Definition: The division operator is suited for queries that include the phrase "for all". It returns the values of attributes in that are associated with every tuple in .
• Conditions: The attributes of must be a subset of the attributes of . If has attributes and has attribute , then returns the distinct values of from that pair with all values of present in .
• Example: If records students taking courses, and lists all core courses, then gives the students who have taken all core courses.

Window Functions:
Window functions perform a calculation across a set of table rows that are somehow related to the current row. This is comparable to the type of calculation that can be done with an aggregate function.

Difference from Aggregate Functions:

• Unlike regular aggregate functions (which group multiple rows into a single output row), window functions do not cause rows to become grouped into a single output row.
• The rows retain their separate identities. The result of the window function is simply added as a new column to the output.

The OVER() Clause:
The OVER() clause defines the "window" or set of rows the function operates on. It can contain:

• PARTITION BY: Divides the result set into partitions to which the window function is applied (similar to GROUP BY but without collapsing rows).
• ORDER BY: Specifies the logical order in which the window function calculation is performed within the partition.

These are window ranking functions used to assign a ranking integer to rows in a partition.

• ROW_NUMBER():

  • Assigns a unique, sequential integer to each row in the partition, starting at 1.
  • Ties are broken arbitrarily.
  • Scenario: Paginating results for a web application (e.g., fetch records 11 through 20).

• RANK():

  • Assigns a rank to each row based on the ORDER BY clause.
  • If rows tie, they receive the same rank. However, the next rank(s) will be skipped. (e.g., Ranks: 1, 2, 2, 4).
  • Scenario: Awarding prizes in a competition where if two people tie for 2nd, the next person gets 4th place.

• DENSE_RANK():

  • Similar to RANK(), ties receive the same rank.
  • Unlike RANK(), no ranks are skipped. (e.g., Ranks: 1, 2, 2, 3).
  • Scenario: Finding the highest salary. If two people have the highest salary, they are both rank 1, and the next highest salary is definitively rank 2.

Static vs Dynamic Hashing:

• Static Hashing: The hash function maps search-key values to a fixed set of buckets. The number of buckets is constant. If the file grows, buckets can overflow, leading to performance degradation (requiring overflow chaining).
• Dynamic Hashing: The number of buckets can dynamically change (grow or shrink) as the database size changes, preventing severe bucket overflow and maintaining performance.

Extendible Hashing Mechanism:
Extendible hashing is a dynamic hashing technique that uses a directory of pointers to buckets.

1. Hash Function: Computes a binary hash value for the search key.
2. Global Depth (): The directory uses the first (or last) bits of the hash value to route to a bucket. The directory has entries.
3. Local Depth (): Each bucket has a local depth , indicating how many bits it relies on.
4. Insertion & Splitting: When a record is inserted into a full bucket:
   • If , only that bucket splits, and its local depth increments. Directory pointers are adjusted.
   • If , the directory size doubles (global depth becomes ), and the overflowing bucket splits. This allows dynamic growth without reorganizing the entire file.

Purpose of Indexing:
An index is a data structure used to significantly speed up the retrieval of data rows from a database table. Instead of scanning every row in a table (Full Table Scan) to find matching data, the database engine uses the index to quickly locate the exact location of the data, minimizing disk I/O.

Clustered vs. Non-Clustered Indexes:

• Clustered Index:

  • Physical Sorting: Determines the physical layout of the data on the disk. The data rows themselves are stored in the order of the clustered index key.
  • Quantity: A table can have only one clustered index (since data can only be physically sorted one way).
  • Leaf Nodes: The leaf nodes of a clustered index contain the actual data pages.
  • Performance: Extremely fast for range queries (e.g., BETWEEN, >, <).

• Non-Clustered Index:

  • Physical Sorting: Does not alter the physical storage order of the data.
  • Quantity: A table can have multiple non-clustered indexes.
  • Leaf Nodes: The leaf nodes contain the index key values and a pointer (RowID or clustered index key) to the actual data row.
  • Performance: Good for exact match queries but requires an extra lookup step to fetch the data row from the heap or clustered index.

Structure of a B+ Tree:
A B+ Tree is a balanced search tree specifically designed for disk-based storage systems.

1. Internal Nodes (Non-leaf): Store only search key values and pointers to child nodes. They act purely as a multi-level index to guide searches. No actual data records are stored here.
2. Leaf Nodes: Store the search keys and the actual data pointers (or data records).
3. Linked Leaves: All leaf nodes are linked together in a sorted linked list, pointing to their right siblings.

Advantages in DBMS:

• Efficient Disk I/O: Because internal nodes do not contain data, more keys fit on a single disk block. This results in a tree with a high branching factor (fanout) and lower height, meaning fewer disk I/O operations are needed to reach the leaves.
• Fast Range Queries: The linked-list structure at the leaf level makes sequential/range scans highly efficient. Once the starting key is found, the system simply traverses the linked leaves.
• Balanced Operations: The tree remains perfectly balanced on insertions and deletions, guaranteeing search, insert, and delete times.

Query processing is the series of steps the DBMS takes to translate a high-level query (like SQL) into an efficient execution plan.

1. Parsing and Translation:
   • The SQL query is checked for syntax and semantic correctness (e.g., verifying tables and columns exist in the catalog).
   • The query is translated into an internal representation, typically a relational algebra query tree.
2. Query Optimization:
   • The DBMS takes the initial query tree and explores alternative, equivalent execution plans.
   • Heuristic Optimization: Applies equivalence rules (like pushing selections and projections down the tree) to reduce the size of intermediate results.
   • Cost-Based Optimization: Evaluates multiple join orders, access paths (index scan vs table scan), and join algorithms (nested loop, hash join, merge join). It estimates the cost (disk I/O, CPU) using database statistics and chooses the lowest-cost plan.
3. Code Generation:
   • The chosen optimal execution plan is compiled into an executable form, often a series of low-level machine or virtual machine instructions.
4. Query Execution:
   • The execution engine runs the generated code, accessing the data files and indexes, and returns the result to the user.

Heuristic Query Optimization:
Heuristic optimization relies on a set of rules (heuristics) that generally improve query performance regardless of the data distribution. The goal is usually to reduce the size of intermediate tables generated during execution.

Common Equivalence Rules (Heuristics) in Relational Algebra:

1. Push Selections down (): . Applying selections as early as possible (moving them down the tree toward the leaf nodes) reduces the number of tuples passed to subsequent operations like joins.
2. Push Projections down: . Similar to selections, stripping out unneeded columns early reduces the memory and disk I/O overhead.
3. Commutativity of Joins/Cartesian Products: . This allows the optimizer to reorder joins to evaluate the most restrictive (smallest result producing) joins first.
4. Combining Operations: A Cartesian product followed by a selection condition ( followed by ) can be converted into a single Join operation (), which is significantly more efficient to execute.