WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 мая 2011 года.

Согласованность данных (иногда консистентность данных, англ. data consistency) — согласованность данных друг с другом, целостность данных, а также внутренняя непротиворечивость.

Согласованность в ER-модели

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

Согласованность в базах данных

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

Согласованность в теории алгоритмов и структур данных

В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 8 апреля 2015 года.

Чтобы сложные структуры данных выполняли свою функцию, на их содержимое приходится накладывать особые условия — условия согласованности. Другими словами: если записать случайные байты в числовой массив фиксированной длины, мы получим случайную кучу чисел, но ничего не «сломаем». Если записать случайные байты, например, в строку в UTF-8, мы можем получить цепочку, с точки зрения UTF-8 бессмысленную — целостность нарушена. Многие задачи, решаемые алгоритмистами и программистами, связаны с поиском эффективной структуры данных и реализацией механизмов поддержки её согласованности.

Например, условия согласованности двоичного дерева поиска таковы:

• Ни одна ссылка (кроме nil в «листьях» дерева) не ведёт в никуда.
• Отсутствие циклов (древовидность): если ходить по ссылкам и против ссылок, существует один-единственный путь между двумя узлами.
• Возрастание ключей в узлах дерева слева направо, а именно ключ в корневом узле должен быть меньше ключей узлов правого поддерева и больше ключей узлов левого поддерева.
• Если в каждом узле дерева поиска хранится также указатель parent на родительский узел, то возникает дополнительное условие согласованности: в каждом узле X указатель на родительский узел должен указывать на такой узел, в котором ровно один из указателей на детей (left или right) указывает на узел X.

Одно из определений инкапсуляции в ООП — никакой вызов метода, никакое присваивание полей не сможет увести объект из согласованного состояния в несогласованное.

См. также

• Модель данных
• ER-модель данных
• Структуры данных (теория алгоритмов)

Литература

• Techniques for Data Consistency in Large Scale Distributed Systems - A Probabilistic Perspective. — Wayne State University, 2008. — 125 с. — ISBN 9780549892878.