Есть таблица с двумя полями - id и connectedids. Каждая запись в этой таблице - вершина графа.
Поле  id определяет порядковый номер вершины графа, а connectedids содержит целые числа разделенные запятыми, определяющие idы других вершин, соединенные с даной вершиной.

Например:
1 - 2,4
2 - 1,3,4
3 - 2,4
4 - 3,1,2

Как проверить и исправить ошибки в записи этого графа?
Т.е. если первая вершина соеденена с 4й, то и 4я должна быть соеденена с первой. Если в connectedids четвертой нет первой, то такую запись надо добавить.

Как удалить вершину графа?
Вместе с удалением всей записи вершины, удалить из connectedids других вершин все ссылки на удаленную

Никак не могу придумать оптимального алгоритма с минимальным количеством запросов в базу.   Помогите.   

У тебя изначально информация не верно хранится. Надо хранить отдельно родителей, отдельно предков.
Плюс, задача проверки - какая? Графы разгные бывают и замкнутые в том числе.
И вообще, задача на практике - какая?

Что-то не поняла идею. 

Я бы предложила хранить отдельно врешины, отдельно ребра. Поскольку по условию задачи граф не ориентированный, то каждое ребро достаточно хранить один раз. Если уже записали (1,4), не нужно писать (4,1). Тогда и такая проверка на ошибки записи не нужна. А ответственность за целостность данных (удаление ребер, при удалении инцидентных им вершин) можно возложить на саму базу, если использовать foreign keys, указав ON DELETE CASCADE 

Идея - дерево.
Тут главное, чтобы автор пояснил свою задачу в абстрактном изъяснении... А иначе будем гадать что и как. Дерево тож не везде сгодится.

Mal Hack, идея не понятна по другому, допустим есть:

Тут у элемент 1 - корень дерева, у элемента 2 - родитель 1, а у элементов 3 и 4 - родитель 2.
Те хранить отдельно родителей и детей не получится - задача поставлена не верно.
Причем условием является хранение графа, а не дерева, как его частного случая.

Я сказал: "хранить родителей и детей отдельно для КАЖДОЙ вершины или единицы графа". Это совершенно другой смысл.

А, в смысле, надо было читать, отдельно родителей, отдельно ДЕТЕЙ. Так ясно.  Дерево хорошо тем, что для него есть подробно разработанные схемы обхода. Но, как Вы справедливо заметили, не подойдет для графа с циклами. В общем-то, для неориентированного графа понятия родителей и детей - несколько искуственное, только для обхода и имеет смысл. Но Вы правы, лучше подождать разъяснения автора темы о характере задачи, тогда можно будет отбирать более рациональный вариант

Mal Hack, 
Это не рационально - допустим три связанные вершины - в худшем случае получится 3 таблицы - в одной все предки 1 вершины, во второй все предки второй и тд
В лучшем случае получится таблица предков и таблица родителей с дублированной информацией.

Вот есть такая идея:
http://forums.lavag.org/index.php?showtopic=3250
воообщем-то тоже самое, что сказала Golda

Объясняю суть задачи.
Требуется доработать проект большой энциклопедии, а именно добавить функцию списка "смотри также".
Т.е. каждая статья является вершиной графа. А в отдельном поле каждой статьи храняется связанные с ней по смыслу статьи. Понятное дело, что если 4я статья ссылается на 107ю, то и 107я должна ссылаться на 4ю.
Такой метод хранения был выбран поскольку акцент делается именно на незамедлительный просмотр связанных статей.

WolfON, еще раз посмотри на мою фразу: "Я сказал: "хранить родителей и детей отдельно для КАЖДОЙ вершины или единицы графа". Это совершенно другой смысл. " 

Ты не понимаешь меня ;)


Sunvas, тебе нужно как раз дерево, причем все рализовывается намного проще, чем ты думаешь.
Скажи, как храняться сами статьи в базе и должны ли показываться ссылки на "похожие" страницы, когда мы смотрим 4 статью, а для нее "похожая" 119, а для нее - 136, более глубоки по уровню "похожести"?

Статьи хранятся в одной таблице, со структурой:

id - номер статьи
title, contenet, [другие служебные поля]
seealso - вот тут мы через запятую и храним ссылки на другие статьи

Есть возможность сделать еще одну таблицу из двух полей или обязательно надо обойтись полем seealso?

Таблицу создать, проблем нет. Но опять таки, акцент делается именно на моментальную загрузку любой статьи с наименьшим количеством запросов.

