How might indexes be represented in the context of relational algebra?
How would an optimizer transform a query to use indexes?
5
-
$\begingroup$ I'm no expert, but I'd say indexes are an implementation detail. $\endgroup$– adrianNCommented Oct 6, 2017 at 14:44
-
2$\begingroup$ This is actually an extremely smart question and you are probably not going to get the response you deserve. The question is much more "how can we model index selection in an extension of relational algebra" and it would probably require some fundamentally new mathematics: possibly new "index operators" operating on the basis sets which only commute with projection operators that prefix the index, and then one chooses the indices that can be commuted to the front of an expression or something. $\endgroup$– CR DrostCommented Oct 6, 2017 at 18:17
-
$\begingroup$ No, no, no! RA can already express the logic behind indexes; needs no extension; is already a fundamental system of mathematics (actually logic). The 'A' stands for Algebra. Sheesh! $\endgroup$– AntCCommented Oct 9, 2017 at 4:15
-
$\begingroup$ @AntC Please give an example where relational algebra expresses indices. $\endgroup$– Elastic LambCommented Oct 9, 2017 at 7:04
-
$\begingroup$ See my full answer: they're expressed in constraints/dependencies like FDs and Inclusion Dependencies. It's a question of the logic of the schema (SQL CREATE ASSERTION); indices are an implementation detail to support the logic. $\endgroup$– AntCCommented Oct 9, 2017 at 7:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes what you must do, but not how you must do it.
It is comparable to the multiplication and other operations of the elementary arithmetic. There is a definition of what multiplying is but not of the way how you have to do it. There are several algorithms to multiply two numbers but the results are all equal. For further information see Wikipedia (What does it mean to multiply two natural numbers?).
Relating to your question that means that the result of an operation is the same with or without indices. The only difference is the increasing performance if you use indices.
$\begingroup$
$\endgroup$
2
@Elastic Lamb's answer is so terribly wrong in so many ways, I have to respond.
Relational Algebra is a practical/executable implementation of a system of logic, expressively equivalent to First Order Predicate Logic. In FOPL, you can state truths about the subject matter -- that's the what. RA corresponds to FOPL and -- exactly -- formulates the how. That's exactly the purpose for RA established by Codd's Theorem at the dawn of Relational Theory 1972
As well as truths like 'Employee E123 works in Department D456 ...' -- that is represented by a tuple in the Employee relation; or 'Employees in Departments D450 to D459' -- a query; you can state truths like 'Employee number uniquely identifies an Employee'; 'for all Employees, the Department each works in must be uniquely identified by a Department number which has a name'.
Those what we might call 'structural' truths are typically expressed in the database schema; and you can see those example truths express keys (uniqueness contraints/Functional Dependencies) and foreign keys (Inclusion Dependencies). Constraints/Dependencies are merely queries that return a Boolean result, and must always return True for the database content to be valid according to the business rules expressed in the schema.
So a practical implementation of RA would build indexes for rapidly validating updates, and give faster response to queries (which typically JOIN across FKs).
Most SQL engines under the hood convert your query to an algebraic form much more like RA. Then they can transform the RA expression using well-known equivalences; and how to transform will depend on what indexes are available, together with statistics about the content of relations and the clustering of keys around indexes. You can see that in practice by getting the query engine to explain its query plan. RA is crucial to the how, because SQL is not an algebra, not structured, barely a language.
-
$\begingroup$ Unique constraints, FD and so on are not part of relational algebra. It is even possible to design a query language which is (strong) equivalent to relational algebra but does not support indices. $\endgroup$ Commented Oct 9, 2017 at 9:31
-
$\begingroup$ Candidate keys are very-much part of the relational algebra, and by extension, so are unique constraints. The OP's question has validity if only to provide a notation in which we can holistically describe the runtime characteristics of a query. $\endgroup$– duretteCommented Jun 10, 2018 at 4:31