Обсуждение: [GENERAL] Imperative Query Languages
Hi All,
This more of a general interest than specifically Postgres question. Are there any “semi-imperative” query languages that have been tried in the past? I’m imagining a language where something like this:
for employee in employees: for department in department: if employee.department == department.department and department.name == "infosec": yield employee.employee, employee.name, employee.location, employee.favorite_drink
would be planned and executed like this:
SELECT employee.employee, employee.name, employee.location, employee.favorite_drink FROM employee JOIN department USING (department)WHERE department.name == "infosec"
The only language I can think of that is vaguely like this is Fortress, in that it attempts to emulate pseudocode and Fortran very closely while being fundamentally a dataflow language.
Kind Regards,
Jason
(copying the list)
Are there any “semi-imperative” query languages that have been tried in the past?
not particularly relevant to the Unix or Windows worlds, but on OpenVMS there's Datatrieve:
-John
On Wed, Jul 5, 2017 at 12:22 AM, Jason Dusek <jason.dusek@gmail.com> wrote:
Hi All,
This more of a general interest than specifically Postgres question. Are there any “semi-imperative” query languages that have been tried in the past? I’m imagining a language where something like this:
for employee in employees: for department in department: if employee.department == department.department and department.name == "infosec": yield employee.employee, employee.name, employee.location, employee.favorite_drinkwould be planned and executed like this:
SELECT employee.employee, employee.name, employee.location, employee.favorite_drink FROM employee JOIN department USING (department)WHERE department.name == "infosec"The only language I can think of that is vaguely like this is Fortress, in that it attempts to emulate pseudocode and Fortran very closely while being fundamentally a dataflow language.
Kind Regards,
Jason
Jason Dusek <jason.dusek@gmail.com> writes:
> This more of a general interest than specifically Postgres question. Are
> there any “semi-imperative” query languages that have been tried in the
> past? I’m imagining a language where something like this:
> for employee in employees:
> for department in department:
> if employee.department == department.department and
> department.name == "infosec":
> yield employee.employee, employee.name, employee.location,
> employee.favorite_drink
I'm pretty sure that that is the model that relational databases (and the
SQL language in particular) replaced, back in the 70s or so. Look up
"network" databases (eg CODASYL) and "hierarchical" DBs (eg IMS) for some
ancient history here. Yeah, you can do it like that, but it's seriously
painful to develop and maintain. People were more excited about spending
human effort to save machine cycles forty years ago than they are today.
regards, tom lane
On Wed, Jul 5, 2017 at 7:22 AM, Jason Dusek <jason.dusek@gmail.com> wrote:
Hi All,
This more of a general interest than specifically Postgres question. Are there any “semi-imperative” query languages that have been tried in the past? I’m imagining a language where something like this:
for employee in employees: for department in department: if employee.department == department.department and department.name == "infosec": yield employee.employee, employee.name, employee.location, employee.favorite_drinkwould be planned and executed like this:
SELECT employee.employee, employee.name, employee.location, employee.favorite_drink FROM employee JOIN department USING (department)WHERE department.name == "infosec"The only language I can think of that is vaguely like this is Fortress, in that it attempts to emulate pseudocode and Fortran very closely while being fundamentally a dataflow language.
Having done a lot of SQL optimisation stuff I have doubts that this is possible. The problem is that it is much easier to go from a declarative to an imperative plan than it is to go the other way. In fact sometimes we use SQL the way your first code works and then it is often a problem.
For example, consider the difference between an EXISTS and an IN query, or between an INNER JOIN and a LATERAL JOIN. PostgreSQL's optimiser is amazing at identifying cases where these are equivalent and planning accordingly, but it is extremely easy to get just outside the envelope where the optimiser gives up and has to default back to an imperative interpretation of these. Proving that two imperative approaches are equivalent is a lot harder than proving that two different imperative approaches implement the same declarative request. In other words, going imperative -> declarative strikes me as a far, far harder problem than the other way.
Also I have done a little bit of work on Apache Spark and there it is extremely important to understand the imperative side of the data flow in that case (what is partitioned and what is not).
--
Best Wishes,
Chris Travers
Efficito: Hosted Accounting and ERP. Robust and Flexible. No vendor lock-in.
On Tue, 4 Jul 2017 at 23:22 Chris Travers <chris.travers@gmail.com> wrote:
Having done a lot of SQL optimisation stuff I have doubts that this is possible. The problem is that it is much easier to go from a declarative to an imperative plan than it is to go the other way. In fact sometimes we use SQL the way your first code works and then it is often a problem.For example, consider the difference between an EXISTS and an IN query, or between an INNER JOIN and a LATERAL JOIN. PostgreSQL's optimiser is amazing at identifying cases where these are equivalent and planning accordingly, but it is extremely easy to get just outside the envelope where the optimiser gives up and has to default back to an imperative interpretation of these. Proving that two imperative approaches are equivalent is a lot harder than proving that two different imperative approaches implement the same declarative request. In other words, going imperative -> declarative strikes me as a far, far harder problem than the other way.Also I have done a little bit of work on Apache Spark and there it is extremely important to understand the imperative side of the data flow in that case (what is partitioned and what is not).
I can not argue these points with you; but Fortress is a good example of imperative looking code that translates to a functional/declarative core; as indeed is monadic or applicative code. LINQ is a more recent and widespread example -- though not encompassing an entire language -- of something that has an imperative form while being declarative under the hood. Scala's for comprehensions -- more or less monad comprehensions --are another.
With regards to Spark, I assume for comprehensions are an important part of the interface?
Kind Regards,
Jason
On Wed, Jul 5, 2017 at 8:34 AM, Jason Dusek <jason.dusek@gmail.com> wrote:
I can not argue these points with you; but Fortress is a good example of imperative looking code that translates to a functional/declarative core; as indeed is monadic or applicative code. LINQ is a more recent and widespread example -- though not encompassing an entire language -- of something that has an imperative form while being declarative under the hood. Scala's for comprehensions -- more or less monad comprehensions --are another.
But Linq effectively is a declarative language that's semi-SQL-like (I wish they used "project" instead of "select" but that's another question). I don't see Linq as semi-imperative.
With regards to Spark, I assume for comprehensions are an important part of the interface?
Nope. You have chained generators and you really need to watch what is parallelizable and what is not, and what is running on the partitions and what is running post-gathering/shuffling. Spark has no real facility for parallelising a comprehension.
Kind Regards,Jason
Best Wishes,
Chris Travers
Efficito: Hosted Accounting and ERP. Robust and Flexible. No vendor lock-in.
On Tue, 4 Jul 2017 at 23:01 Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm pretty sure that that is the model that relational databases (and the
SQL language in particular) replaced, back in the 70s or so. Look up
"network" databases (eg CODASYL) and "hierarchical" DBs (eg IMS) for some
ancient history here. Yeah, you can do it like that, but it's seriously
painful to develop and maintain. People were more excited about spending
human effort to save machine cycles forty years ago than they are today.
Network database programming is, indeed, imperative; but as I understand it there was not much of a planning layer -- the program was the plan. In C#, one has LINQ; and in Scala and Haskell, monadic comprehensions; and even in Python one can overload iteration to allow a translation of imperative syntax to declarative syntax. The goal with these features, is generally to present a familiar interface to an unfamiliar semantics.
If we imagine network databases have one layer:
Imperative Plan
And SQL databases have two:
Declarative Query -> Imperative Plan
It seems reasonable to say, LINQ, &al. have three:
Imperative Syntax -> Declarative Query -> Imperative Plan
Fortress is rather the same, since it translates imperative to functional to assembly.
Kind Regards,
Jason
On Wed, Jul 5, 2017 at 8:42 AM, Jason Dusek <jason.dusek@gmail.com> wrote:
If we imagine network databases have one layer:Imperative PlanAnd SQL databases have two:Declarative Query -> Imperative PlanIt seems reasonable to say, LINQ, &al. have three:
Imperative Syntax -> Declarative Query -> Imperative PlanFortress is rather the same, since it translates imperative to functional to assembly.
I am curious where you see LINQ as starting at an imperative syntax.
Here's a good case that illustrates the problem I think. Suppose the following is understood imperatively:
FOR x IN RANGE student
SELECT WHERE x.age < 25
PROJECT ALL(x), lock_if_possible(x.id)
Now, lock_if_possible has side effects. If we understand this to be imperative, then we have no possibility of turning this into a declarative query because we are interested in the side effects. So you cannot say that this is equivalent to the SQL of
SELECT *, lock_if_possible(id)
FROM student
WHERE age < 25
The reason is that while the imperative version represents *one* valid interpretation of the declarative, there are other interpretations of the declarative that are not at all equivalent. The hoops we have to jump through to make this work in an imperative way in SQL are sometimes rather amusing.
Kind Regards,Jason
Best Wishes,
Chris Travers
Efficito: Hosted Accounting and ERP. Robust and Flexible. No vendor lock-in.
On Tue, 4 Jul 2017 at 23:57 Chris Travers chris.travers@gmail.com wrote:
I am curious where you see LINQ as starting at an imperative syntax.
The imperative integration is thin, I admit — it just the integration with for loops.
Here's a good case that illustrates the problem I think. Suppose the following is understood imperatively:FOR x IN RANGE studentSELECT WHERE x.age < 25PROJECT ALL(x), lock_if_possible(x.id)Now, lock_if_possible has side effects. If we understand this to be imperative, then we have no possibility of turning this into a declarative query because we are interested in the side effects. So you cannot say that this is equivalent to the SQL ofSELECT *, lock_if_possible(id)FROM studentWHERE age < 25The reason is that while the imperative version represents *one* valid interpretation of the declarative, there are other interpretations of the declarative that are not at all equivalent. The hoops we have to jump through to make this work in an imperative way in SQL are sometimes rather amusing.
What are some alternative interpretations of this query? Are you referring to which rows are candidates for locking? Or the order of locking?
Kind Regards,
Jason
On Wed, Jul 5, 2017 at 12:22 AM, Jason Dusek <jason.dusek@gmail.com> wrote: > Hi All, > > This more of a general interest than specifically Postgres question. Are > there any “semi-imperative” query languages that have been tried in the > past? I’m imagining a language where something like this: huh. Somewhat snarky answer, all of them? :-). Most languages are imperative including just about all the ones that are popular in "the enterprise" (minus SQL). You can for example code that looks remarkably like that in pl/pgsql. Since postgres is a SQL server, it would have to get compiled down to boring SQL statements but it's generally understood (at least by me) that this is an inefficient way to write code. Downthread, Tom mentions CODASYL, etc, but could have mentioned the big daddy, ISAM, and all it's various flavors. Virtually all business code was written using it (and much of it still is) leading into the SQL era. Code generally looked exactly like your example, except it was much more stupid looking being written in (generally) COBOL, and added in error handling, which is where the technique tends to break down. SQL came about because some particularly smart people realized that programmers were writing the same boiler plate code over and over again and that perhaps access to data could be generalized and focused down to the real problem being solved. This fortunately came about before "enterprise developers" and "enterprise tool vendors" were as organized as they are today and so was able to germinate into something incredibly useful... This revolution in programming was IMNSHO the single greatest innovation in computer science; so much so that legions of the unenlightened have been tirelessly working (hibernate) to eliminate or displace its benefits, without much success: http://www.codingdojo.com/blog/9-most-in-demand-programming-languages-of-2016/ :-D merlin
On Wed, Jul 5, 2017 at 7:02 AM, Merlin Moncure <mmoncure@gmail.com> wrote: > Downthread, Tom mentions CODASYL, etc, but could have mentioned the > big daddy, ISAM, and all it's various flavors. Virtually all business > code was written using it (and much of it still is) leading into the > SQL era. Code generally looked exactly like your example, except it > was much more stupid looking being written in (generally) COBOL, and > added in error handling, which is where the technique tends to break > down. SQL came about because some particularly smart people realized > that programmers were writing the same boiler plate code over and over > again and that perhaps access to data could be generalized and focused > down to the real problem being solved. This fortunately came about > before "enterprise developers" and "enterprise tool vendors" were as > organized as they are today and so was able to germinate into > something incredibly useful... To state the very obvious: If you assume for the sake of discussion that the programmer of a hypothetical imperative query language is infinitely capable and dedicated, and so is at least as capable as any possible query optimizer, the optimizer still comes out ahead, because it is capable of producing a different, better query plan as the underlying data changes. Of course, it's also true that it's very hard to beat the query optimizer under ideal conditions. However, the OP seemed to be describing something that maps imperative code to a declarative SQL query or something equivalent, which isn't quite the same thing. The declarative nature of SQL feels restrictive or at least unfamiliar to many programmers. What is often somehow missed is that it's restrictive in a way that's consistent with how the relational model is supposed to work. It seems hard to some programmers because you have to formulate your query in terms of an outcome, not in terms of a series of steps that can be added to iteratively, as a snippet of code is written. It's very different to something like bash, because it requires a little bit of up-front, deliberate mental effort. And, because performance with many different possible outputs matters rather a lot. IMV, what the OP describes wouldn't work well because it would superficially *appear* to not be restrictive in the way that some people dislike, but actually would be just as restrictive. The only way you could write it is by imagining what the SQL it produced looks like. Or, if I've misunderstood his point, then it wouldn't work because of the same reason that things like CODASYL are obsolete. Some developers don't like SQL because they don't have a good intuition for how the relational model works. While SQL does have some cruft -- incidental complexity that's a legacy of the past -- any language that corrected SQL's shortcomings wouldn't be all that different to SQL, and so wouldn't help with this general problem. Quel wasn't successful because it was only somewhat better than SQL was at the time. This is a conversation that I had a few times when I worked for Heroku, with coworkers that weren't on the database team. They asked similar questions. It took me a while to piece this together. -- Peter Geoghegan
On Wed, 5 Jul 2017 at 14:36 Peter Geoghegan pg@bowt.ie wrote:
However, the OP seemed to be describing something that maps imperative
code to a declarative SQL query or something equivalent, which isn't
quite the same thing. The declarative nature of SQL feels restrictive
or at least unfamiliar to many programmers.
Yes, that is what I am describing.
SQL is great and I am fully on board with the idea. Everywhere I go, I promote the greatness of SQL, of the relational model, and of Postgres. I didn’t write in so much to challenge SQL or pitch navigational databases, as to ask about examples of “pseudo-imperative” languages.
Fortress is the most noteworthy of these; but anyone who’s seen Haskell’s do notation realizes there is some promise in the idea: the imperative structure makes some programs much clearer, even in a pure functional language.
IMV, what the OP describes wouldn't work well because it would
superficially *appear* to not be restrictive in the way that some
people dislike, but actually would be just as restrictive. The only
way you could write it is by imagining what the SQL it produced looks
like.
It’s not so much that SQL is restrictive, as that it is confusing in parts. It is the same with regards to Haskell without do notation — the chained lambdas boggle the mind. Another — very similar — idea is futures as an approach to getting around callbacks — they create the appearance of a linear sequence of execution, when some parts might be parallel; but this turns out to be a benefit overall. Yet another is using while read x in shell pipelines — an imperative structure, yet used to model stream processing.
But this is perhaps neither here nor there: it seems there are no such languages, no logic languages disguised as imperative languages. There are only a very few functional languages disguised as imperative languages. It’s an idea that has interested me for many a year — for the reasons that Peter cites — and not having seen any language wholly organized in this way, I thought I’d write to ask you all if you had seen any.
Kind Regards,
Jason
From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Jason Dusek
SQL is great and I am fully on board with the idea. Everywhere I go, I promote the greatness of SQL, of the relational model, and of Postgres. I didn’t write in so much to challenge SQL or pitch navigational databases, as to ask about examples of “pseudo-imperative” languages.
Brief comments.
1. LINQ has some of what you describe, and certainly provides some of the benefits you mention.
2. The Third Manifesto http://thethirdmanifesto.com specifies a pure relational language (a ‘better SQL’) in largely imperative terms, and there is an implementation https://reldb.org that is mainly imperative.
3. My own project http://www.andl.org/ is functional rather than imperative but still fulfils the same purpose. On SQLite and Postgres, it generates SQL.
No, SQL is not great. It’s actually full of holes at every level, from basic language design to serious breaches of the relational model to monstrous incompatibilities between implementations. However, the concept of SQL is great (which is why it’s been so successful), and existing implementations have done extraordinarily well, all things considered. As they say, the good enough is the enemy of the great. SQL is here to stay.
Regards
David M Bennett FACS
Andl - A New Database Language - andl.org
On 5 July 2017 at 01:22, Jason Dusek <jason.dusek@gmail.com> wrote: > Hi All, > > This more of a general interest than specifically Postgres question. Are > there any “semi-imperative” query languages that have been tried in the > past? I’m imagining a language where something like this: > > for employee in employees: > for department in department: > if employee.department == department.department and > department.name == "infosec": > yield employee.employee, employee.name, employee.location, > employee.favorite_drink > > would be planned and executed like this: > > SELECT employee.employee, employee.name, employee.location, > employee.favorite_drink > FROM employee JOIN department USING (department) > WHERE department.name == "infosec" > > The only language I can think of that is vaguely like this is Fortress, in > that it attempts to emulate pseudocode and Fortran very closely while being > fundamentally a dataflow language. It's probably of broader interest to consider some sort of "more relational" language that would, in effect, be "more declarative" as opposed to "more imperative" than SQL. (I'd not be keen on heading back to CODASYL!!!) The notable example of such would be the "Tutorial D" language attributable to Darwen and Date's "Third Manifesto" https://en.wikipedia.org/wiki/D_(data_language_specification) http://wiki.c2.com/?TutorialDee Unfortunately, the attempts to construct implementations of D have all pretty much remained at the "toy" point, experiments that few beyond the implementors seem to treat as realistic SQL successors. Another option, in principle, would be to consider QUEL, which was what Stonebraker used initially as the query languages for Ingres and Postgres. https://en.wikipedia.org/wiki/QUEL_query_languages None of these options seem to be dominantly better than SQL, and for something to supplant SQL, it would need to be a fair bit better. -- When confronted by a difficult problem, solve it by reducing it to the question, "How would the Lone Ranger handle this?"
On Mon, Jul 10, 2017 at 4:26 PM, Christopher Browne <cbbrowne@gmail.com> wrote: > On 5 July 2017 at 01:22, Jason Dusek <jason.dusek@gmail.com> wrote: >> Hi All, >> >> This more of a general interest than specifically Postgres question. Are >> there any “semi-imperative” query languages that have been tried in the >> past? I’m imagining a language where something like this: >> >> for employee in employees: >> for department in department: >> if employee.department == department.department and >> department.name == "infosec": >> yield employee.employee, employee.name, employee.location, >> employee.favorite_drink >> >> would be planned and executed like this: >> >> SELECT employee.employee, employee.name, employee.location, >> employee.favorite_drink >> FROM employee JOIN department USING (department) >> WHERE department.name == "infosec" >> >> The only language I can think of that is vaguely like this is Fortress, in >> that it attempts to emulate pseudocode and Fortran very closely while being >> fundamentally a dataflow language. > > It's probably of broader interest to consider some sort of "more relational" > language that would, in effect, be "more declarative" as opposed to > "more imperative" than SQL. (I'd not be keen on heading back to > CODASYL!!!) > > The notable example of such would be the "Tutorial D" language > attributable to Darwen and Date's "Third Manifesto" > > https://en.wikipedia.org/wiki/D_(data_language_specification) > http://wiki.c2.com/?TutorialDee > > Unfortunately, the attempts to construct implementations of D > have all pretty much remained at the "toy" point, experiments > that few beyond the implementors seem to treat as realistic > SQL successors. > > Another option, in principle, would be to consider QUEL, which > was what Stonebraker used initially as the query languages for > Ingres and Postgres. > > https://en.wikipedia.org/wiki/QUEL_query_languages > > None of these options seem to be dominantly better than SQL, > and for something to supplant SQL, it would need to be a > fair bit better. I'd like to see a SQL variant (maybe preprocessed) with an algebraic syntax. My biggest gripes with SQL are all the keywords (there are other spoken languages than English??) and the unnecessarily irregular syntax. merlin
From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Merlin Moncure > It's probably of broader interest to consider some sort of "more relational" > language that would, in effect, be "more declarative" as opposed to > "more imperative" than SQL. (I'd not be keen on heading back to > CODASYL!!!) > > The notable example of such would be the "Tutorial D" language > attributable to Darwen and Date's "Third Manifesto" > > https://en.wikipedia.org/wiki/D_(data_language_specification) > http://wiki.c2.com/?TutorialDee > > Unfortunately, the attempts to construct implementations of D have all > pretty much remained at the "toy" point, experiments that few beyond > the implementors seem to treat as realistic SQL successors. > > Another option, in principle, would be to consider QUEL, which was > what Stonebraker used initially as the query languages for Ingres and > Postgres. > > https://en.wikipedia.org/wiki/QUEL_query_languages > > None of these options seem to be dominantly better than SQL, and for > something to supplant SQL, it would need to be a fair bit better. I'd like to see a SQL variant (maybe preprocessed) with an algebraic syntax. My biggest gripes with SQL are all the keywords(there are other spoken languages than English??) and the unnecessarily irregular syntax. If you want a comprehensive list of what's wrong with SQL, it's easy enough to find. The list is long, but near the top arethe failure to adhere to the relational model, NULLs, and language design (irregular syntax, etc). But SQL is deeply embeddedand currently there are no competitors in its space. In the academic arena Datalog is preferred, and there are solidcommercial implementations. It's easy enough to pre-process your own syntax, and Andl effectively does that by generating SQL on Postgres and SQLite.But that doesn't provide enough benefits on its own, and displacing SQL from any of the places it's currently usedis not going to happen any time soon. Regards David M Bennett FACS Andl - A New Database Language - andl.org
They said it couldn't be done...
dandl <david@andl.org> schrieb am Di. 11. Juli 2017 um 06:58:
From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Merlin Moncure
> It's probably of broader interest to consider some sort of "more relational"
> language that would, in effect, be "more declarative" as opposed to
> "more imperative" than SQL. (I'd not be keen on heading back to
> CODASYL!!!)
>
> The notable example of such would be the "Tutorial D" language
> attributable to Darwen and Date's "Third Manifesto"
>
> https://en.wikipedia.org/wiki/D_(data_language_specification)
> http://wiki.c2.com/?TutorialDee
>
> Unfortunately, the attempts to construct implementations of D have all
> pretty much remained at the "toy" point, experiments that few beyond
> the implementors seem to treat as realistic SQL successors.
>
> Another option, in principle, would be to consider QUEL, which was
> what Stonebraker used initially as the query languages for Ingres and
> Postgres.
>
> https://en.wikipedia.org/wiki/QUEL_query_languages
>
> None of these options seem to be dominantly better than SQL, and for
> something to supplant SQL, it would need to be a fair bit better.
I'd like to see a SQL variant (maybe preprocessed) with an algebraic syntax. My biggest gripes with SQL are all the keywords (there are other spoken languages than English??) and the unnecessarily irregular syntax.
If you want a comprehensive list of what's wrong with SQL, it's easy enough to find. The list is long, but near the top are the failure to adhere to the relational model, NULLs, and language design (irregular syntax, etc). But SQL is deeply embedded and currently there are no competitors in its space. In the academic arena Datalog is preferred, and there are solid commercial implementations.
It's easy enough to pre-process your own syntax, and Andl effectively does that by generating SQL on Postgres and SQLite. But that doesn't provide enough benefits on its own, and displacing SQL from any of the places it's currently used is not going to happen any time soon.
Regards
David M Bennett FACS
Andl - A New Database Language - andl.org