Я бы сделал так.
Делаем таблицу из двух полей. Оба поля содержат ID статей.
Соотвественно в эти поля заносим два ID дву статей, которые "похожи" друг на друга.
Соответственно, когда надо достать список, делаем
SELECT `*` FROM myt WHERE id1 = $id OR id2 = $id.
Так получим список ID статей, которые так или иначе "похожи" на нашу.
Причем надо будет потом, из него (мы же получим матрицу из двух столбцов и n строк) сделать один массив, откуда удалить повторяющиеся (по хорошему этого быть не должно, надо следить за повторами на этапе добавления связи).
Затем делаем SELECT `*` FROM myt WHERE id1 IN ($mylist) OR id2 IN ($mylist).
Это уже два этапа вложенности, думаю хватит.
Проверок соответственно уже не надо делать, а саязана ли 4 с 3, если 3 связана с 4.

Хм. Я подумаю над таким вариантом. Однако статей в энциклопедии действительно много, за быстродействие опасаюсь. Нужен только один уровень вложенности.

Если действительно статей, как в википедии, то можно воспользоваться и одним полем в таблице самих статей. Сделать его строковым, к примеру разделить числа "|", ну и в момент редактирования статьи, если похожая статья добавляется, то ее надо добавить и в добавляемой. При удалении тоже самое. Я бы так сделал вряд ли. Уж на крайний случай сделал так, но в отдельной таблице, где есть поля только ID статьи и seealso.

Тут надо тестировать... 

А чем отдельная таблица лучше дополнительного поля?

Хранить в одном поле информацию, которую затем ещё и парсить, занятие, ИМХО, не из благородных (в отношении к серверу.).. т.к. вместо того, чтобы нормализовать БД вынеся всю схожую информацию в отдельную таблицу и выбирать это 1-2 запросами, Вы будете выбирать информацию, а потом средствами РНР её ещё и парсить... очень много интересеного по поводу древовидных структур в БД и работы с ними можно прочитать здесь.

Sunvas, отдельная таблица - ты покупаешь кухонный стол, а в единой таблице, ты покупаешь стол, тебе дают 20 стульев, 25 сервизов, лампочку и зубную счетку, и спрашивается а нафига мне напильник, если  не курю.

Fally, проблем с парсингом нет. Тут один хороший человек показал как сделать все красиво. Mal Hack, интересно объяснил. )

Mal Hack, объяснение - супер   

Кстати, Вы, фактически, повторили мою идею, и к дереву Ваш последний вариант отношения не имеет, т.к. не гарантируется ни связаность графа, ни отсутсвие циклов. Рассмотрите, например, вариант,

(1, 2, 3), (4,5) - где в каждых скобках - набор попарно связанных статей. Это никак не дерево.

Добавлю также, что если сделать сочетание (id1, id2) - первичным ключом, и выработать соглашение, благодаря которому пары всегда будут записываться в одном и том же порядке (например, id1 - всегда меньший, id2 - всегда больший, то и дополнительные запросы для проверки целостности не понадобятся. Ну и не забыть сделать для каждого из полей id1, id2 - внешний ключ с ON DELETE CASCADE, чтобы не заботиться о том, что будет со связями при удалении.

Sunvas, хранение нескольких значений в одном поле противоречит одному из ключевых принципов построения реляционной базы данных: атомарности полей таблиц. DB. Вы теряете на этом возможность переложить на базу данных часть забот о ее целостности и усложняете себе жизнь при составлении всевозможных запросов, кроме, может быть, одного, заранее выбранного. Вариант, при котором ребра хранятся отдельно от вершин, если проставлены все нужные ключи, дает Вам больше гарантий целостности базы и, думаю, должен положительно сказаться на быстродействии при выборе статьи. Вам ведь на самом деле, наверное, не id связанной статьи в базе нужно  показать, а какие-то другие ее поля (название, например).
Значит, понадобятся два запроса: одним выбирает seealso, а дальше в PHP нужно составлять второй запрос типа 



В случае же, о которым писали Mal Hack и я, несложно сделать все на уровне SQL, не прибегая к помощи PHP.



Но даже, если Вы не потратили впустую первый запрос, выбрав в нем все остальные данные о статье, конструкция IN в запрросе - не самая быстрая. Посмотрите, недавно Sta1ker приводил данные своего тестирования для MySQL. http://forum.vingrad.ru/forum/topic-165156.html

Подумайте о том, что усложняются и все остальные операции: добавления, удаления статей, выбора всевозможной статистики. Вы лишаете себя возможности сделать что бы то ни было, связанное с полем seealso, одним запросом.