Алгоритмы для обновления реляционных данных

Question

Какие алгоритмы, как известно, выполняют задачу по обновлению базы данных путем вставки, обновления и удаления строк при наличии ограничений базы данных?

В частности, скажем, что перед образами строк, подлежащих удалению, после изображений вставленных строк и обоими изображениями обновляемых строк находятся в памяти. Строки могут быть для нескольких таблиц. Точная последовательность обновлений либо неизвестна, либо не была сохранена - известны только предыдущие изображения и изображения после того, как база данных должна быть сделана для отражения.

База данных содержит первичный ключ, внешний ключ и уникальные ограничения индекса. Проблема состоит в том, чтобы найти последовательность команд, чтобы обновить базу данных. Для простоты я хочу указать, что первичный ключ строки никогда не будет изменен.

Система базы данных не поддерживает проверку отложенных ограничений. (Это решение тривиально для таких баз данных). Я также должен сделать правило, что столбцы первичных ключей не могут быть обновлены после вставки, и не разрешается удалять строку и повторно вставлять ее с тем же самым первичным ключом, хотя некоторые алгоритмы могут в противном случае найти это удобно. (Это необходимо для наиболее распространенных сценариев, где все первичные ключи автоматически сгенерирован системой базы данных.)

Какие алгоритмы:

1. Если предположить, что ограничения внешнего ключа должно быть приведено в исполнение в любое время, но уникальные индексы не являются используемый.
2. Предполагая, что ограничения внешнего ключа и уникальные ограничения индекса должны быть соблюдены в любое время.

Я прошу, потому что я думаю, что # 1 может быть значительно проще.

EDIT: Цель состоит в том, чтобы решить проблему отсутствия проверки отложенных ограничений в общем (или почти общем смысле) пути. Я полагаю, что высококачественные пакеты ORM должны это сделать. Я хочу объяснить алгоритмы, предоставленные вами здесь или извне в академической статье и т. Д. Я не буду рассматривать указатель на программный пакет или исходный код на этот вопрос.

НАИВНЫЙ АЛГОРИТМ:

петли через таблицы и для каждой строки, которая добавляется, изменение или удаление генерации одного INSERT, UPDATE или DELETE заявление, соответственно, для каждого из них. Прокрутите созданные сгенерированные операторы и примените к базе данных. Если заявление не применяется, продолжайте работу с другими операциями. Повторите утверждения, которые потерпели неудачу. Продолжайте повторять, пока не будет больше сбоев, или пропуск успешно не выполняет никаких заявлений. Если утверждения остаются, попробуйте временную настройку данных в проблемных столбцах, чтобы попытаться добиться успеха.

Это уродливый алгоритм грубой силы и выяснение части «временной настройки» - это самостоятельная задача. Итак, мне нужен улучшенный и полный алгоритм.

EDIT2:

RBarryYoung сообщений ответ, который получает близко (но не сигары), чтобы полностью решить сценарий № 1 при решении наиболее распространенных сценария # 2 проблемы одновременно. Ниже приведен пример шаблона обновления сценария № 1. Я видел очень часто в приложениях, но еще не достиг решения.DELETE/UPDATE-INSERT точно соответствует времени в сценарии №1, но трюк заключается в том, чтобы выяснить, когда отклоняться от него. Я также подозреваю, что отклонение от него увеличивает количество УНИКАЛЬНЫХ проблем по сценарию № 2, возможно, увеличивая мой интерес к решению сценария №2.

Обратите внимание, что нет никаких циклов и никаких первичных ключей не изменено. Однако внешний ключ для родителя изменяется.

CREATE TABLE A 
(
    AId INT NOT NULL PRIMARY KEY 
) 

CREATE TABLE B 
(
    BId INT NOT NULL PRIMARY KEY, 
    AId INT NOT NULL FOREIGN KEY REFERENCES A (AId) 
) 

CREATE TABLE C 
(
    CId INT NOT NULL PRIMARY KEY, 
    AId INT NOT NULL FOREIGN KEY REFERENCES A (AId), 
    BId INT NOT NULL FOREIGN KEY REFERENCES B (BId) 
) 

Перед Изображения:

A (1) 
B (1,1) 
C (1,1,1) 

После того, как изображения:

A (1) 
B (2,1) [To be deleted: (1,1)] 
C (1,1,2) 

сортировки: A, B, C

Первая команда DELETE B (1,1) который терпит неудачу из-за C (1,1,1).

