[silentbicycle]

Right. If you strip away terminology and other baggage (some of which is specific to MySQL, Oracle, etc. anyway) and look at just the relational model, it's actually pretty simple.

You have a relation (often called a "table"), which is a set of tuples (often called "rows"). Some of the fields ("columns") in a given tuple can be a key for that tuple, and some of them can be keys referencing other relations ("foreign keys"). The result of a query (such as getting all rows with a given value in a given column, joining one row to zero or more rows in another table via a foreign key, or the intersection of two relations) is another relation, and can be queried the same way.

It's tuples and set theory.

There's implementation details (and the implementation details for a high performance RDBMS are not trivial, don't get me wrong), indexing, transactions, constraints, etc. on top of that, but the core relational model itself is not very complicated.

[mjrusso]

In your first CS courses, you learn how to build linked lists, sets, etc., and implement your very first algorithms using these data structures.

Relational databases come later, and many of the important concepts (set theory, tuples, etc.) build on knowledge learned by studying and implementing and using these initial data structures. It is in this way that I believe lists, sets, etc. are more fundamental than relational database tables, columns, and rows.

[silentbicycle]

Some people learn set theory before data structures and algorithms. People focusing on math rather than computer science, for example. As long as we're speculating about hypothetical aliens, I wouldn't reject that possibility.

Arrays, linked lists, binary trees and mergesort could be more fundamental than the relational model, but the relational model in turn may be simpler than (say) red-black trees, BSPs, skiplists (depending on how the aliens view randomness), or OOP.

It's an interesting thought-experiment, though - if CS were being re-invented from the ground up, which things would be more fundamental and likely to be discovered first, especially with significantly different hardware?

[antirez]

Well in a limited fashion this experiment could be actually be done. I'm not sure how this would be modeled, but I guess giving smart young guys that don't know nothing about programming a set of "tools" in a simulation that can be used to create the building blocks of many different data structures.

Then provide problems, and look at what they do and invent in order to solve such problems.

Will be very hard to do this in an unbiased fashion actually...

[silentbicycle]

Absolutely. Hence, thought experiment and aliens.

Having programmers explore in a (to them) really weird language (like Prolog or Haskell) and seeing what they come up with might be a good approximation, though.

I may never have thought of difference lists, but then Prolog made them seem obvious. :)