My grandmother was interested in genealogy and had a bunch of genealogical books about the family. They were passed down to my mother and I got them when she passed on. So I got a genealogy program and started looking online. It was pretty easy to find connections, since there is so much information out there. However, I soon formed the opinion that:
Genealogy records back to around 1500 are pretty good, but of course the earlier ones are spotty since records were kept in parish churches and some were destroyed by fire or war.
From 1500 back to 1000, the records are concentrated on royalty or well-connected individuals.
From 1000 back, it's pretty much royalty only with a few exceptions.
At some point, genealogy became important to your status. At that point people started making up well-connected genealogies to imply they were from royal stock at some point in the chain. So before 1000, I would guess that all bets are off as far as documentation.
*******************************
There is a "mathematical theorem" going around that purports to prove that everyone (of European descent) is descended from Charlemagne (748-814). It is basically statistical in nature, so it doesn't necessarily prove anything, but the numbers are very interesting. It goes something like this:
P = a particular person from year Y
G = number of generations from you to year Y
N = male population of Europe in year Y
X = probability that a particular ancestor at generation G is not P
Z = probability that none of your ancestors at generation G is P
The number of ancestors in year Y is 2**G. Half are male, or 2**(G-1).
Given a particular male ancestor from generation G, the probability that he was not P is X=[1-(1/N)]. Therefore, the probability that all of your ancestors from year Y are not P is Z=X**[2**(G-1)].
In this example, using Charlemagne, we estimate Y=800, G=40, and N=15,000,000. The probability that P is not Charlemagne works out to be a very small number, on the order of 10**-15900. The same argument presumably holds for any other male at that time, such as Roland or Einhard, knights in the service of Charlemagne (maybe even Sulieman?).
At what year does the probability of not being related to someone from that year become reasonable?
Estimating 3.33 generations/century and using the following estimates of the population of europe (interpolated from data of Josiah C. Russell, listed at
http://www.fordham.edu/halsall/source/pop-in-eur.html)
Y N G-1 log(Z)
(millions)
800 15 39 -15900
900 18 36 -1660
1000 20 32 -93
1100 25 29 -9.3
1200 30 26 -.97
1300 35 22 -.05
Up to about 1100, the probability is negligible (less then 0.000000005).
Around 1200, the probability is about 10% and around 1300 the probability is almost 90%. Of course, at some point, statistical arguments don't apply, so the later years are highly conjectural. The real question is: at what point does the statistical approach break down?
Assuming that the approach is valid until 1100, consider that you are likely to be related to some interesting historical figures:
King Duncan (~1010-1040) (a contemporary of MacBeth, in fact a cousin)
William the [Conqueror/Bastard, depending on who you talk to], ordered the gathering of data for the Domesday Book. (And of course Harold Godwinson (who lost the battle in 1066))
Urraca, Queen of Aragon became ruler of Leon-Castile in 1094 when her husband died. She remarried in 1098 and then spent 13 years at war with her second husband, Alfonso the Battler, to protect the inheritance rights of her son by her first marriage. She led her own armies into battle.
http://www.lothene.demon.co.uk/others/women11.html) (sorry, that link seems to have disappeared since this analysis was written in the '90s)
And Aethelred the Unready, whom we have to thank for the institution of a regular monetary and taxation system (in order to pay the Danegeld). (PS: Unready is a corruption of old english for "having bad counsellors")
Going to earlier times, we can assume that as long as civilizations were in contact there must have been cross marriages, particularly for diplomatic or political reasons, so that we can extend the argument beyond Europe to the known world, and maybe even beyond.