[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. :)