Lambda the Ultimate

Haskell DB comes to mind. Static programming language checks all the way.

But if one accepts SQL as a given [...]

...which is something which I most certainly do not accept. This is possibly because I work with Z39.50 for a living.

This is not true - there are/have been many languages that included sophisticated handling of persistent data.

At one extreme there were languages developed during research into orthogonal persistance that focussed on lessening or, in some cases, completely removing the distinction between transient (in-memory) and persistent (disk) data.

There have also been a number of languages that elevated relational data access (and other more expressive persistent data models) into the language itself.

PL/SQL et al obviously have db integration features, as does COBOL (although that's obviously not 'modern').

The very few languages (C/C++/Java/C#/VB) that are in significant commercial use are not really representative of language designers efforts - many more languages are designed than used, so maybe the question shouldn't be about why language designers don't include such features (they do), but rather whether interesting language features preclude widespread adoption, especially with the democratization of programming. My gut feel is that adding features as Joel suggests involves considerably more changes ala typing, transactions, exception handling etc, than simply elevating APIs to the status of statements, and the resulting language starts to experience combinatorial explosion of semantic weight (and problems).

round here, foxpro is fairly popular i believe. i think that has significant database integration (but may be wrong - never used it).

The relational model is challenging to deal with in a way that makes sense in modern programming languages. It works pretty well when you are trying to select data, but trying to relate those selects to updates or other operations is difficult. Typically all we have are bare names, which don't necessarily reflect where the data comes from or how it would be changed, or how it is related to other parts of the select results. Other operations like left joins -- and really even joins -- aren't part of the basic metaphors of most languages, which expect things in terms of objects and simple data structures.

Not that it isn't a worthy goal to make RDBMS access more natural, but I think the problems are more challenging than just syntactic. *And* I think the relational model isn't natural for most programming tasks or most programmers -- a language based around set theory and the relational calculous isn't going to get very far, because people are willing to use that for database access (e.g., SQL, PL/SQL, etc), but they aren't going to use it for general programming tasks.

Ah, but that's where having the "lazily evaluated expressions that can be introspected" is so useful - you can use that introspection to know something about the results as well as to generate the query in the first place. So, no, if you do it right you have much more than bare names.

I really need to write more about the stuff I'm doing in this area, but for now see: http://www.cincomsmalltalk.com/userblogs/avi/blogView?searchCategory=databases

Abstract: We give a polymorphic account of the relational algebra. We introduce a formalism of ``type formulas'' specifically tuned for relational algebra expressions, and present an algorithm that computes the ``principal'' type for a given expression. The principal type of an expression is a formula that specifies, in a clear and concise manner, all assignments of types (sets of attributes) to relation names, under which a given relational algebra expression is well-typed, as well as the output type that expression will have under each of these assignments. Topics discussed include complexity and polymorphic expressive power.

Quote: In this paper, we do type inference for the relational algebra. The relational algebra is very different from the programming languages usually considered in type inference ... The set-based nature of relation types, and the particulars of the standard relational algebra operators when viewed polymorphically, present new challenges. As a consequence, our formalism of type formulas is drastically different from the formalisms used in the theory of programming languages.

So are there any languages in which Z39.50 has a better integration than just being passed around as strings?

Haskell (amongst others) contains powerful techniques for processing lists.

If the compiler could utilise indices when processing list comprehensions we wouldn't need SQL, we would have a native (and natural) means for querying databases built in to the language.

Of course, that then leads to the thorny problem of multi-user database transactions in a language that eschews state.

But it's a start...

BTW, Erlang has an application called "Mnemosyne" which is an optimizing compiler from list comprehensions to Mnesia database calls.

I haven't used it much. When the DB is all in ram and in your address space you can just make as many little calls as you like and write your queries as regular functions - no intrinsic need for a DSL.

Haskell (amongst others) contains powerful techniques for processing lists.

Being pedantic again, techniques for processing arbitrary algebraic datatypes, including lists and trees. We may not be able to use list comprehensions with any algebraic datatype but we can make their usage as simple with other techniques (e.g. combinators).

Of course, that then leads to the thorny problem of multi-user database transactions in a language that eschews state.

Hmmm, we can embed these issues in monads, both database access (client side using IO) and transaction processing (server side using State monad to build the transaction).

A related discussion

OK, my time to disagree. The ordering of the records is a property of the indices used by the table - the data itself is essentially unstructured. Each index could be stored in a different fashion, (including of course tree structures), but it should not be limited to such a form.

As far as I am aware there is no reason why List Comprehensions couldn't be made to work with a generic DatabaseIndex Typeclass.

A State monad would be appropriate for the database server because to ensure database integrity all database commits ultimately have to be single threaded.

On the client machine however, my gut feeling is that it isn't so simple. I don't think it makes as much sense to force a single threaded approach when connecting to multiple database servers on multiple machines each of which probably has hundreds/thousands of users. Multi-database commits can be a thorny issue at the best of times, and I don't think this is an issue that has been satisfactorily addressed yet.

Daniel: ...a database table is a tree of records

You may want to state what kind of data model you are each referring to. I had assumed it was the relational data model but in that case you're both wrong; the value of a relation is defined as a set (unordered!) of tuples. I don't have reference material handy so I can't point to anything definitive, though the wikipedia has a pretty good entry on it.

I don't think it makes as much sense to force a single threaded approach when connecting to multiple database servers on multiple machines each of which probably has hundreds/thousands of users.

I would hope that the DBMS would be handling these details (and provide a sufficient interface, of course.) Clients of the database should be as isolated from such physical concerns as possible, and having the client applications responsible in any way for data integrity would be a disaster. Is there anything language/application would need beyond ways to indicate the start and end of a transaction, and a way to know whether it was a success or failure?

Isn't that what I was saying? That data is completely separate from its sequencing and access via indices?

As for the DBMS stuff, remember that this whole thread is about integrating database access and manipulation into the language, hence my "gut" feeling that it isn't that simple on the client.

Relational databases have a mathematically model that is the same for all programming languages. In contrast each OOP database or OOP language implementation model is different; it is impossible to design a single OOP interface to relational databases (other than a trivial re-implementation of the relational model itself) that would be optimal for all OOP models. Each OOP-relational interface must be hand-rolled because of this deficiency.

This is the fatal and largely unrealized flaw in OOP that will eventually lead to its abandonment. OOP recreates (for languages) the database debacle that culminated in CODASYL network-style databases decades ago and that was cleaned up by the ensuing arrival and overwhelming acceptance of relational databases. However the enlightenment that has occurred for databases has not yet arrived for programming languages, and it will take another decade for language developers to realize they took a wrong turn when they went down the OOP path.

I have to hold up my hand and admit that my paid work is in a 4GL RDBMS, so I think I may have some insights into what works in the "Real World".

I don't use SQL a great deal because it's a bad fit for a lot of database work. Many "set" operations are actually operating on single records. Also, SQL lacks basic concepts like a "screenful" of records. A better approach in these circumstances is to define a query across the tables you need whilst applying constraints to the records fetched, and then manipulating them in turn as appropriate. Sounds a lot like a list comprehension, doesn't it?

Database transactions have to be "atomic" as far as possible, but at the same time wholesale database locking during user access is unacceptable in massive multi-user systems. This means that you have to be aware that the data you are working with may have mutated outside of your control. With respect to Haskell, you then have some of the problems inherent with state in a language that has not been designed with these in mind.

My own inclinations are that many of these can be solved by adding proper parallel semantics to Haskell, and indeed these will prove useful in any event upon future multi-core multi-CPU machines. Languages like Oz have thought and are thinking about these "practical" aspects, I just wish there was more interest in the Haskell community. The "Real World" can be messy, and doesn't always pare down to a clean mathematical model.

Boy am I going to get flamed now...

He does make some use of the two extra equational laws that distinguish sets from lists, so I imagine that you'd want a programming language to offer some sort of specification/checking for legal equational transformations. That's a pretty generic and non-ad-hoc feature, though. Done right, I bet a compiler could optimize the database queries it sends to the database engine as part of its ordinary optimization passes. :)

Safe Query Objects: Statically-Typed Objects as Remotely-Executable Queries, with Siddhartha Rai. Submitted to OOPSLA 2004.

i'm pretty sure i read somewhere recently the claim that k manages the largest database(s?) in existence (i've been reading around a bit on concatenative languages). that claim, incidentally, is probably untrue, since i doubt it's used for babar (in astronomy we're copying from high energy physics in anticipation of the next generation of survey telescopes, which will generate huge amounts of data - some may even process the images in realtime and store only measured parameters, discarding the raw data).

