Hacker News new | ask | show | jobs
by thinkpad20 4638 days ago
Looks really interesting. I wrote an SQL parser and compiler frontend for a SQLite-style database last summer. I started off in C using Lex/Yacc, but for the last piece of the project I used Haskell. This step was to take SRA ("sugared relational algebra"), which is essentially a transition step between SQL and simple relational algebra, and desugar it into relational algebra. The code is up at https://github.com/thinkpad20/sql if anyone is interested, with the code for that portion being contained in the haskell folder. I might translate the whole thing into Haskell (maybe using Attoparsec) at some point.

I was curious that you used a different version of relational algebra than the one I had been taught. I've usually seen RA described in terms of six fundamental operators: Project (pi), Select (sigma), Rename (rho), Cross Product, Union and Difference. What gave rise to the model you chose?

Anyway, it's great to see that more people are using Haskell. I would love to be able to work in it some day.
1 comments
jakewheat 4638 days ago
That is really fascinating, I will have a good look at that, thanks! I have a SQL parser in Haskell on github here (using Parsec): https://github.com/JakeWheat/hssqlppp

The model in the article is roughly based on the version in Date and Darwen's work which is almost the same as what you mention: project, rename, extend, join, union and not matching. The summarize by is kind of syntax sugar in this system. I left out some of the operators which weren't used anywhere in the code in the article. Industrial grade conversion from SQL to relational algebra is a real challenge!

link
thinkpad20 4638 days ago
Wow, your parser is a behemoth! My parser ended up being around 500 lines of Yacc. I know I didn't fully implement SQL, but I thought I had gotten pretty close. Are you doing any extra fancy stuff inside of the parser? Clearly the documentation is pretty extensive. I like the lhs work; I might start doing some of my projects in LHS.

SQL to RA is definitely quite a task, but it was pretty fun (up until the end, when it just started getting annoying...). Then again, I think compilers and programming languages are a blast anyway. Haskell makes it even more so :)

When I wrote this code, I wasn't really comfortable using monads, so all of the threading is explicit. If I were to revisit it, I would probably use a state monad, which might also make it easier to make it tail-recursive (as it is, my desugarer is not written in a tail-recursive manner).

link
jakewheat 4638 days ago
The parser also does typechecking, and attempts to cover a good subset of DML, DDL and procedural SQL as well. Maybe it could be smaller!

How would you handle correlated subqueries when converting from SQL to RA?

link