Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 15
Текст из файла (страница 15)
При обходедерева в ширину нужно обязательно хранить в памяти всевершины очередного яруса. Это требует большого расходапамяти. Например, в 100-м ярусе двоичного дерева содержится299 вершин. Вычислительных ресурсов всего земного шара нехватит, чтобы хранить информацию обо всех этих вершинах.\СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратом основана наследующих принципах:1. все программные утверждения упорядочиваются;2. на каждом шаге обхода из текущей вершины Gосуществляется переходлибо в новую вершину-потомок G 0 , которая являетсяSLD-резольвентой запроса G и первого по порядкупрограммного утверждения D, ранее не использованногодля этой цели;I либо в ранее построенную родительскую вершину G 00(откат), если все программные утверждения уже былиопробованыдля построения SLD-резольвентзапроса G .СТРАТЕГИИВЫЧИСЛЕНИЙЛОГИЧЕСКИХIПРОГРАММСтратегия обхода в глубину с возвратомIIимеет эффективную реализацию: в памяти нужно хранитьлишь запросы той ветви, по которой идет обход, и каждыйзапрос должен вести учет использованных программныхутверждений;является, к сожалению, вычислительно неполной.Стратегия обхода в глубину чувствительна к порядкурасположения программных утверждений в логическихпрограммах.
Результат вычисления запроса может изменитьсяпри перестановке программных утверждений. Посколькусоображения эффективности превалируют над требованиямивычислительной полноты, в качестве стандартной стратегиивычисления логических программ выбрана стратегия обхода вглубину.
Программист должен сам выбрать нужный порядокрасположения программных утверждений, чтобы стандартнаяСТРАТЕГИИВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХстратегия вычисления отыскала все вычисленные ответы.ПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y )P(X , X )R(b) ;Q(c) ;R(X ), Q(Y );Q(X );?P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }✓@I@@R t?Q(X1 ), R(X1 )?R(X1 ), Q(Y1 ), R(X1 ) t@@6(2), {X1 /c}(3), {X1 /b} 6(1), {U/X1 , V /Y1 }?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), "?t?⇤?t?R(c)failure5. Транзакционное управление в СУБД.
Методы сериализации транзакций. Поддержание механизма транзакций - показатель уровня развитости СУБД. Корректноеподдержание транзакций одновременно является основой обеспечения целостности баз данных(и поэтому транзакции вполне уместны и в однопользовательских персональных СУБД), атакже составляют базис изолированности пользователей во многопользовательских системах.Часто эти два аспекта рассматриваются по отдельности, но на самом деле они взаимосвязаны,что и будет показано в этой лекции.Под транзакцией понимается неделимая с точки зрения воздействия на БДпоследовательность операторов манипулирования данными (чтения, удаления, вставки,модификации) такая, что либо результаты всех операторов, входящих в транзакцию,отображаются в БД, либо воздействие всех этих операторов полностью отсутствует.
Лозунгтранзакции - "Все или ничего": при завершении транзакции оператором COMMIT результатыгарантированно фиксируются во внешней памяти (смысл слова commit - "зафиксировать"результаты транзакции); при завершении транзакции оператором ROLLBACK результатыгарантированно отсутствуют во внешней памяти (смысл слова rollback - ликвидироватьрезультаты транзакции).Понятие транзакции имеет непосредственную связь с понятием целостности БД. Очень частоБД может обладать такими ограничениями целостности, которые просто невозможно ненарушить, выполняя только один оператор изменения БД. Например, в базе данныхСОТРУДНИКИ-ОТДЕЛЫ естественным ограничением целостности является совпадениязначения атрибута ОТД_РАЗМЕР в кортеже отношения ОТДЕЛЫ, описывающем данныйотдел (например, отдел 320), с числом кортежей отношения СОТРУДНИКИ таких, чтозначение атрибута СОТР_ОТД_НОМЕР равно 320.
Как в этом случае принять на работу вотдел 320 нового сотрудника? Независимо от того, какая операция будет выполнена первой,вставка нового кортежа в отношение СОТРУДНИКИ или модификация существующегокортежа в отношении ОТДЕЛЫ, после выполнения операции база данных окажется внецелостном состоянии.Поэтому для поддержания подобных ограничений целостности допускается их нарушениевнутри транзакции с тем условием, чтобы к моменту завершения транзакции условияцелостности были соблюдены. В системах с развитыми средствами ограничения и контроляцелостности каждая транзакция начинается при целостном состоянии БД и должна оставитьэто состояние целостными после своего завершения.
Несоблюдение этого условия приводит ктому, что вместо фиксации результатов транзакции происходит ее откат (т.е. вместооператора COMMIT выполняется оператор ROLLBACK), и БД остается в таком состоянии, вкотором находилась к моменту начала транзакции, т.е. в целостном состоянии.Если быть немного более точным, различаются два вида ограничений целостности: немедленнопроверяемые и откладываемые. К немедленно проверяемым ограничениям целостностиотносятся такие ограничения, проверку которых бессмысленно или даже невозможнооткладывать. Примером ограничения, проверку которого откладывать бессмысленно,являются ограничения домена (возраст сотрудника не может превышать 150 лет). Болеесложным ограничением, проверку которого невозможно отложить, является следующее:зарплата сотрудника не может быть увеличена за одну операцию более, чем на 100,000 рублей.Немедленно проверяемые ограничения целостности соответствуют уровню отдельныхоператоров языкового уровня СУБД.
При их нарушениях не производится откат транзакции, алишь отвергается соответствующий оператор.Откладываемые ограничения целостности - это ограничения на базу данных, а не на какие-либо отдельные операции. По умолчанию такие ограничения проверяются при концетранзакции, и их нарушение вызывает автоматическую замену оператора COMMIT наоператор ROLLBACK. Однако в некоторых системах поддерживается специальный операторнасильственной проверки ограничений целостности внутри транзакции.
Если послевыполнения такого оператора обнаруживается, что условия целостности не выполнены,пользователь может сам выполнить оператор ROLLBACK или постараться устранитьпричины нецелостного состояния базы данных внутри транзакции (видимо, это осмысленнотолько при использовании интерактивного режима работы).И еще одно замечание. С точки зрения внешнего представления в момент завершениятранзакции проверяются все откладываемые ограничения целостности, определенные в этойбазе данных. Однако при реализации стремятся при выполнении транзакции динамическивыделить те ограничения целостности, которые действительно могли бы быть нарушены.Например, если при выполнении транзакции над базой данных СОТРУДНИКИ-ОТДЕЛЫ вней не выполнялись операторы вставки или удаления кортежей из отношения СОТРУДНИКИ,то проверять упоминавшееся выше ограничение целостности не требуется (а проверкаподобных ограничений вызывает достаточно большую работу).Во многопользовательских системах с одной базой данных одновременно могут работатьнесколько пользователей или прикладных программ.
Предельной задачей системы являетсяобеспечение изолированности пользователей, т.е. создание достоверной и надежнойиллюзии того, что каждый из пользователей работает с БД в одиночку.В связи со свойством сохранения целостности БД транзакции являются подходящимиединицами изолированности пользователей. Действительно, если с каждым сеансом работы сбазой данных ассоциируется транзакция, то каждый пользователь начинает работу ссогласованным состоянием базы данных, т.е. с таким состоянием, в котором база данныхмогла бы находиться, даже если бы пользователь работал с ней в одиночку.При соблюдении обязательного требования поддержания целостности базы данных возможныследующие уровни изолированности транзакций:1.
Первый уровень - отсутствие потерянных изменений. Рассмотрим следующий сценарийсовместного выполнения двух транзакций. Транзакция 1 изменяет объект базы данныхA. До завершения транзакции 1 транзакция 2 также изменяет объект A. Транзакция 2завершается оператором ROLLBACK (например, по причине нарушения ограниченийцелостности).
Тогда при повторном чтении объекта A транзакция 1 не видит измененийэтого объекта, произведенных ранее. Такая ситуация называется ситуацией потерянныхизменений.Естественно,онапротиворечиттребованиюизолированностипользователей. Чтобы избежать такой ситуации в транзакции 1 требуется, чтобы дозавершения транзакции 1 никакая другая транзакция не могла изменять объект A.Отсутствие потерянных изменений является минимальным требованием к СУБД почасти синхронизации параллельно выполняемых транзакций.2. Второй уровень - отсутствие чтения "грязных данных".
Рассмотрим следующий сценарийсовместного выполнения транзакций 1 и 2. Транзакция 1 изменяет объект базы данныхA. Параллельно с этим транзакция 2 читает объект A. Поскольку операция измененияеще не завершена, транзакция 2 видит несогласованные "грязные" данные (в частности,операция транзакции 1 может быть отвернута при проверке немедленно проверяемогоограничения целостности). Это тоже не соответствует требованию изолированностипользователей (каждый пользователь начинает свою транзакцию при согласованномсостоянии базы данных и в праве ожидать видеть согласованные данные).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
