ExoticnessДумаю вы правы, но никто кроме самого юзера не имеет доступа к другим категориям. Я попробую сделать так как задумал изначально - буду вставлять в поле айдишник юзеров, но всё же по прежнему открыт для предложений.
Каким образом лучше именовать первичный ключ? Не будет ли ненормально, если везде будет Id?


это нормально везде id - так по умолчанию работает куча фреймворков.... но твоя творческая душа верно вучствует - это тупо. (пить нынче тоже нормально, а не пить совсем не нормально :) )

если таблица для понятия cat - то её имя cats первичный ключ catId (idcat можно так, но люди говорят что мы читаем слева направо, поэтому надо левее болле общее, а правее более конкретное)
в другой таблице не как лохи называть ссылку на категорию parentId - особенно исходя из того что тут нету наследования, и следовательно нету родителей
а назвать таблице tasks полле ссылку catId - очень хорошо если у тебя получиться что где бы в базе не присутсвовало catId сразу можно зуб давать что это везде одно и тоже значение. - тоесть несмотря на код создания таблиц ты сразу знал, если в двух таблицах есть поля catId то это точно можно делать джойин по этому полю.

для него индекс создать назвав его FK_tasks_catId - внешний ключ таблицы tasks на значение catId.

другие индексы
AK_table_field - альтернативный ключ - поле тоже уникальное, и может быть использованно для идентификации записи на равне с первичным ключом
EK_table_field - дополнительный ключ - просто индекс по полю...
или
EK_table_field1_field2_field3 для составного индекса... чтобы читая это сразу понимать что там.

а для твоей задачи, и вообще, помагает мыслить первичными ключами....

название категории входит в первичный ключ? - нет,
являеться альтернативным ключом?(ты хочешь чтобы по названию категории можно было сразу сказать о чом речь? нет)
значит его не расматриваем... есть catId
есть userId
у тебя категория любая одного или нескольких юзеров? одного, значит рядом с catId должно быть userId(ссылка) на юзера

а все остальные поля это обвеска этих ключевых.