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.
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!
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).
Comments
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.
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!
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).
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?