I'm asking this because I'm trying to figure out the "essential" building blocks of a declarative language by stripping out and unifying features (not the mathematical blocks but the user-facing blocks) and I've wandered into territory where I've stripped away the value/type distinction and am considering what you can do with sets of labels and of discrete maps, which seem to overlap with relations. For example, the set {(father -> "bob"), (child -> "jim")} can be interpreted as an ordinary record/struct, but could also be interpreted as a labelled tuple belonging to a relation, and a set of such sets becomes the relation. Relational operators could then act on it.

If you haven't already, you should take a look at "Data types a la carte" (http://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesALaCarte.pdf) and subsequent literature.

Thanks for the references. I'm not sure how relevant they are though, since they are attempts to bolt new capabilities onto existing languages through "smart" encodings. I'm looking for features that could be built into a language and how well they would serve as building blocks.

I realize this is rather general and vague, but, IME trying to unify things as much as possible can be fun, and lead to interesting languages, but also lead to languages that are very hard to implement efficiently, and force you into tough design choices with no clear right answer. As an apropos example, one way to unify functional & relational(/logic) programming would be to treat functions as a special case of relations. But, while we know how to implement higher order functions, implementing higher-order relations is really, really difficult in general. So my line of work with Datafun, while it could be described as a "functional relational language", definitely isn't taking this approach: even though conceptually functions are a special-case of relations, we keep them separate because it avoids a bunch of hard problems. On the other hand, there is a project - Bill Wadge's "Higher-order extensional Prolog" - that is trying to tackle full-on higher-order relational programming. I don't know much about it, but it'll be damn cool if it works! So, I can't tell you whether trying to blur the distinction between data structures & relational algebra is a hot mess or a good idea, but I can tell you that it might be difficult 🙂.

Thanks for the perspective @rntz. Perhaps it's too difficult a problem to tackle. I wish prototyping these things were easier! There seems to be too many prereqs to just try everything possible (as you point out the numerous research areas behind everything). Perhaps that's a good motivator for why the web needs to be a better enabler of conceptual communication between people.