Обратите внимание, что если третий столбец в C допускает NULL (которого в этом случае нет), чистое решение может включать в себя NULLing его в раннем проходе, поскольку это позволило бы данному алгоритму нормально работать и иметь обычный преимущества для решения большинства проблем сценария №2. Отличное решение этой проблемы должно учитывать и такие вещи. Полная общность этого вопроса, несомненно, является увлекательной проблемой.

Answer 1

Похоже, вы ищете инструмент Diff для базы данных. Такой инструмент будет искать различия между двумя таблицами (или двумя базами данных) и генерировать необходимые скрипты для их выравнивания.

Смотрите следующую запись для получения дополнительной информации:
https://stackoverflow.com/questions/104203/anyone-know-of-any-good-database-diff-tools

Answer 2

OpenDbDiff имеет исходный код. Вы можете посмотреть на это и выяснить алгоритмы.

http://opendbiff.codeplex.com/Release/ProjectReleases.aspx?ReleaseId=25206

Answer 3

я написал один раз, но это чужой IP, так что я не могу вдаваться в излишние подробности. Тем не менее, я готов рассказать вам о процессе, который научил меня, как это сделать. Это было инструментом, чтобы сделать теневую копию «базы данных» клиента, находящейся на salesforce.com, написанной на .NET 1.1.

Я начал с этого делать грубой силой (создайте DataSet и базу данных из схемы, отключите ограничения в DataSet, проведите по каждой таблице, загрузите строки, игнорируя ошибки, для строк, которые еще не находятся в таблице, повторяйте до тех пор, пока не добавится больше строк, или больше ошибок, или нет изменений в количестве ошибок, затем выгрузите DataSet в базу данных до тех пор, пока не будет ошибок и т. д.).

Грубая сила была отправной точкой, потому что не было уверенности, что мы могли бы сделать это вообще. «Схема» salesforce.com не была истинной реляционной схемой. Например, если я правильно помню, были некоторые столбцы, которые были внешними ключами, относящимися к одной из нескольких родительских таблиц.

Это заняло навсегда даже при отладке. Я начал замечать, что большую часть времени тратили на обработку нарушений ограничений в базе данных. Я начал замечать структуру нарушений ограничений, так как каждая итерация медленно сходилась, чтобы сохранить все сохраненные строки.

Все откровения, которые у меня были, были связаны с моей скукой, наблюдая, как система сидит около 100% процессора в течение 15-20 минут за раз, даже с небольшой базой данных.«Необходимость - мать изобретения», и «перспектива ждать еще 20 минут для тех же рядов, как правило, фокусирует ум», и я выяснил, как ускорить работу в более чем 100 раз.

Answer 4

Хорошо, я думаю, что это все, хотя вещь Unique Key довольно трудно понять. Обратите внимание, что любые ошибки, возникающие при выполнении SQL, должны приводить к полному откату всей транзакции.

UPDATE: оригинальный порядок, который я реализовал был:

Каждая таблица, BottumUp (все Удаление для таблицы) Каждая таблица, TopDown (Все обновления, то все Вставки)

После встречный пример, я считаю, что знаю, что я исправлю только ограниченную проблему (проблема №1, без UC): путем изменения порядка:

Каждая таблица, TopDown (все вставки) Каждая таблица, Низходящий(Все обновления) Каждая таблица, BottumUp (все удаляет)

Это, безусловно, НЕ работает с уникальными ограничениями, хотя, насколько мне представляется, потребуется сортировка зависимостей на основе строки (в отличие от статической таблицы FK зависимая сортировка, которую я сейчас использую). Особо сложным является то, что может потребоваться получить информацию о записывающем содержимом, отличном от измененных (в частности, проверка наличия значений конфликта UC и дочерних записей для промежуточных шагов).

Во всяком случае, вот текущая версия:

Public Class TranformChangesToSQL 
Class ColVal 
    Public name As String 
    Public value As String 'note: assuming string values' 
End Class 

Class Row 
    Public Columns As List(Of ColVal) 
End Class 

Class FKDef 
    'NOTE: all FK''s are assumed to be of the same type: records in the FK table' 
    ' must have a record in the PK table matching on FK=PK columns.' 
    Public PKTableName As String 
    Public FKTableName As String 
    Public FK As String 
End Class 

