Unit3 - Subjective Questions

Relational Algebra is a procedural query language. The fundamental operations are:

1. Select (): Selects tuples that satisfy a given predicate.
   • Notation:
2. Project (): Selects specified columns (attributes) and discards others.
   • Notation:
3. Union (): Returns a relation containing all tuples that appear in either or both of the two specified relations.
   • Notation:
4. Set Difference (): Returns a relation containing tuples that appear in the first relation but not the second.
   • Notation:
5. Cartesian Product (): Combines information from two relations by pairing every tuple of the first relation with every tuple of the second.
   • Notation:
6. Rename (): Renames the output relation or attributes.
   • Notation:

The primary differences between WHERE and HAVING are:

1. Execution Time:
   • WHERE: Filters rows before any grouping or aggregation takes place.
   • HAVING: Filters groups after the aggregation has been performed.
2. Usage with Aggregates:
   • WHERE: Cannot contain aggregate functions (like SUM, COUNT) directly.
   • HAVING: Is specifically designed to work with aggregate functions.

Example:
Consider a table Sales(Product, Amount).

• To find rows where the amount is > 100:
  SELECT * FROM Sales WHERE Amount > 100;
• To find Products where the total sales are > 1000:
  SELECT Product, SUM(Amount) FROM Sales GROUP BY Product HAVING SUM(Amount) > 1000;

SQL Joins combine rows from two or more tables based on a related column.

Types of Joins:

1. Inner Join: Returns records that have matching values in both tables.
2. Left (Outer) Join: Returns all records from the left table, and the matched records from the right table. (Nulls for unmatched right side).
3. Right (Outer) Join: Returns all records from the right table, and the matched records from the left table.
4. Full (Outer) Join: Returns all records when there is a match in either left or right table.

Difference:

• Inner Join: If a tuple in table A has no matching tuple in table B, that tuple is excluded from the result.
• Outer Join: Preserves tuples even if they have no match. If a tuple in table A matches nothing in table B, the result includes the tuple from A with NULL values for the attributes of B.

Window Functions perform a calculation across a set of table rows that are somehow related to the current row. Unlike regular aggregate functions, window functions do not cause rows to become grouped into a single output row; the rows retain their separate identities.

Syntax Example: SELECT profit, RANK() OVER (ORDER BY profit DESC) FROM Sales;

Difference between RANK() and DENSE_RANK():

• RANK(): Assigns a rank to each row. If two rows have the same value, they get the same rank, but the next rank is skipped.
  • Example Sequence: 1, 2, 2, 4
• DENSE_RANK(): Assigns a rank to each row. If two rows have the same value, they get the same rank, and the next rank is not skipped.
  • Example Sequence: 1, 2, 2, 3

Structure of a B+ Tree:
A B+ Tree is a balanced binary search tree used for indexing.

1. Internal Nodes: Store only keys and pointers to children. They do not store actual data pointers.
2. Leaf Nodes: Store all keys and the actual data pointers (or records).
3. Linked Leaves: All leaf nodes are linked together in a linked list format, allowing for efficient sequential access.

Advantages over B-Tree:

1. Height: Since internal nodes only store keys (not data), more keys fit in a single block (node). This leads to a larger fan-out and reduced tree height, reducing disk I/O.
2. Range Queries: B+ Trees are superior for range queries. Once the starting leaf is found, the system simply traverses the linked list of leaves. A B-Tree requires traversing up and down the tree structure.
3. Predictability: Search time is consistent as every search must traverse from root to leaf.

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 on the disk (unless it is a Materialized View).

Syntax: CREATE VIEW ViewName AS SELECT ...

Advantages:

1. Security: specific rows or columns can be hidden from users by granting access only to the view, not the underlying table.
2. Simplicity: Complex queries (involving multiple joins or aggregations) can be encapsulated in a view, allowing users to select from the view simply.
3. Logical Data Independence: If the schema of the underlying table changes, the view definition can be updated without affecting the external applications that use the view.
4. Consistency: Users see a consistent, frozen definition of data logic.

A Correlated Subquery is a subquery that uses values from the outer query. The subquery is executed once for each row processed by the outer query.

