Queries Refactored

6/14/2006 8:05:45 AM

Queries Refactored

Earlier, I pointed to Erik Meijers paper on XLinq: XML Programming Refactored; it was an article that I have been wanting to blog about.

Erik distinguishes between relational operations (projection, filtering, grouping, sorting and aggregation) and domain-specific operations. SQL doesn’t have many domain-specific operations; however, XQuery contains quite a number, such as structure axes and attributes. In distinguishing these two types of operations on queries, Erik was able to generalize relational queries across all data types. He gets at the essence of LINQ and how it can become possible to perform queries on different data types. SQL is not just for database tables. Actually tables, although a simple concept, aren’t even the best data types to highlight the expressiveness of relational operations because tables can’t be composed, which is why you don’t see many nested SQL queries. In contrast, composed queries are quite common in XQuery, which makes it somewhat of a better SQL than SQL in this regard.

I alluded to a related article Comprehensions, a Query Notation for DBPLs last year. This article identifies two additional advantages to incorporating relational operations to programming languages—support for computation and for recursion. It also points out that relational operations are possible on any data type which is ringad (ie, which has four functions that satisfy certain algebraic laws; basically a monad and a zero and a combine function.) Examples of ringads from the paper include sets, relations, bags, lists, trees, graphs and finite maps. Sets and lists are pretty much covered by IEnumerable extension methods, but I get the sense that full generality of LINQ has yet to be explored.

One idea of mine comes from this Constraint Logic Programming example in Chris Sells blog. Here’s the original example.

people_at_the_meal(Grandparents, Parents, Children) :-
  Grandparents * 3 + Parents * 2 + Children * 0.5 = 20,
  Grandparents + Parents + Children = 20. 

One could extend LINQ to support solving the above CLP program by writing the following

from grandparents in Domain<int>
from parents in Domain<int>
from children in Domain<int>
where grandparent >= 0 && parents >= 0 && children >= 0
where grandparents * 3 + parents * 2 + children * .5 = 20
where grandparent + parents + children = 20
select new { grandparents, parents, children }

Here we are working with “infinite sets.”   This examples would have to make use of expression trees to be able to solve the problem.






Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media