InnoDB

I have mentioned how to shrink InnoDB tables and the System Tablespace (ibdata1) in the past

• Mar 25, 2012 : Why does InnoDB store all databases in one file?
• Apr 01, 2012 : Is innodb_file_per_table advisable?
• Apr 15, 2012 : What happens when InnoDB hits its tablespace autoextend max?
• Apr 15, 2013 : MySQL database drop insanely slow
• Mar 31, 2014 : mysql directory grow to 246G after one query, which failed due to table is full

MyISAM

You could simply run for mydb.mytable

OPTIMIZE TABLE mydb.mytable;

which will shrunk a MyISAM table and recalculate the index statistics. To shrink all MyISAM tables, see my Jul 24, 2012 answer to MySQL: reducing ibdata file size for MyISAM tables

GIVE IT A TRY !!!

Trying to do FKs will just frustrate you - you don't actually need it.

If you handle versioning by using an InsertDateTime concept, then you're basically describing a Type2 dimension as used by many data warehouses. There is quite a lot of material out there about tuning systems that sit over the top of data warehouses, but from a T-SQL perspective, consider using APPLY. Like this:

SELECT ...
FROM ... AS t
CROSS APPLY (
    SELECT TOP (1) ...
    FROM ... AS rev
    WHERE rev.UID = t.UID
    AND rev.InsertDateTime < @revdatetime
    ORDER BY rev.InsertDateTime DESC) AS something
WHERE something.IsDeleted = 'N'

This kind of construct benefits from an index on (IsDeleted, UID, InsertDateTime DESC).

Alternatively, if you want to look at the whole table as at a particular time, use ROW_NUMBER() like:

WITH numbered AS
 (  SELECT *, ROW_NUMBER() OVER (PARTITION BY UID ORDER BY InsertDateTime DESC) AS rownum
    FROM ...
    WHERE InsertDateTime < @revDateTime
),
VersionAtTime AS
(   SELECT *
    FROM numbered
    WHERE rownum = 1
    AND IsDeleted = 'N'
)
SELECT ...
FROM VersionAtTime
....

(edited from original to move the IsDeleted predicates outside the sub-queries, removing all versions at that particular time)