After database connection:
$sqlquery=SELECT * FROM yourTable WHERE name='$enteredName' AND lastname='$enteredLastname' AND
telephone='$enteredTelephone'
$res=mysql_query($sqlquery,$db);
$control=mysql_num_rows($res);
if($control)
{
echo "<script>window.alert('The record already exist!')</script>";
exit;
}
If not control then insert the new record...
This is only an example, naturally...