Data Querying Notes

Introduction to Data Querying

  • These notes cover data querying in relational databases.
  • Focus is on performing meaningful and efficient queries.

Retrieving Data Efficiently

  • Data querying involves retrieving data from a database.
  • The goal is to filter large datasets for specific tasks.

Roadmap

  • Introduction to SELECT queries in SQL.
  • Aggregation and string operations in SQL.
  • Joins, set operations, and nested SQL queries.
  • SQL query execution by the database query engine.
  • Programmatic access to the database.
  • Summary of main conclusions.

Structured Query Language (SQL)

  • Data definition language (CREATE, DROP, ALTER).
  • Data manipulation language (INSERT, UPDATE, DELETE, SELECT) - aka CRUD.
  • SELECT queries are covered in depth.

What vs. How

  • SQL is a declarative language, specifying what to do, not how.
  • Example: Asking for patients in Pittsford vs. step-by-step instructions to retrieve them.
  • Declarative nature makes SQL easy to use but requires understanding of how it works for performance optimization.

Logical Model

  • Example database schema includes tables like Patient, Visit, and Doctor.
  • Attributes include ssn, firstName, lastName, dob, salary, etc.

Simple Query

  • Example: SELECT firstName FROM Patient;
  • Retrieves first names of all patients.
  • The result is a new relation (named "Result") with a single attribute: firstName.

Closure Property

  • The result of a SQL query is a new relation.
  • This new relation can be used in further SQL queries.
  • Example: SELECT a, b FROM A; produces "Result", then SELECT b FROM “Result”;

Another Simple Query

  • Example: SELECT lastName FROM Doctor;
  • Retrieves last names of all doctors.
  • May return repeated results.

Removing Redundant Tuples

  • Use SELECT DISTINCT lastName FROM Doctor; to remove duplicates.
  • Warning: DISTINCT is computationally expensive, so avoid when possible.

Warnings in SQL

  • Warnings highlight potential performance issues.
  • SQL's declarative nature requires awareness of internal workings for query optimization.
  • Avoid using DISTINCT blindly; use it only when necessary.

Arithmetic Operations

  • Example: SELECT lastName, salary * 1.1 FROM Doctor;
  • Performs arithmetic operations on attributes.
  • Other allowed operators: +, -, /
  • Attribute names can be “salary * 1.1”; renaming is preferable.

Attribute Renaming

  • Use the AS clause to rename attributes.
  • Example: SELECT lastName, salary * 1.1 AS projected FROM Doctor;
  • Resulting attribute name is “projected”.

Star (*)

  • Use SELECT * FROM Doctor; to retrieve all attributes.
  • Useful when you don't know the attribute names.

Conditions

  • Use the WHERE clause to specify conditions for tuple retrieval.
  • Example: SELECT ssn, firstName FROM Doctor WHERE (salary < $130K AND lastName = ‘Patel’) OR salary > $170K;
  • Boolean conditions can use AND, OR, NOT.
  • Comparison operators:

Null Values

  • Use IS NULL or IS NOT NULL to handle empty values.
  • Example: SELECT ssn FROM Patient WHERE middleName IS NOT NULL;

Sorting Results

  • Use the ORDER BY clause to sort tuples.
  • Example: SELECT ssn, lastName FROM Doctor ORDER BY lastName ASC, salary DESC;
  • ASC for ascending, DESC for descending order.
  • Warning: Sorting can be computationally expensive.

INSERT, UPDATE, DELETE

  • INSERT INTO … SELECT …;
  • DELETE FROM … WHERE …;
  • UPDATE … SET … WHERE …;
  • Use SELECT queries to add data.
  • Use conditions to specify tuples for deletion or updates.

Aggregation Functions

  • SQL has 5 built-in aggregation functions: AVG, MIN, MAX, SUM, COUNT.

Basic Aggregation Queries

  • Example: SELECT MIN(salary) FROM Doctor WHERE dob >= ‘1986-01-01’;
  • Retrieves a single value (e.g., minimum salary).

Grouping

  • Use the GROUP BY clause to compute multiple aggregations.
  • Tuples with the same value on attributes in the GROUP BY clause are placed in one group.
  • Example: SELECT lastName, AVG(salary) FROM Doctor WHERE salary < $170K GROUP BY lastName;

