undefined | Better HN

0 pointsmunk-a4y ago0 comments

I had a specific class on relational algebra in uni and it is up there with algorithm design and analysis in the realm of classes that actually provided me the most long term value.

Relational algebra is a lot easier once you start viewing it as relational algebra - a declarative expression of intent that can be manipulated and re-expressed similar to other purely mathematical statements. Then, when performance tuning becomes the watchword, you take that flexible expression and slice and dice it according to how the DBMS you're working with requires to align it with performance. You always want to think of your queries as complex summoning spells that draw in different necessary resources in some particular patterns and then impose an expression form on that blob of data - then you'll skate through all things SQL.

0 comments

dragontamer4y ago

Relational algebra comes from my study of constraint programming / optimization (a closely related field to 3SAT solvers).

From this perspective, the study of relations is more about solving these NP-hard problems. For example, coloring a graph. You can solve things "locally", such as:

    Texas | New Mexico | Oklahoma
    -----------------------------
    Red   | Blue       | Green
    Red   | Blue       | Yellow
    Red   | Green      | Blue
    Red   | Green      | Yellow
    Red   | Yellow     | Blue
    Red   | Yellow     | Green
    Blue  | Red        | Green
    Blue  | Red        | Yellow
    Blue  | Green      | Red
    Blue  | Green      | Yellow
    ...
    (etc. etc. for all other valid combinations)

And so on for each "locally valid graph coloring" (looking only at a limited number of states). You then combine all of these relations together to find a solution to the 4-coloring problem.

We can see that "solving" a 4-coloring problem is as simple as a cross-join over all these relations (!!!). That is: Texas_NewMexico_Okalhoma cross-join Texas_Oklahoma_Louisiana cross-join Louisiana_Mississippi_Arkansas cross-join ...

We can see immediately that "Texas_NewMexico_Okalhoma cross-join Texas_Oklahoma_Louisiana" will create a new relation, a "Texas_NewMexico_Oklahoma_Louisiana" table, though with the information from just two earlier tables, this new table is "incomplete" so to speak (you'll need to join this table with many other Texas, NewMexico, Oklahoma, and Louisiana tables to ensure global consistency).

We can imagine a big 48-wide table consisting of the 48 states of USA as the final solution to a graph coloring problem. Successful calculation of this massive table will enumerate all possible solutions (!!) of the graph coloring problem.

----------------

Somehow, I find it more obvious to understand relations from this perspective. If anything, learning about constraint programming has made my relational algebra better (and as a result, has made my database skills probably better too)

Its also a funny corner where if you "study relations" hard enough, you eventually reach NP complete problems. 3SAT is easily written in the form of database relations after all :-) (But using a database as a 3SAT solver is probably a bad idea, despite being mathematically connected)

j / k navigate · click thread line to collapse