Declarative Query Processing in Relational Database Systems - Automated Physical Database Design and Tuning - page 7

inside countMatches itself and therefore avoid the initial filtering step. If ele-
ments in S are sorted, we could use a modified version of countMatches4
that skips over elements in R that are greater than 500 and employs binary
search only on the remaining (very few) elements to compute our result with-
out reading S completely. Implementing such complex strategies generically
is far from simple, since in our example filtering and countMatches interact
with and have to be aware of each other (it gets progressively more dicult
as our repertoire of routines grows). Imagine if our task is to obtain triplets of
matching values among three tables by reusing or extending countMatches !
In general, for each routine to be fully composable while still retaining declar-
ative capabilities, we need to create some sort of meta-environment to reason
with each routine both separately and in conjunction with others (clearly not
a straightforward task). In effect, this is precisely the feature set that the
declarative query processing capabilities of the SQL provide.
1.2 SQL: Declarative Query Processing
Structured Query Language is a declarative language designed for querying
and updating data in relational database management systems (DBMSs). The
data model in SQL is simple. All information in a database is structured in ta-
bles, which are defined as multisets of rows (rows are also called tuples). Each
row, in turn, contains one value for each typed column in the table. Suppose
that we want to model information about employees working in departments.
We could then use two tables, shown in Figure 1.2. In the figure, each row in
table Emp represents one employee and contains the employee's ID (column
EId ), name, title, and salary as well as the ID of the department the employee
works in ( DId ) and the ID of the employee's manager ( MId ). In turn, each
row in table Dept represents a department and contains the department ID
( DId ), a description, the city where the department is located, and its yearly
budget. We represent the relationship of an employee working in a department
by matching DId values in the Emp and Dept tables.
SQL queries take tables as inputs and return tables as outputs and can
therefore be easily composable. The generic form of a SQL query is as follows:
SELECT expressions
FROM relational inputs
WHERE predicate
GROUP BY columns
HAVING predicate
ORDER BY columns
The FROM clause defines the query data sources, which can be either
database tables or nested SQL queries themselves. By definition, the combined