Class TableInfo 
    Public Name As String 
    Public PK As String      'name of the PK column' 
    Public UniqueKeys As List(Of String) 'column name of each Unique key' 
    'This table''s Foreign Keys (FK):' 
    Public DependsOn As List(Of FKDef) 
    'Other tables FKs that point to this table' 
    Public DependedBy As List(Of FKDef) 
    Public Columns As List(Of String) 
    'note: all row collections are indexed by PK' 
    Public inserted As List(Of Row)  'inserted after-images' 
    Public deleted As List(Of Row)  'deleted before-images' 
    Public updBefore As List(Of row) 
    Public updAfter As List(Of row) 
End Class 

Sub MakeSQL(ByVal tables As List(Of TableInfo)) 
    'Note table dependencies(FKs) must NOT form a cycle' 

    'Sort the tables by dependency so that' 
    ' child tables (FKs) are always after their parents (PK tables)' 
    TopologicalSort(tables) 

    For Each tbl As TableInfo In tables 
     'Do INSERTs, they *must* be done first in parent-> child order, because:' 
     ' they may have FKs dependent on parent inserts' 
     ' and there may be Updates that will make child records dependent on them' 
     For Each r As Row In tbl.inserted 
      Dim InsSQL As String = "INSERT INTO " & tbl.Name & "(" 
      Dim valstr As String = ") VALUES(" 
      Dim comma As String = "" 
      For Each col As ColVal In r.Columns 
       InsSQL = InsSQL & comma & col.name 
       valstr = valstr & comma & "'" & col.value & "'" 
       comma = ", " 'needed for second and later columns' 
      Next 
      AddSQL(InsSQL & valstr & ");") 
     Next 
    Next 

    For Each tbl As TableInfo In tables 
     'Do UPDATEs' 
     For Each aft In tbl.updAfter 
      'get the matching before-update row' 
      Dim bef As Row = tbl.updBefore(aft.Columns(tbl.PK.ColName).value) 
      Dim UpdSql As String = "UPDATE " & tbl.Name & " SET " 
      Dim comma As String = "" 
      For Each col As ColVal In aft.Columns 
       If bef.Columns(col.name).value <> col.value Then 
        UpdSql = UpdSql & comma & col.name & " = '" & col.value & "'" 
        comma = ", " 'needed for second and later columns' 
       End If 
      Next 
      'only add it if any columns were different:' 
      If comma <> "" Then AddSQL(UpdSql & ";") 
     Next 
    Next 

    'Now reverse it so that INSERTs & UPDATEs are done in parent->child order' 
    tables.Reverse() 

    For Each tbl As TableInfo In tables.Reverse 
     'Do DELETEs, they *must* be done last, and in child->paernt order because:' 
     ' Parents may have children that depend on them, so children must be deleted first,' 
     ' and there may be children dependent until after Updates pointed them away' 
     For Each r As Row In tbl.deleted 
      AddSQL("DELETE From " & tbl.Name & " WHERE " & tbl.PK.ColName & " = '" & r.Columns(tbl.PK.ColName).value) & "';" 
     Next 
    Next 

End Sub 
End Class 

Answer 5

Нет, я не нахожу это увлекательным. Я не считаю, что проблема квадратурного круга тоже увлекательна, и на этой теме тоже существуют люди, которые сильно или даже жестоко не согласны со мной.

Когда вы говорите, что «у него практические приложения», вы хотите сказать, что «решение этой проблемы имеет практическое применение»? Я предлагаю, чтобы решение, которое не существует, по определению не может иметь «практических приложений». (И я полагаю, что решение, которого вы ищете, не существует, как квадратура круга.)

Вы что-то спорили о том, «когда другие приложения зависают от каскадных удалений ...». В вашем первоначальном заявлении о проблеме не упоминалось ничего о «других приложениях».

Проблема, которую я нахожу более увлекательной, - «как создать СУБД, которая достаточно хороша, чтобы программисты больше не сталкивались с такими проблемами и больше не должны были задавать такие вопросы». Такая СУБД поддерживает множественное назначение.

Желаю вам удачи.

Answer 6

Почему вы даже пытаетесь это сделать? Правильный способ сделать это - заставить механизм базы данных отложить проверку ограничений до совершения транзакции.

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

Как я уже сказал, правильный способ сделать это - отключить ограничения до тех пор, пока все SQL-запросы не будут запущены, а затем снова включите их для фиксации. Конец будет терпеть неудачу, если ограничения не будут выполнены. Postgres (например) имеет функцию, которая делает это очень легко.