a table is just a set of tuples.
this is like saying 32 bits are more fundamental to computer science than the abstract idea of an integer.
this is like saying 32 bits are more fundamental to computer science than the abstract idea of an integer.
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.
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.
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?
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...
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. :)