Usually you would use some form of unique identifier or key - in an airline case an FF number or a passport no. should do the trick alongside something like DOB for extra safety.

As an aside, this is something I am involved with in a different industry. In the UK this is pretty challenging as we don't have an identity card number that we commonly capture. Across our sprawling estate of systems you can "exist" many times without us being sure we are looking at the same person. We are undertaking a huge exercise (including eyeballing 1000s of records in the worst cases) to merge these records.

Luckily I've moved to Asia where we capture a unique ID number in all the markets we operate in, so a far more simple proposition