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", thenSELECT 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:
DISTINCTis 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
DISTINCTblindly; 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
ASclause 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
WHEREclause 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 NULLorIS NOT NULLto handle empty values. - Example:
SELECT ssn FROM Patient WHERE middleName IS NOT NULL;
Sorting Results
- Use the
ORDER BYclause to sort tuples. - Example:
SELECT ssn, lastName FROM Doctor ORDER BY lastName ASC, salary DESC; ASCfor ascending,DESCfor descending order.- Warning: Sorting can be computationally expensive.
INSERT, UPDATE, DELETE
INSERT INTO … SELECT …;DELETE FROM … WHERE …;UPDATE … SET … WHERE …;- Use
SELECTqueries 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 BYclause to compute multiple aggregations. - Tuples with the same value on attributes in the
GROUP BYclause are placed in one group. - Example:
SELECT lastName, AVG(salary) FROM Doctor WHERE salary < $170K GROUP BY lastName;
Having
- Use the
HAVINGclause to filter groups created byGROUP BY. - Example:
SELECT lastName, AVG(salary) FROM Doctor GROUP BY lastName HAVING AVG(salary) > $140K
String Operations
- Use the
LIKEclause 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
otherNotesattribute of visits: Word -> (ssn, scheduled date).
N-grams
- Divide a string value into sequences of 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
ONclause 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,
- Traditional implementation with nested loops.
- If the join condition is fulfilled, add the combination of tuples to the result.
Sort-Merge,
- Sort both relations and iterate simultaneously.
Hash,
- Hash all values of
primaryDoctorfor 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
INclause 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<>withSOME.
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.
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.
Joins with cartesian product
- We can combine Cartesian products with a restriction to obtain a join.
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”
- Vulnerable code:
Use a PreparedStatement!
- To prevent SQL injections, use
PreparedStatement. - Example:
"SELECT * FROM users “ + “WHERE name = ?;"ps.setString(username);
Malicious People Out There!
- Always use
PreparedStatementto 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?