Gregory Maxwell:
For every wikidata table there are actually two tables in the database, a item table and a revision table. In item, the key will be constrained to be unique and non-null, in the revision table it will be just non-null.
Generally just follow mediawiki for the fields, but rather than text have your data fields.
The scenario of having a basically flat table that is versioned is a simple one. It gets tricky when you have 20 tables which are in complex relations with each other, and you want to revert or view a particular revision. Note that even our current MediaWiki is broken in this respect - when you view an old version of a page, you see it with the latest versions of the templates it uses, which can lead to very funny results.
Example: In Ultimate Wiktionary, you have an expression ("dog") which can be associated with multiple words of different types and genders, which can be associated with multiple defined meanings (each of which can be associated with a meaning text), synonyms and translations. This is a powerful concept, because it allows you to "magically" find all translations and synonyms when you know what meaning you refer to for a particular expression. The possible applications are endless.
The problem with relations of that complexity is that, if you don't want to balloon your tables, (I think) you need a lot of revision pointers between them. I'm going to try to model this with a simpler example. If you want to model something, feel free to help - it is sometimes good if multiple heads work on the same problem and come up with different solutions.
Too many people see Wikidata as being about infoboxes. I saw it that way when I first came up with the idea, but it's really more interesting to see it as a wiki engine for arbitrary database-driven applications. The goal is, to steal a Perl proverb, to make simple things simple and complex things possible. For apps like UW, a lot of custom code will have to be written, but the basic table structures can be the same as for any other WD application.
Best,
Erik