> That's an interesting perspective. If you're dealing with genuine sets, and > you define your language in terms of second-order operations, then something > like LIMIT could be included. Would have to be, I guess.
Every aggregation function is at least second order: a function that applies a function to the set. So for MIN the function is 'less than', for SUM() the function is 'plus' and so on. In Andl aggregation functions are provided by fold(), which takes a function as an argument. > But that's not what SQL is, or what LIMIT is. Debatable. Many dialects of SQL provide aggregation, which is second order. > You were rather dismissive of my nth() function, but that approximates what > LIMIT does (approximation is all that's possible) with a first-order > operation. Sorry. Your nth() is a second order function that can be implemented in Andl or any language that supports generic aggregation. I would argue that it suffers from the same problem, depending on definition and implementation. The (single-pass) implementation would maintain a temporary table of rows that are 'minimum so far seen', to a maximum of N. It would be an implementers decision what to do with a row equal to one in that table once N has been reached: add it or ignore it? > BTW, I still think you're agreeing with me. I'm insisting on using the > "values of the tuple", implicitly restricted to first-order operations. > Cardinality, as you say, as a second order *function*, hardly a "value". But > at least I understand your argument now. > > > To that you can successively add negation, recursion, higher order > > functions and fixpoint/while. Each of those allows operations that > > others do not, but there is disagreement about which should be > > considered 'relational'. > > OK, I see. It's fitting that the debate is about the definition of the set > of relational operators. > > I'm conservative in that regard. I'm wary of the complexity that higher- > order operations bring to the language. Each higher level brings (I suspect) > more complexity than the prior, while solving fewer new problems. True, but for SQL at least the complexity arises from faults in the language. The aim of Andl is to do more in the database language layer and less in the application, with a language that makes higher order operations much easier. For that I think you really need aggregation functions, ordered functions and while (recursion). > I think recursion is a good extension, and a good example. It permits the > expression of hierarchies. It's indispensable ... for maybe 1% of queries. When you need it you really need it. The main driver is graphs that have been expressed as relations with self-joins, but it's also needed to implement an algorithm that is intrinsically an iterated computation eg Mandelbrot, Sudoku solver. > I guess you could convince me it makes SQL Turing Complete, but that's a very > dense thicket. Recursive structures are useful. If they could be > manipulated without making the language Turing Compiete, I'd consider that a > plus. [A side-note: there are two models of computation: the other is the lambda calculus; the two are of equivalent power but quite different in construction. Datalog with negation has the same computational power, deals better with some kinds of data but not necessarily relations.] Many writers say the same: a query language should use the lowest language level possible, but for Andl to reach its goals it must make that power available and accessible for when needed. > > Thank you for the reference -- I didn't have that one. I'm familiar > > with the material. > > You're welcome, and it shows. > > I think we've managed to hash out some agreement: > > 1. Second order functions are "relational", or can be, depending on one's > definition. We have support for them already in SQL. > > 2. Limit, as currently implemented, lies outside the theory because it > doesn't operate on sets. I'll put that one on hold pending a suitable reference or detailed mathematical treatment. Regards David M Bennett FACS Andl - A New Database Language - andl.org