As for comments in this forum:

The relational model defines a table as a set of tuples. Most implementations use various forms of binary trees for indexes into the list of tuples, but since there can be multiple indexes it seems strage to say that a "table is a tree of records". Often the indexes contain a subset of the data in the record: sometimes a query can be executed by only examining the index, but sometimes multiple indexes and the actual tuples are accessed.

I tend to think of the relational model as "assembly language of data". One key similarity is that data does not have an inherent interpretation, but is only interpreted by they operations applied to it. For example, a word of memory is interpretated as an integer or a float by an assembly instruction, not by its inherent type; similarly, values in a table are interpreted as keys/foreign keys during a join operation, but the semantics of the relationship is not stored in the database -- it is only in the query. As a result, I prefer to use the Entity-Relationship (ER) Model, since it assigns more meaning to the data in the database.

In either case, I don't think that typing problems are the central issue in impedance mismatch. As many have pointed out, most languages can represent lists of tuples, and NULL data values are not really a fundamental problem for programming languages. In addition, the ER model maps very naturally to object-oriented languages.

As for connecting data from the database with its source, this is an important issue. But object-oriented languages make this easy -- just wrap the data in an object that keeps track of its source (this is done in most OO/DB interfaces, like ADO). I suppose you could use "lazily evaluated expressions that can be introspected" to do the same, but its not the only way.

