Таблица отношений пользователей. Как правильно?
Правильная таблица отношений:
Отмечу на всякий случай никаких id(самих записей) не должно быть! все выборки по ключам приведенным ниже
user_id|friend_id|relation_id|date(timestamp)
222|444|1|ts
444|222|2(не просто дружит а например встречается, женат, и т.п. для каждого случая свой уникальный id)|ts
первичный ключ составной (user_id,relation_id)
дополнительный ключ (friend_id, relation_id)
если кидают заявку создается 1 запись user_id>friend_id>0
проверка на поступившие заявки friend_id(current_user_id) | relation_id = 0
подтверждение: (должна быть транзакция!) то есть если отвалится один из запросов нужно вернуть все как было.
на MyISAM ручками(средствами PHP проверяем). На innodb делаем транзакцию средствами БД.
вписываем строчку с подтверждением курент_юзер > фриенд_ид > relid - 1 и обновляем основную заявку до единицы. Повторюсь если одна из команд не пройдет надо все откатить. 
если отказ то удаляем основную заявку из базы.
по поводу дополнительных отношений:
кинуть заявку можно только пользователю у которого взаимно стоит 1 и проверка собственно на заявки
friend_id(current_user_id) | relation_id >(больше) 1.
Остальной алгоритм тот же. одновременно у 1 пользователя может быть только одна запись с отношением больше 1 (желательно, это как индикатор именно личного отношения, для группировки друзей лучше все же завести отдельное поле) 
Описание с реальной базы данных на 30 миллионов пользователей.
А по другому вменяемо никак и не сделать.