Mechanism:

1. The outer query selects a candidate row.
2. The value from this row is passed to the inner query.
3. The inner query executes.
4. The outer query evaluates the qualification based on the inner query result.

Example:
Find employees whose salary is greater than the average salary of their respective department.

sql
SELECT e1.emp_name, e1.salary
FROM Employee e1
WHERE e1.salary > (
SELECT AVG(e2.salary)
FROM Employee e2
WHERE e2.dept_id = e1.dept_id
);

Here, e1.dept_id is a reference to the outer table Employee e1.

Extendible Hashing is a dynamic hashing technique that handles database growth by splitting buckets and doubling the directory size rather than rehashing all data.

Components:

1. Directory: An array of pointers to buckets. The size is , where is the global depth.
2. Buckets: Store the data records. Each bucket has a local depth .

Handling Overflow:
When a bucket overflows (becomes full):

1. Compare Depths:
   • If Local Depth < Global Depth: The bucket is split into two. The local depth of the new buckets is incremented. The directory pointers are updated to point to the new buckets. No directory expansion is needed.
   • If Local Depth == Global Depth: The directory size doubles (Global Depth increases by 1). The overflowing bucket splits, and pointers are redistributed. Other buckets remain untouched.

This approach ensures that only the specific overflowing area is reorganized, making it efficient for large databases.

Set operators combine the results of two or more SELECT statements.

1. UNION: Combines the result sets of two queries and removes duplicates.
   • UNION ALL preserves duplicates.
2. INTERSECT: Returns only the rows that appear in both result sets.
3. EXCEPT (or MINUS): Returns rows from the first query that are not present in the second query.

Requirements (Union Compatibility):
For these operators to work, the two queries must be union-compatible:

1. Same Number of Columns: Both queries must return the same number of attributes.
2. Compatible Data Types: The data types of the corresponding columns must be compatible (e.g., you cannot union a String column with an Integer column).

The Division operator () is used to answer queries like "Find entities in R that are associated with all entities in S".

Derivation:
Let and be relations.

Step-by-step logic:

1. Identify all candidate values: .
2. Build all possible combinations of candidate values with every value in : .
3. Identify the combinations that do not exist in the original relation : .
4. Identify the values associated with these missing combinations: .
5. Subtract these "incomplete" values from the list of all candidates.

Example: Find students (from table Enrolled) who have taken all courses listed in table RequiredCourses.

Query Optimization is the process of selecting the most efficient execution plan for a given query to minimize response time and resource usage.

1. Heuristic Optimization:

   • Uses rule-based approaches to transform the query into a more efficient equivalent form.
   • Common Rules: Perform Selection early (push down ), perform Projections early (push down ), and reorder Joins so smaller relations are joined first.
   • It does not calculate actual costs but relies on general "good practices."

2. Cost-Based Optimization (CBO):

   • Estimates the cost of various execution plans based on database statistics (table size, index selectivity, row count).
   • Assigns a "cost" (usually relative I/O or CPU time) to operations.
   • Selects the plan with the lowest estimated cost.

Clustered Index:

• Data Organization: The physical order of rows on the disk is the same as the order of the index.
• Count: There can be only one clustered index per table (because data can only be sorted physically in one way).
• Speed: Faster for retrieving ranges of data or sorting.
• Leaf Nodes: The leaf nodes contain the actual data pages.

Non-Clustered (Secondary) Index:

• Data Organization: The logical order of the index does not match the physical order of the data on the disk.
• Count: A table can have multiple non-clustered indexes.
• Speed: generally slower than clustered for range queries because it requires pointer lookups.
• Leaf Nodes: The leaf nodes contain pointers (or row IDs) to the data pages, not the data itself.

Aggregate Functions perform a calculation on a set of values and return a single scalar value.

1. COUNT(): Returns the number of rows.
2. SUM(): Returns the total sum of a numeric column.
3. AVG(): Returns the average value.
4. MIN(): Returns the smallest value.
5. MAX(): Returns the largest value.

Handling NULLs:

• COUNT(*): Counts all rows, including those with NULLs.
• COUNT(column): Counts only rows where column is NOT NULL.
• SUM, AVG, MIN, MAX: Ignore NULL values completely. For example, the average of (10, NULL, 20) is calculated as , not divided by 3.

Hash Join Algorithm:
Used for joining two relations, and , on a common attribute.

1. Build Phase: The algorithm scans the smaller relation (say ) and builds an in-memory hash table using the join attribute as the key.
2. Probe Phase: It then scans the larger relation (). For each tuple in , it hashes the join attribute and probes the hash table to find matches from .

Preference:

• Hash Join is preferred when both tables are large and there are no existing indices on the join columns. It is generally faster than Nested Loop for large datasets.
• Nested Loop Join is preferred if one table is very small, or if the join column is indexed.

Static Hashing:

• The number of buckets is fixed when the file is created.
• Function: (where is fixed).
• Problem: As the database grows, buckets fill up, leading to overflow chains (collisions). Performance degrades to linear search in long chains.
• Resizing: Requires rehashing the entire database into a larger file, which is expensive.

Dynamic Hashing:

• The number of buckets grows or shrinks as records are added or deleted.
• Techniques: Extendible Hashing, Linear Hashing.
• Advantage: Maintains performance (approx. 1 disk access per retrieval) regardless of data volume growth.
• Mechanism: Uses a directory or specific splitting rules to split only the overflowing bucket without reorganizing the whole data.

Materialized View:
A database object that contains the results of a query and physically stores the data on the disk (like a cached table).

Comparison:

1. Storage:
   • Standard View: Virtual; stores only the query definition.
   • Materialized View: Physical; stores the actual data rows.
2. Performance (Read):
   • Standard View: Slower for complex queries because the underlying query runs every time the view is accessed.
   • Materialized View: Very fast, as data is pre-computed.
3. Maintenance (Write):
   • Standard View: Always up to date.
   • Materialized View: Needs Refresh (updating). If the base tables change, the materialized view becomes stale until it is refreshed (immediately or periodically). This adds overhead to write operations.

Heuristic rules transform a query tree into an equivalent, more efficient tree:

1. Push Selection Down (): Perform selection operations as early as possible (closest to the leaf nodes). This reduces the number of tuples passed to subsequent operations like joins.
2. Push Projection Down (): Perform projection early to reduce the size of tuples (remove unused columns) before expensive operations like joins.
3. Reorder Joins: Join the most restrictive relations (resulting in the smallest intermediate relation) first.
4. Combine Operations: A sequence of unary operations (like a selection followed by another selection) can be combined into a single operation.
5. Evaluate Cartesian Products last: Never perform a cross product () if a Join () is possible, as cross products generate massive intermediate results.

Usage: GROUP BY groups rows that have the same values in specified columns into summary rows. HAVING filters these groups based on a condition.

Syntax:
sql
SELECT column_name, aggregate_function(column_name)
FROM table_name
WHERE condition
GROUP BY column_name
HAVING condition;

Example:
Assume a Students table with Department and Marks.
To find departments where the average marks are greater than 80:
sql
SELECT Department, AVG(Marks)
FROM Students
GROUP BY Department
HAVING AVG(Marks) > 80;

Here, the database first groups students by department, calculates the average, and then filters out departments with an average .

Natural Join ():
A natural join is a specific type of inner join that joins two tables based on all attributes that have the same name in both tables. It removes duplicate columns from the result.

Relational Algebra:
Notation:
If and , the join condition is implicitly AND . The result schema is .

SQL:
sql
SELECT *
FROM R
NATURAL JOIN S;

Note: Use with caution in SQL, as adding a column with the same name to one table later can unintentionally change the join logic.

Selectivity is a measure of the variety of unique values in a column, used by the query optimizer to choose indices.

• Definition: Selectivity is the ratio of distinct values to the total number of rows.
  
• High Selectivity: Values are unique or nearly unique (e.g., Primary Key, Phone Number). Indexes are very effective here because a query filters out most rows.
• Low Selectivity: Many repeated values (e.g., Gender: 'M', 'F'). Indexes are generally inefficient here because the database might have to read a large percentage of the table anyway, making a full table scan faster than index lookup.