As for the idea that "memory is so cheap that we can just load everything and use normal iteration" -- I don't buy it:

• Iterating through millions of records to find the few that are needed is not efficient; indexes can still help a lot.
• Straightforward queries often involve nested iteration (think a million squared); query optimization with indexes can reorder these operations to be very efficient.
• Transaction models require isolation: as a result every object a transaction touches must be added into the transactions working set -- a linear scan of all objects touches everything.

So, what is the fundamental problem? The desire for a uniform (object-oriented) semantic model while still supporting the efficiency of query optimization. This is why none of the object-relational/persistent object systems have been fully successful: they are conceptual clean but don't provide a way to leverage the power of database engines for query optimization. The alternative, ODBC and its descendants, let you use the power of the database but introduce a complete semantic disconnect between the programming language and the query language. Even the advanced "query objects" in systems like Hibernate and JDO are really no better than SQL strings, since they are still constructed and verified at runtime.

Our paper is a first step toward a new approach to solving this problem. If anyone has comments, I'd love to hear about them.

Buffering: I'm assuming that the collections returned by the Query Objects are lazy? That is, is the collection returned immediately upon receipt of the first tuple, acting like a stream rather than a fixed list. Or must I await for the full collection to be completed before the method releases the results. Something along the lines of iterator seems to come to mind.

Joining: What is it about the Join operation that causes grief? Harking back to RPG days, we would define a join in a similar DDS format, and then that join could be used in the same manner as a native table. That is, why can't Query Objects be Views, Procedures, or Functions, rather than just a raw table definition (indeed, the table may be little more than a view from the database side).

Overall, interesting work. Do you have the code for the example posted on the web? (might give a better feel for how the pieces fit together).

As for the code, it is not on a web site yet. It will be eventually, but it is not there yet.

