46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T4a8,The Selection operator is a **unary operation** in relational algebra, meaning it operates on a single relation to produce a new relation as output. Its purpose is **horizontal filtering**—selecting specific tuples (rows) from a relation based on a specified condition while preserving all attributes (columns). **Formal Definition:** Given a relation R with schema R(A₁, A₂, ..., Aₙ) and a selection predicate P, the Selection operation is defined as: $$σ_P(R) = \{t \mid t ∈ R ∧ P(t)\}$$ In plain language: the Selection σₚ(R) returns the set of all tuples t from relation R where the predicate P evaluates to true for t. **Key Properties:** 1. **Type Preservation**: The output schema is identical to the input schema. If R has attributes (A₁, A₂, ..., Aₙ), then σₚ(R) also has attributes (A₁, A₂, ..., Aₙ). 2. **Cardinality Reduction**: The number of tuples in the result is less than or equal to the number in the input: |σₚ(R)| ≤ |R|. Selection can only reduce or maintain cardinality, never increase it. 3. **Closure Property**: The output is always a valid relation, ensuring that Selection can be composed with other relational operations.66:T435,``` Employee Relation: +--------+-----------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+-----------+-------------+--------+------------+ | E001 | Alice | Engineering | 120000 | 2019-03-15 | | E002 | Bob | Marketing | 85000 | 2020-06-22 | | E003 | Charlie | Engineering | 95000 | 2021-01-10 | | E004 | Diana | HR | 78000 | 2018-11-30 | | E005 | Eve | Engineering | 135000 | 2017-08-05 | +--------+-----------+-------------+--------+------------+ σ_{department='Engineering'}(Employee): +--------+---------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+---------+-------------+--------+------------+ | E001 | Alice | Engineering | 120000 | 2019-03-15 | | E003 | Charlie | Engineering | 95000 | 2021-01-10 | | E005 | Eve | Engineering | 135000 | 2017-08-05 | +--------+---------+-------------+--------+------------+ Note: All 5 columns preserved, only rows matching the predicate are retained. ```67:T49c,Understanding the Selection operator requires grounding in set theory, as relational algebra is fundamentally a set-based formalism. The Selection operator performs **set restriction**—it produces a subset of the input relation. **Set-Theoretic Properties:** **1. Subset Guarantee:** For any relation R and predicate P: $$σ_P(R) ⊆ R$$ Every tuple in the result must be a tuple in the original relation. Selection never creates new tuples or modifies existing ones. **2. Idempotence:** Applying the same Selection twice produces the same result: $$σ_P(σ_P(R)) = σ_P(R)$$ Once tuples not satisfying P are eliminated, applying the same filter again has no additional effect. **3. Commutativity:** The order of cascaded Selections doesn't matter: $$σ_{P1}(σ_{P2}(R)) = σ_{P2}(σ_{P1}(R))$$ This property is crucial for query optimization, allowing the optimizer to reorder Selection operations. **4. Cascade into Conjunction:** Multiple Selections can be combined into one with a conjunctive predicate: $$σ_{P1}(σ_{P2}(R)) = σ_{P1 ∧ P2}(R)$$ This equivalence allows query optimizers to either split or merge Selection operations based on execution efficiency.68:T466,The power and flexibility of Selection lies in its predicate—the boolean expression that determines which tuples pass through the filter. Understanding predicate construction is essential for effective query writing. **Atomic Predicates (Simple Conditions):** The simplest predicates compare a single attribute to a value or another attribute: - **Attribute-Constant Comparison**: `salary > 100000` - **Attribute-Attribute Comparison**: `end_date > start_date` General form: ` ` Comparison operators include: =, ≠ (or <>), <, >, ≤ (<=), ≥ (>=) **Compound Predicates:** Atomic predicates combine using logical connectives to form compound predicates: - **Conjunction (AND)**: Both conditions must be true - `department = 'Engineering' AND salary > 100000` - **Disjunction (OR)**: At least one condition must be true - `department = 'Engineering' OR department = 'Research'` - **Negation (NOT)**: The condition must be false - `NOT (status = 'inactive')` **Operator Precedence (highest to lowest):** 1. Comparison operators (=, <, >, etc.) 2. NOT 3. AND 4. OR69:T4cc,``` # Conjunction (AND) - Both conditions must be true σ_{department='Engineering' ∧ salary>100000}(Employee) Result: Employees in Engineering earning more than $100,000 +--------+-------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+-------+-------------+--------+------------+ | E001 | Alice | Engineering | 120000 | 2019-03-15 | | E005 | Eve | Engineering | 135000 | 2017-08-05 | +--------+-------+-------------+--------+------------+ # Disjunction (OR) - At least one condition true σ_{department='HR' ∨ salary>120000}(Employee) Result: HR employees OR anyone earning more than $120,000 +--------+-------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+-------+-------------+--------+------------+ | E004 | Diana | HR | 78000 | 2018-11-30 | | E005 | Eve | Engineering | 135000 | 2017-08-05 | +--------+-------+-------------+--------+------------+ # Complex predicate with precedence σ_{dept='Eng' ∧ salary>100000 ∨ hire_date<'2018-01-01'}(Employee) Equivalent to: (dept='Eng' AND salary>100000) OR hire_date<'2018-01-01' Note: AND binds tighter than OR without parentheses ```6a:T5e1,``` Employee Relation with NULLs: +--------+---------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+---------+-------------+--------+------------+ | E001 | Alice | Engineering | 120000 | 2019-03-15 | | E002 | Bob | Marketing | NULL | 2020-06-22 | ← salary unknown | E003 | Charlie | NULL | 95000 | 2021-01-10 | ← department unknown | E004 | Diana | HR | 78000 | NULL | ← hire_date unknown +--------+---------+-------------+--------+------------+ σ_{salary > 100000}(Employee) +--------+-------+-------------+--------+------------+ | emp_id | name | department | salary | hire_date | +--------+-------+-------------+--------+------------+ | E001 | Alice | Engineering | 120000 | 2019-03-15 | +--------+-------+-------------+--------+------------+ → Bob is EXCLUDED: NULL > 100000 evaluates to UNKNOWN → Charlie EXCLUDED: 95000 > 100000 is FALSE → Diana EXCLUDED: 78000 > 100000 is FALSE σ_{salary <= 100000}(Employee) +--------+---------+-----------+--------+------------+ | emp_id | name | department| salary | hire_date | +--------+---------+-----------+--------+------------+ | E003 | Charlie | NULL | 95000 | 2021-01-10 | | E004 | Diana | HR | 78000 | NULL | +--------+---------+-----------+--------+------------+ → Bob is STILL EXCLUDED: NULL <= 100000 is also UNKNOWN! → Neither σ_{salary>100000} nor σ_{salary<=100000} includes Bob ```6b:T461,Understanding the performance characteristics of Selection is essential for writing efficient queries and predicting system behavior. Two key concepts govern Selection performance: **selectivity** and **evaluation cost**. **Selectivity:** The selectivity of a predicate P on relation R is the fraction of tuples that satisfy the predicate: $$sel(P, R) = \frac{|σ_P(R)|}{|R|}$$ Selectivity ranges from 0 (no tuples match) to 1 (all tuples match). **Examples of Selectivity:** - `emp_id = 'E001'` on primary key: selectivity ≈ 1/n (highly selective) - `department = 'Engineering'` on 5-department company: selectivity ≈ 0.2 - `salary > 0` on salary column: selectivity ≈ 1.0 (non-selective) - `status = 'active' AND country = 'US' AND age > 30`: compound selectivity **Selectivity Estimation:** Database query optimizers estimate selectivity using: 1. **Histograms**: Statistical distributions of column values 2. **Distinct Value Counts**: Uniformity assumption: selectivity ≈ 1/NDV for equality 3. **Range Statistics**: Min/max values for range predicates 4. **Sampling**: Running predicate on data sample6c:T565,Understanding how database systems implement Selection illuminates why some queries are fast and others are slow. The query execution engine has several strategies available, each suited to different scenarios. **Strategy 1: Full Table Scan** The simplest approach reads every tuple and evaluates the predicate: ``` Algorithm: FullTableScan(R, P) result ← ∅ for each page p in R: for each tuple t in p: if P(t) = TRUE: add t to result return result ``` - **Cost**: O(n) tuple evaluations + O(B) I/O operations (B = number of pages) - **When Used**: No suitable index, low selectivity predicates, small tables - **Advantage**: Simple, predictable, uses sequential I/O **Strategy 2: Index Scan** When an index exists on selection attributes: ``` Algorithm: IndexScan(R, P, Index) result ← ∅ keys ← SearchIndex(Index, P) -- Returns matching keys for each key k in keys: rid ← Index.lookup(k) -- Get record ID t ← R.fetch(rid) -- Fetch tuple by ID if P(t) = TRUE: -- Verify (for partial matches) add t to result return result ``` - **Cost**: O(log n) + O(k) for k matching tuples + random I/O per match - **When Used**: Highly selective predicates on indexed columns - **Advantage**: Examines only relevant tuples - **Disadvantage**: Random I/O pattern can be costly for many matches6d:T40d,**SQL Predicates Beyond Basic Algebra:** SQL provides several predicate forms that extend beyond simple comparisons: 1. **BETWEEN**: `salary BETWEEN 50000 AND 100000` (inclusive range) 2. **IN**: `department IN ('Eng', 'HR', 'Sales')` (set membership) 3. **LIKE**: `name LIKE 'John%'` (pattern matching with wildcards) 4. **IS NULL / IS NOT NULL**: Explicit NULL testing 5. **EXISTS**: Subquery existence testing (correlated with other operators) 6. **ANY / ALL**: Subquery comparison operators **Expression in Predicates:** SQL allows expressions, not just attributes, in predicates: ```sql -- Function application in predicate SELECT * FROM Employee WHERE YEAR(hire_date) = 2023; -- Arithmetic expression SELECT * FROM Employee WHERE salary * 1.1 > 100000; -- String function SELECT * FROM Employee WHERE UPPER(department) = 'ENGINEERING'; ``` **Warning**: Expressions on columns often prevent index usage, causing full table scans. Prefer `hire_date >= '2023-01-01' AND hire_date < '2024-01-01'` over `YEAR(hire_date) = 2023`.45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792318196641,"state":{"data":{"json":{"id":"seed_f73df6c127ebd2d03bb7298c3867d3f3","slug":"selection-and-projection","category":"Database Management Systems","topic":"Relational Algebra","title":"Selection and Projection","description":"Master the two fundamental unary operations in relational algebra: Selection (σ) for filtering rows based on predicates and Projection (π) for selecting specific columns. Understand their formal definitions, implementation strategies, optimization opportunities, and how they combine to form the foundation of all database queries.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_f11e4c9b6fe566e232f9b4adc3068944","title":"Selection (σ) Operator","order":0,"content":[{"id":"opening-hook","title":"The Art of Filtering Data","content":[{"data":{"content":"Imagine you have a database containing millions of employee records, but you only need information about employees in the Engineering department who earn more than $100,000. How do you extract precisely the rows you need without retrieving and discarding irrelevant data? This is the fundamental problem that the **Selection operator (σ)** solves—and it does so with mathematical elegance and computational efficiency.\n\nThe Selection operator, denoted by the Greek letter sigma (σ), is one of the most frequently used operations in relational algebra. Every time you write a `WHERE` clause in SQL, you're invoking the conceptual machinery that Selection provides. Understanding this operator deeply isn't just academic—it's essential for writing efficient queries, understanding query optimization, and debugging performance problems in database systems."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the formal mathematical definition of the Selection operator, master predicate construction and evaluation, comprehend the implementation strategies used by real database systems, and recognize how Selection forms the foundation for declarative data retrieval across all SQL operations.","variant":"info"},"type":"callout"}]},{"id":"formal-definition","title":"Formal Definition and Notation","content":[{"data":{"content":"$65"},"type":"text"},{"data":{"title":"Basic Selection Notation","content":"$66","description":"Consider a relation Employee with schema Employee(emp_id, name, department, salary, hire_date). Here are various Selection expressions and their meanings:"},"type":"example"},{"data":{"icon":"Info","title":"Notation Variations","content":"You may encounter different notational conventions: σ_{P}(R), σ[P](R), SELECT[P](R), or R WHERE P. All express the same operation. The subscript or bracketed expression contains the selection predicate, and the relation appears either inside parentheses or to the left of the operator symbol. This course uses σ_{P}(R) as the standard notation.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"mathematical-foundation","title":"Mathematical Foundation","content":[{"data":{"content":"$67"},"type":"text"},{"data":{"rows":[["Identity","σ_{true}(R) = R","Selecting with always-true predicate returns entire relation"],["Empty Result","σ_{false}(R) = ∅","Selecting with always-false predicate returns empty relation"],["Cascade","σ_{P1}(σ_{P2}(R)) = σ_{P1 ∧ P2}(R)","Cascaded selections combine into single selection"],["Commutativity","σ_{P1}(σ_{P2}(R)) = σ_{P2}(σ_{P1}(R))","Order of cascaded selections doesn't matter"],["Idempotence","σ_P(σ_P(R)) = σ_P(R)","Repeated identical selection has no additional effect"],["Selectivity Bound","0 ≤ |σ_P(R)| ≤ |R|","Result cardinality bounded by input cardinality"]],"caption":"Selection Algebraic Laws","headers":["Law Name","Expression","Meaning"]},"type":"table"},{"data":{"content":"**Relationship to Predicate Logic:**\n\nThe selection predicate P is a formula in first-order predicate logic. For each tuple t, P(t) evaluates to either true or false (we'll address NULL values later). The predicate can reference:\n\n- **Attribute values**: Referencing specific columns of the tuple being evaluated\n- **Constants**: Literal values (numbers, strings, dates)\n- **Logical connectives**: AND (∧), OR (∨), NOT (¬)\n- **Comparison operators**: =, ≠, <, >, ≤, ≥\n\nThe expressiveness of selection predicates directly corresponds to the fragment of first-order logic restricted to single-tuple evaluation."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why Mathematical Foundations Matter","content":"These algebraic laws aren't just theoretical curiosities—they're the foundation of query optimization. When a database optimizer sees a complex query, it uses these equivalences to rewrite the query into a more efficient form while guaranteeing identical results. Understanding these laws helps you predict optimizer behavior and write queries that are easier to optimize.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"predicate-anatomy","title":"Anatomy of Selection Predicates","content":[{"data":{"content":"$68"},"type":"text"},{"data":{"title":"Compound Predicate Examples","content":"$69","description":"Demonstrating various compound predicate constructions on the Employee relation"},"type":"example"},{"data":{"items":["**Operator Precedence Confusion**: `A OR B AND C` evaluates as `A OR (B AND C)`, not `(A OR B) AND C`. Always use explicit parentheses for clarity.","**Type Mismatches**: Comparing string '100' with integer 100 may cause implicit conversions with unexpected results. Ensure type consistency.","**NULL Comparisons**: The expression `salary > 100000` returns UNKNOWN (not false) when salary is NULL. We'll cover three-valued logic in detail.","**Case Sensitivity**: String comparisons may or may not be case-sensitive depending on database collation. Always verify your database's behavior."],"title":{"icon":"AlertCircle","text":"Common Predicate Pitfalls","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"titleType":"number","titleNumber":3},{"id":"three-valued-logic","title":"Three-Valued Logic and NULL Handling","content":[{"data":{"content":"One of the most subtle aspects of Selection is how it handles NULL values. In standard relational algebra, tuples either satisfy a predicate or they don't—a two-valued Boolean world. However, SQL and practical database systems use **three-valued logic (3VL)** to handle unknown or missing values.\n\n**The Three Truth Values:**\n\n1. **TRUE**: The predicate definitely holds\n2. **FALSE**: The predicate definitely does not hold\n3. **UNKNOWN**: The result cannot be determined (typically due to NULL)\n\n**Selection passes only tuples where the predicate evaluates to TRUE.** Tuples evaluating to FALSE or UNKNOWN are excluded.\n\n**NULL in Comparisons:**\n\nWhen any operand in a comparison is NULL, the result is UNKNOWN:\n\n- `NULL = NULL` → UNKNOWN (not TRUE!)\n- `NULL > 100` → UNKNOWN\n- `100 = NULL` → UNKNOWN\n- `'Alice' <> NULL` → UNKNOWN"},"type":"text"},{"data":{"rows":[["TRUE","TRUE","TRUE","TRUE","FALSE"],["TRUE","FALSE","FALSE","TRUE","FALSE"],["TRUE","UNKNOWN","UNKNOWN","TRUE","FALSE"],["FALSE","TRUE","FALSE","TRUE","TRUE"],["FALSE","FALSE","FALSE","FALSE","TRUE"],["FALSE","UNKNOWN","FALSE","UNKNOWN","TRUE"],["UNKNOWN","TRUE","UNKNOWN","TRUE","UNKNOWN"],["UNKNOWN","FALSE","FALSE","UNKNOWN","UNKNOWN"],["UNKNOWN","UNKNOWN","UNKNOWN","UNKNOWN","UNKNOWN"]],"caption":"Three-Valued Logic Truth Tables","headers":["P","Q","P AND Q","P OR Q","NOT P"]},"type":"table"},{"data":{"title":"NULL Handling in Selection","content":"$6a","description":"Demonstrating how NULLs affect selection results"},"type":"example"},{"data":{"icon":"AlertCircle","title":"The NULL Paradox","content":"A critical implication: σ_{P}(R) ∪ σ_{NOT P}(R) ≠ R when NULLs are present. Tuples with NULL values in predicate-relevant columns disappear from both results! To include NULLs, you must explicitly test: `salary > 100000 OR salary IS NULL`.","variant":"warning"},"type":"callout"},{"data":{"content":"**Testing for NULL:**\n\nSince comparisons with NULL yield UNKNOWN, SQL provides special predicates:\n\n- `IS NULL`: Returns TRUE if the value is NULL\n- `IS NOT NULL`: Returns TRUE if the value is not NULL\n\nThese are the only predicates that return TRUE or FALSE (never UNKNOWN) when evaluating NULL values.\n\n**Practical Implications:**\n\nWhen writing selections involving nullable columns:\n1. Consider whether NULL rows should be included\n2. Use explicit NULL tests when needed\n3. Remember that negating a predicate doesn't capture NULL rows\n4. COALESCE or IFNULL functions can provide default values for comparison"},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"selectivity-and-cost","title":"Selectivity and Computational Cost","content":[{"data":{"content":"$6b"},"type":"text"},{"data":{"rows":[["column = constant","1/NDV(column)","Uniform distribution of values"],["column > constant","(max - constant)/(max - min)","Uniform distribution in range"],["column < constant","(constant - min)/(max - min)","Uniform distribution in range"],["column BETWEEN a AND b","(b - a)/(max - min)","Uniform distribution in range"],["column LIKE 'prefix%'","Varies","Uses histogram if available"],["P₁ AND P₂","sel(P₁) × sel(P₂)","Independence assumption"],["P₁ OR P₂","sel(P₁) + sel(P₂) - sel(P₁)×sel(P₂)","Inclusion-exclusion"],["NOT P","1 - sel(P)","Complement"]],"caption":"Selectivity Estimation Heuristics","headers":["Predicate Type","Typical Selectivity Estimate","Assumptions"]},"type":"table"},{"data":{"content":"**Time Complexity:**\n\n**Without Indexes:**\nSelection requires a **full table scan**: O(n) where n is the number of tuples. Every tuple must be read and evaluated against the predicate.\n\n**With Indexes:**\nIf an index exists on the selection attribute, complexity improves dramatically:\n- B-tree index equality: O(log n) to find first match + O(k) for k matches\n- B-tree index range: O(log n) + O(k)\n- Hash index equality: O(1) expected + O(k) for k matches\n- Bitmap index: O(n/w) where w is word size (efficient for low-cardinality columns)\n\n**Space Complexity:**\n\nSelection produces a result relation that requires storage. In the worst case (selectivity = 1), the output equals the input size. In practice:\n- Streaming evaluation: Process one tuple at a time, O(1) working memory\n- Materialized result: O(sel × n) space for result storage"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Selectivity Matters for Query Planning","content":"Query optimizers use selectivity estimates to choose execution strategies. A highly selective predicate (sel < 0.01) might warrant an index lookup, while a non-selective predicate (sel > 0.3) might favor a full table scan. Inaccurate selectivity estimates cause poor query plans—one reason database statistics must be kept current.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"implementation-strategies","title":"Implementation Strategies","content":[{"data":{"content":"$6c"},"type":"text"},{"data":{"left":[{"data":{"items":["Table is small (fits in memory)","Selectivity > 10-20% of table","No suitable index exists","Sequential I/O is much faster than random","Query touches most columns (wide rows)","Predicate involves functions on columns"],"title":{"icon":"CheckCircle","text":"Full Table Scan: Best When","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Predicate is highly selective (< 5%)","Index covers predicate columns","Table is large and doesn't fit in memory","Clustered index aligns with predicate","Index-only query (all needed columns in index)","Point queries on primary key"],"title":{"icon":"Zap","text":"Index Scan: Best When","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Strategy 3: Bitmap Index Scan**\n\nFor complex predicates combining multiple conditions:\n\n```\nAlgorithm: BitmapScan(R, P₁ AND P₂, Index₁, Index₂)\n bitmap1 ← Index₁.getBitmap(P₁) -- Bitmap of RIDs matching P₁\n bitmap2 ← Index₂.getBitmap(P₂) -- Bitmap of RIDs matching P₂\n combined ← bitmap1 AND bitmap2 -- Bitwise AND\n result ← ∅\n for each bit set in combined:\n rid ← position of bit\n t ← R.fetch(rid)\n add t to result\n return result\n```\n\n- **When Used**: Compound predicates with multiple indexed columns\n- **Advantage**: Combines index results before fetching, reduces random I/O\n\n**Strategy 4: Index-Only Scan (Covering Index)**\n\nWhen all needed columns exist in the index:\n\n```\nAlgorithm: IndexOnlyScan(Index, P)\n result ← ∅\n for each entry e in Index where P(e) = TRUE:\n add ProjectedTuple(e) to result\n return result\n```\n\n- **Advantage**: No table access required—index contains all needed data\n- **Fastest possible**: Avoids I/O for tuple fetching entirely"},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"selection-in-sql","title":"Selection in SQL","content":[{"data":{"content":"The Selection operator manifests in SQL through the `WHERE` clause. Understanding this connection helps bridge theoretical algebra with practical query writing.\n\n**Direct Mapping:**"},"type":"text"},{"data":{"rows":[["σ_{P}(R)","SELECT * FROM R WHERE P"]],"headers":["Relational Algebra","SQL Equivalent"]},"type":"table"},{"data":{"content":"**SQL extends the basic Selection capability with additional features not present in pure relational algebra:**"},"type":"text"},{"data":{"fileName":"selection_examples.sql","languages":[{"code":"-- Basic Selection: σ_{department='Engineering'}(Employee)\nSELECT * \nFROM Employee \nWHERE department = 'Engineering';\n\n-- Compound Selection: σ_{department='Engineering' ∧ salary>100000}(Employee)\nSELECT * \nFROM Employee \nWHERE department = 'Engineering' \n AND salary > 100000;\n\n-- Range Selection\nSELECT * \nFROM Employee \nWHERE salary BETWEEN 80000 AND 120000;\n\n-- Pattern Matching (SQL extension beyond pure relational algebra)\nSELECT * \nFROM Employee \nWHERE name LIKE 'A%'; -- Names starting with 'A'\n\n-- Set Membership (simpler than multiple OR conditions)\nSELECT * \nFROM Employee \nWHERE department IN ('Engineering', 'Research', 'Product');\n\n-- NULL Handling\nSELECT * \nFROM Employee \nWHERE salary IS NOT NULL \n AND salary > 100000;\n\n-- Combining NULL check with OR\nSELECT * \nFROM Employee \nWHERE salary > 100000 \n OR salary IS NULL; -- Include unknown salaries","label":"SQL","value":"sql"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"$6d"},"type":"text"},{"data":{"icon":"AlertCircle","title":"SARGability: Index-Friendly Predicates","content":"A predicate is 'SARGable' (Search ARGument able) if it can leverage an index. Non-SARGable predicates include: functions on columns (YEAR(date)), arithmetic on columns (salary * 1.1), implicit type conversions, and LIKE patterns starting with wildcards ('%suffix'). Rewrite predicates to be SARGable whenever possible for optimal performance.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary and Key Takeaways","content":[{"data":{"content":"The Selection operator is the fundamental filtering mechanism in relational algebra, and mastering its properties is essential for database professionals. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**Selection (σ) performs horizontal filtering** — It extracts tuples matching a predicate while preserving all attributes. The output schema equals the input schema.","**Predicates can be atomic or compound** — Simple comparisons combine with AND, OR, NOT to form complex boolean expressions. Operator precedence matters.","**Three-valued logic handles NULLs** — Comparisons with NULL yield UNKNOWN. Only tuples evaluating to TRUE pass Selection; UNKNOWN tuples are excluded.","**Algebraic laws enable optimization** — Commutativity and cascade properties allow query rewriting. Selection is idempotent and always produces a subset.","**Selectivity drives execution strategy** — High selectivity favors index scans; low selectivity favors full table scans. Query optimizers estimate selectivity from statistics.","**Implementation varies by context** — Full scans, index scans, bitmap scans, and index-only scans each have optimal use cases. Understanding when to expect each helps diagnose performance.","**SQL's WHERE clause implements Selection** — The mapping is direct, but SQL extends with BETWEEN, IN, LIKE, and other conveniences. SARGable predicates enable index optimization."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nHaving mastered the Selection operator for horizontal filtering, we'll next explore the predicates in greater depth. Understanding the different types of conditions you can express—and how databases evaluate them—is crucial for writing effective queries. The next page dives deep into predicate conditions, covering comparison types, logical operators, and advanced predicate patterns."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a comprehensive understanding of the Selection operator—from its formal mathematical definition through implementation strategies to practical SQL usage. This knowledge forms the foundation for all filtering operations in relational databases. Next, we'll dive deeper into the predicate conditions that power Selection.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_5ff161ac6f172df3c985694f82f7aa7d","title":"Predicate Conditions","order":1,"content":null,"isLocked":true},{"id":"seed_a78a23e81d054e2f6b7a5c0f7c9b05eb","title":"Projection (π) Operator","order":2,"content":null,"isLocked":true},{"id":"seed_2b58413f08f11d6a12a9161ebf9b8ae8","title":"Duplicate Elimination","order":3,"content":null,"isLocked":true},{"id":"seed_ea584b0ac35948f45da0b463d50a8efe","title":"Combining Operations","order":4,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792318196528,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"selection-and-projection"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"selection-and-projection\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318196641,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318196637,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_f73df6c127ebd2d03bb7298c3867d3f3"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_f73df6c127ebd2d03bb7298c3867d3f3\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318196641,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318196638,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_5ff161ac6f172df3c985694f82f7aa7d"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_5ff161ac6f172df3c985694f82f7aa7d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318196641,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318196638,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_5ff161ac6f172df3c985694f82f7aa7d"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_5ff161ac6f172df3c985694f82f7aa7d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318196641,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792318196638,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_5ff161ac6f172df3c985694f82f7aa7d"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_5ff161ac6f172df3c985694f82f7aa7d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318196641,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_5ff161ac6f172df3c985694f82f7aa7d","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_5ff161ac6f172df3c985694f82f7aa7d\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6e"}]},"children":"$L6f"}]