Having

  • Use the HAVING clause to filter groups created by GROUP BY.
  • Example: SELECT lastName, AVG(salary) FROM Doctor GROUP BY lastName HAVING AVG(salary) > $140K

String Operations

  • Use the LIKE clause for pattern matching in strings.
  • LIKE ‘Smit%’ (starts with Smit).
  • LIKE ‘%oor%’ (contains oor).
  • LIKE ‘ _ _ _ ’ (3 characters).
  • LIKE ‘ _ _ _ %’ (at least 3 characters).
  • Warning: String comparisons can have bad performance.

No Indexes!

  • Example: SELECT ssn FROM Doctor WHERE lastName LIKE ‘Smit%’;
  • Without an index on lastName, this query will be slow.

Indexes

  • Data structure that facilitates efficient queries over attributes in a relation.
  • Similar to an index in a book.

Indexes for Primary Keys

  • Every primary key is automatically indexed.

Index Everything?

  • Creating indexes for all relations and columns is not reasonable.
  • Indexes speed up queries but slow down updates and take up disk space.

B+-Tree

  • Index implementation using a tree structure.
  • Each node has a sorted list of attribute values.
  • Follow pointers to find the row.

Hashing

  • Index implementation based on hashing.
  • Select a bucket according to the hashing of an attribute (e.g., instructor's department).

Indexes in MySQL

  • CREATE INDEX PersonBirthDate ON Person(birthDate) [USING {BTREE | HASH}];
  • Specify index implementation (BTREE by default).

B+-Tree Index Rules

  • Allowed: =, >,
  • Not allowed: <>, LIKE '%ZZZ%', lastName LIKE firstName (non-constant).

Hash Index Rules

  • Allowed: =, <>
  • Not allowed: anything else.

Not Only Strings

  • Indexes can be applied to dates, integers, or binaries.

Fulltext Indexes

  • Useful for substring searches.

Inverted Index

  • List relating each word to the unique identifier of an entity.
  • Example for otherNotes attribute of visits: Word -> (ssn, scheduled date).

N-grams

  • Divide a string value into sequences of nn values.
  • Example: occupation of every patient for queries like “patients that work in bio.”
  • 3-grams are popular.

Fulltext Indexes in MySQL

  • CREATE FULLTEXT INDEX VisitOtherNotes ON Visit(otherNotes);
  • MySQL uses inverted index to implement fulltext indexes.

Regular vs. Fulltext Indexes

  • Example for regular index: SELECT ssn FROM Doctor WHERE lastName LIKE ‘Smit%’;
  • Example for fulltext index: SELECT ssn FROM Doctor WHERE MATCH(lastName) AGAINST(‘rivero,Smith');
  • Regular indexes are automatically managed, while fulltext indexes need to be explicitly invoked.

Natural Language Mode

  • Looks for case-insensitive keywords.

Boolean Mode

  • Allows including and excluding substrings.
  • SELECT ssn FROM Doctor WHERE MATCH(lastName) AGAINST(‘+bu* -burt‘ IN BOOLEAN MODE);
  • Wildcards allowed with fixed characters at the beginning.

Cartesian Product and Renaming

  • If we perform the query that you see in this slide, we will retrieve a Cartesian product between the Doctor and Patient relations.
  • Performing Cartesian products has a very bad performance, how can we avoid them?
  • Example: SELECT * FROM Doctor AS d, Patient AS p;
  • Relationships are renamed using AS.
  • Warning: Cartesian products have bad performance.

"Handmade" Joins

  • SELECT d.lastName, p.lastName FROM Doctor AS d, Patient AS p WHERE p.primaryDoctor = d.ssn;
  • Specifies attributes to compare.
  • Avoid this notation; use the ON clause instead.

Joins Using ON

  • SELECT d.lastName, p.lastName FROM Doctor AS d JOIN Patient AS p ON p.primaryDoctor = d.ssn;
  • Equivalent to “handmade” join but clearer.
  • Keep join condition separate from other filtering conditions.

Cartesian Product and Filter

  • A join is composed of a Cartesian product and a filter.

"Self" Joins

  • Used to query tree relationships.
  • SELECT DISTINCT sr.lastName FROM Doctor AS sr JOIN SupervisedBy ON sr.ssn = supervisor JOIN Doctor AS se ON se.ssn = supervisee WHERE se.salary > $100K;

Interpretation of Joins

  • For each tuple in Doctor, combine it with each tuple in Patient.
  • If the join condition is met, add to the result.
  • Implies performing a Cartesian product, which is inefficient.

Interpretation is Not Implementation!

  • SQL is declarative; specify what, not how.
  • SQL query engines aim to efficiently implement queries.

Strategies to Implement Joins

  • Nested-loop
  • Sort-merge
  • Hash

Nested-Loop, O(n2)O(n^2)

  • Traditional implementation with nested loops.
  • If the join condition is fulfilled, add the combination of tuples to the result.

Sort-Merge, O(nlog⁡n)O(n \log n)

  • Sort both relations and iterate simultaneously.

Hash, O(n)O(n)

  • Hash all values of primaryDoctor for Patient.
  • Iterate through Doctor and find its hash in the lookup table.

Set Operations

  • Union
  • Intersection
  • Difference

Commonalities of Set Operations

  • Operate on two relations.
  • Relations must have the same number of attributes and names.
  • Automatically remove duplicates (like DISTINCT).

Union

  • `SELECT lastName FROM Patient WHERE dob >= ‘1980-09-01’ UNION SELECT lastName FROM Doctor WHERE dob >= ‘1980-09-01’;
  • Retrieves last names of people born on or after Sep 1, 1980.

Intersection (Not in MySQL)

  • SELECT ssn FROM Doctor INTERSECT SELECT ssn FROM Patient;
  • Doctors who are also patients.

Difference (Not in MySQL)

  • SELECT ssn FROM Doctor EXCEPT SELECT primaryDoctor AS ssn FROM Patient;
  • Doctors that are not primary doctors of any patient.
  • The order of relations is important.

Nesting Queries

  • Use closure property to perform nested queries.

Set Membership

  • Use the IN clause to test set membership.
  • SELECT DISTINCT lastName FROM Doctor AS d JOIN Patient ON d.ssn = primaryDoctor WHERE d.ssn IN ( SELECT supervisee FROM SupervisedBy JOIN Doctor ON supervisor = ssn WHERE salary > $100K);

Set Comparison (1)

  • SQL allows us to compare a value over a set. If we wish to express “greater than at least one”, we can use > SOME
  • > SOME (greater than at least one).
  • SELECT ssn FROM Doctor WHERE salary > SOME ( SELECT salary FROM Doctor JOIN SupervisedBy ON ssn = supervisor);
  • SQL allows <, <=, >, >=, =, and <> with SOME.

Set comparison (2)

  • Similarly, we are able to express “greater than all”, so we use the ALL clause to define this condition
  • > ALL (greater than all).
  • SELECT ssn FROM Doctor WHERE salary > ALL ( SELECT salary FROM Doctor JOIN SupervisedBy ON ssn = supervisor);

Empty/Non-Empty Sets

  • “The EXISTS clause tests for empty sets produced by a SELECT subquery.”
  • SELECT ssn FROM Doctor AS d WHERE firstName LIKE ‘Reg%’ AND EXISTS ( SELECT COUNT(doctor) FROM Visit WHERE doctor = d.ssn AND scheduled BETWEEN ’2015-09-01’ AND ’2016-08-31’ HAVING COUNT(doctor) >= 3);
  • EXISTS
  • Scoping rules apply similar to variables in programming languages.

Road Map Query Execution

  • Let’s study now how the query engine optimizes and executes the queries.

SQL is a declarative language

  • Remember that one of the properties of SQL is that it is a declarative language, which means that we specify what to retrieve but not how, the query engine is responsible for implementing the how. How is the query engine doing that?

Relational algebra expression

  • A query in SQL is automatically translated into a relational algebra expression. Let’s study relational algebra.
  • \LARGE \pi{d.lastName, p.lastName} \sigma{salary > $100K} \sigma_{d.ssn = primaryDoctor} \times Doctor X Patient

Procedural

  • Relational algebra is a procedural language, which means that a query is executed step by step in the same way as it is expressed.

Restriction

  • We use sigma to denote a restriction operation in which we filter the tuples of a relation, in our example, we are retrieving just those doctors whose last name is Smith and has a salary less than $100K. We may use ˄ (and), ˅ (or) and ¬ (not) for Boolean expressions and =, ≠,
  • \sigma_{lastName = \"Smith\" ˄ salary < $100K} Doctor

Projection

  • Projection allows us to retrieve a new relation with just the attributes (columns) specified there. In this example, we are removing all attributes of the Doctor relation except of lastName and salary. The main different with respect to SQL is that, in this case, we remove duplicates since, in the formal language, a relation is a set and, therefore, tuples with the same content can appear only once.
  • πlastName,salaryDoctor\pi_{lastName, salary} Doctor

Composing Operations

  • We are able to compose operations by nesting them. In this case, we are restricting the Doctor relation and projecting just the last name.
  • \pi{lastName} \sigma{lastName = \"Smith\" ˄ salary < $100K} Doctor

Cartesian product

  • Cartesian product combines all tuples of two given relations into one single relation. In this case, we are combining Doctor and Patient relations. Check that attributes in the final relation may have exactly the same names, so we concatenate the name of the relation to differentiate among them.
  • Doctor×PatientDoctor \times Patient

Joins with cartesian product

  • We can combine Cartesian products with a restriction to obtain a join.
  • σd.ssn=primaryDoctorPatient×Doctor\sigma_{d.ssn = primaryDoctor} Patient \times Doctor

Other (basic) operations

  • Relational algebra allows three more basic operations: set union, set difference, and renaming.
  • Union (∪)
  • Difference (-)
  • Rename (ρ)

Mandatory for query optimization!

  • Relational algebra is the language that allows us optimize our queries in a relational database, let’s see how it works.

Equivalent expressions

  • The same relational algebra expression may have multiple equivalent expressions and not all of them have the same performance. In the next step, the query engine is responsible for evaluating all of these alternatives and selecting the one that is going to perform better. This is done by estimating the costs of the operations. In this example, check that the original expression is computing the whole Cartesian product between Doctor and Patient, however, we are only interested in doctors whose salary is greater than $100K, therefore, we are able to filter out doctors that are not of our interest. As a result, we predict that the right expression is going to perform better than the original one and we select it to be executed.
  • \pi{d.lastName, p.lastName} \sigma{salary > $100K} \sigma_{d.ssn = primaryDoctor} \times Doctor Patient

Execution plan

  • Once the query engine has chosen a relational algebra expression, it is translated into an execution plan over the physical model.

Operations over the physical model

  • MySQL allows us to visualize the plan. Check that, in this case, it is using an index over salary to retrieve only those doctors whose salary is greater than $100K. Then, it is using a nested loop that is using a primary key lookup over patients. As you can see, the execution plan contains the indexes that it is going to use and the algorithms to access the structures.

Access Using JDBC

  • Access using JDBC
  • Remember that we already saw how to have programmatic access to MySQL using JDBC. We are going to study now transactions and how to prevent SQL injections.

Preventing SQL Injection

  • SQL injection is used to attack relational databases.
  • It consists of adding malicious SQL statements to exploit security vulnerabilities.
  • Example:
    • Vulnerable code: "SELECT * FROM users “ + “WHERE name ='"; + userName + "';"
    • Malicious input: userName = “' OR '1'='1”

Use a PreparedStatement!

  • To prevent SQL injections, use PreparedStatement.
  • Example:
    • "SELECT * FROM users “ + “WHERE name = ?;"
    • ps.setString(username);

Malicious People Out There!

  • Always use PreparedStatement to prevent SQL injection attacks.

Conclusion

  • Studied SQL for data retrieval.
  • Covered joins, aggregations, and set operations.
  • Explained SQL programming and relational algebra.

Relational Algebra

  • Reviewed relational algebra and execution plans.

  • \pi{d.lastName, p.lastName} \sigma{salary > $100K} \sigma_{d.ssn = primaryDoctor} \times Doctor Patient

  • It is not ethic (and illegal!) to make choices based on race, gender, religion, or origin

  • Careful with unintended consequences

  • Retrieve people with last name Rivera (these are likely to come from Latin America and be Catholic)

  • Aggregating/omitting information does not necessarily preserve privacy

  • A large percentage of people in the US can be identified by using ZIP code, birth date, and gender

  • In a professional environment, how to behave when facing these issues?