Now, having some nice theoretical model that fits well with the rest of the language (like in Haskell DB) seems appealing. BUT it is far from being simple for the avarage programmer (maybe not avarage Haskell programmer, but surely avarage Java or C# programmer :-). Simply SQL is something known, and combinators, you know...

What you suggest is a good idea, and would definitely reduce the number of bugs. But unfortunately, you can't rely on this to eliminate any dynamic checks, though, because the database schema can change and invalidate the analysis the macro did. :( I know Oracle keeps track of which tables stored procedures reference, and invalidates any procedures that do things that don't make sense any more. Unless you can hook your linker into the database the same way, you have to be conservative.

The same argument holds for shared libraries in your system, you cannot change them without interferring with program which use them, no matter how secure and pure is language it was wrote in.

Of course one could think about implementing relational model or SQL validator to check SQL statements... BUT, database is such a validator itself... No mentioning all the problems such as "how to retrieve type of stored procedure", "how to be compatible with that, that and that database system"...

Macro feature of Nemerle just gives an easy way of implementing some validator of SQL statements. You can do this in many ways, actually "send to database" approach took me 267 lines of code and it seems very powerful even in its prototype state. :)

I've not heard that joins are a problem. In fact I've heard little evidence of them being brought into an OO language at all.

Maybe there are citations of this in the paper? I've not read it yet.

Joins represent bi-directional links...

Hmm. There's a deeper discussion here.

Hmm. There's a deeper discussion here.

Yes, enlighten me. What is it exactly that joins are supposed to do or what problems should they solve in an OO language?

And I am sorry Ehud. I completely agree with you about languages (concerning C Omega), vaporware (for we only have a few small mods to the JS internals), and languages starting with a C (thankfully though, the language is named Color =).

I personally am not a good SQL programmer, and we though about how mainly languages one has to know when following an MVC website design strategy (3, maybe 4 if you use and count XML as a different language than HTML). Our fix starts with access databases using a URI.

x = <mysql://usr:passwd@domain.com/>

And being that I view the '.' operator much like a tree accesor, we could access a field in a table like so.

x.database.table[0].field

The array of course references the row of the table. My only problem with this is the mental mapping between rows starting at one and the historical precedence of arrays starting at 0.

Thankfully I was on the same page with Joel, and thought 'if' and 'where' acting very much alike. Now mind you this does not fix the problem that is addressed in the title of this posting, but I personally believe it is a step in the right direction.

A way of bridging the gap is of course with persistent languages. With the current advent of big RAMs (and swap space anyway), the variant known as "prevalent" becomes feasible. Basically all data are normal objects of the language held in main memory as usual but a means exist to make them all survive program termination, and restore to the last state upon restarting. The Prevayler system does this for Java. My Mneson database system (Ada + DSLs) is similar in that all data is in main memory except non-tiny strings.

Someone mentioned Foxpro. Foxpro is Clipper with Windows. Clipper is one of the once called xBASE systems, which included dBASE, and is essentially SQL.

RE: Using a language with macro capabilities like Scheme or Nemerle you can just pass the SQL queries as text and have macro send them to database for validation. This could provide compile-type checking if the text is sent to the database at compile time, when the macro is expanded. Requiring the compile step of a program depend upon having a running instance of the database is not inconeivable, but it certainly makes configuration management harder. Also, some queries are composed or written at runtime (see my paper mentioned above for a typical example); I am not sure how macros would handle this case.

RE: Yes, enlighten me. What is it exactly that joins are supposed to do or what problems should they solve in an OO language? I don't think that joins should go into an object-oriented language. I was merely pointing out that joins are used in the same way that inter-object pointers (links) are used in OO. In a database the relationship between two rows is bi-directional: joining an emplyoee table to a department table can be used to find 1) the department of an employee, or 2) the employees in a department. Changing the department of an employee automatically changes the set of emplyees in the old and new departments. This kind of referential consistency is automatic due to the normalized data reprentation.

RE: persistent languages. I have two comments: SQL is in effect a domain-specific language for describing search operations that can be very efficiently optimized based on indexes, etc. Most persistent object systems don't provide equivalent optimizations -- you could ague that its all in memory so it doesn't matter, but I am not sure I believe it. Second, it is good to have redundant live servers for availability and scalability. I don't see how memory-mapped persistent object systems can be distributed/replicated effectively.

RE: Access to DB via URL. This has been done many times before. SQL server includes something like this as a standard option. I don't see how it solves anything. It is not as expressive as real SQL, or admit the same kinds of optimizations in real SQL. You might as well just map your database to a bunch of Javascript arrays with data in them, and be done. For some this might be a solution to impedance mismatch, but not for me.