Software & Systems

Поддержка целостности информации является одной из основных функций современных реляционных СУБД. В каждой БД, помимо таблиц, присутствуют ограничения целостности и триггеры – программные объекты, предназначенные для поддержания целостности хранимой и обрабатываемой информации. Правильность и полнота реализации этих программных объектов обеспечивают высокую защищенность данных и, как следствие, способствуют повышению качества БД и информационной системы (ИС) в целом.

Тестирование и проверка ограничений целостности при проектировании и сопровождении БД являются залогом сохранности данных. Механизмам работы ограничений целостности и способам их тестирования посвящено большое число работ. К примеру, в [1] делается обзор современных методов и программных средств верификации реляционных БД. В работе [2] представлена утилита для автоматической генерации тестовых данных. Она случайным образом генерирует тестовые записи согласно критериям, заданным инженером по тестированию, и особенностям тестируемой БД. Критерии составляют схема БД, логические взаимосвязи между столбцами в таблицах, ссылочная целостность БД, количество генерируемых записей и т.д. Главной задачей утилиты является наполнение БД записями для ее (БД) последующего тестирования. Это может быть полезно, например, при проведении нагрузочного тестирования БД.

При тестировании ограничений целостности распределенных БД возникает своя специфика. Описанный в [3] инструмент извлекает некоторые данные из схемы БД и создает набор update-опера­ций (так называемых шаблонов), которые могут нарушить ограничения целостности. Далее составляются интеграционные тесты. Таким образом, для одного ограничения целостности могут быть составлены один или несколько шаблонов, которые содержат один или несколько тестов. В процессе выполнения выбираются ограничение целостности, соответствующие ему шаблоны тестирования и интеграционные тесты. Интеграционные тесты ранжируются, для чего предложен оригинальный способ ранжирования, учитывающий расположение серверов распределенной БД. Таким образом, выбирается тест, максимально использующий локальную информацию БД и минимизирующий данные, которые необходимо передать по сети для выполнения теста. Это заметно снижает нагрузку на БД при проведении тестирования, так как, согласно [4], в распределенных БД стоимость доступа к удаленным данным в наибольшей степени влияет на производительность.

При эксплуатации программной системы достаточно часто необходима ее модификация. Соответственно возникает необходимость убедиться в том, что работающая БД соответствует документации. Для этого можно использовать приложение, описанное в [5]. Оно анализирует ER-диаграмму и введенные в него ограничения целостности. На основе этой информации генерируются запросы (create, update, delete), совокупность которых полностью покрывает все имеющиеся в БД ограничения целостности и позволяет проверить БД на соответствие спецификации. Далее приложение анализирует результаты выполнения этих операций и составляет набор запросов (alter), позволяющих привести существующую БД к требуемому виду.

В процессе верификации ПО возникает необходимость проверки соответствия БД формальной спецификации. В этом случае целесообразно применение формальных методов верификации по отношению к реляционным БД. Требования целостности реляционных БД, как правило, хорошо формализуются, причем для формализации подходит язык реляционной алгебры, знакомый любому специалисту по реляционным БД. Разработка методики и программной системы для формальной верификации реляционных БД на соответствие требованиям целостности является актуальной задачей в области обеспечения и оценивания качества автоматизированных ИС.

Программная система для формальной верификации реляционных БД

Оригинальный метод формальной верификации реляционных БД в части ограничений целостности и триггеров реализует Constraints Validator. Используемый метод предполагает логико-алгеб­раическое моделирование требований целостности. Каждое требование целостности в специ- фикации должно быть описано с помощью пре- диката, называемого формальный описатель (логическое выражение, используемое для формулирования требования на выбранном языке спецификаций; представляет собой логическое утверждение того, что некоторое множество состояний данных в указанных условиях является допустимым). Спецификация на БД в целом представляет собой набор формальных описателей всех требований целостности. Безошибочность описателей проверяется на ранних стадиях жизненного цикла БД, после чего список описателей фиксируется и далее не изменяется. Таким образом, описатели выражают формальные требования заказчика к БД.

Формальное описание требований целостности (правила, при помощи которого задается множество допустимых значений некоторого атрибута сущности/связи или принцип логического согласования записей БД между собой) согласуется с логической схемой данных. Если создается реляционная БД, то схема данных описывается в терминах теории отношений, а требования целесообразно описывать на языке реляционной алгебры. В общем случае формальный описатель требования целостности имеет следующий вид: Expr(tables)½ins(T1) Ú … Ú ins(Tn) Ú upd(T1) Ú … Ú upd(Tn) Ú del(T1) Ú … Ú del(Tn), где tables={T1, T2, …, Tn} – множество таблиц, связываемых данным ограничением; ins(), upd(), del() – предикаты выполнения DML-опера­торов вставки, обновления и удаления строк таблиц соответственно. Перечень предикатов в описателе после знака «|» показывает, при выполнении каких операций должно быть истинным логическое условие Expr(tables).

Спецификация оформляется в виде текстового файла и используется в качестве входных данных программы. Каждой реляционной операции в описателях соответствует некоторый символьный псевдокод.

Для общего требования целостности можно не указывать перечень операций в явном виде. Например, требование «масса груза всегда положительна» является общим, на что указывает слово «всегда». Предположим, для хранения сведений о грузах используется таблица loads, массы грузов записываются в столбец mass. Тогда формальный описатель этого требования будет выглядеть так: smass£0(loads)=Æ, а в программной системе его можно представить с использованием псевдокода реляционных операций: [mass£0](loads)=0.

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

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

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

·     часть требований целостности не была реализована (есть описатели заявленных требований, которым не соответствует ни один восстановленный описатель);

·     в БД имеются лишние объекты-ограничения или нужные объекты-ограничения содержат недекларированные возможности (некоторые из восстановленных описателей не соответствуют в точности ни одному из описателей исходных требований).

Обработка типовых ограничений целостности

В реляционных БД существует ряд типовых ограничений целостности: первичный ключ, уникальность значений, определенность значений, ограничение домена (ограничение по логическому условию) и внешний ключ. Типовые требования целостности, как и любые другие, могут быть смоделированы с помощью формальных описателей, которые также можно назвать типовыми. Такие конструкции  сравнительно легко распознаются программной системой.

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

Например, к первичному ключу предъявляются два требования – уникальность и определенность каждого значения. Следовательно, ни одно значение не будет повторяться дважды и ни одно значение не будет NULL. Пусть имеется отношение R и в нем атрибут x (возможно, составной). Тогда ограничение целостности «Первичный ключ» будет выглядеть следующим образом:

sCOUNT(x)>1Ú(x is null)(gx(R))=Æ,

а в программной системе будет представлено как [COUNT(x)>1 & (x is null)](х[R])=0.

Обработка триггеров

Триггеры являются более гибким средством поддержания корректности данных в БД. Каждый триггер содержит процедурную реализацию некоторого алгоритма поддержки целостности, поэтому для триггеров не могут существовать типовые описатели.

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

Восстановление описателя по коду триггера проходит в несколько этапов. Вначале програм- мная система восстанавливает промежуточные описатели по каждому простому оператору в теле триггера с применением словаря промежуточных описателей. Если программе не удается автоматически подобрать по словарю для некоторого SQL-оператора промежуточный описатель, этим занимается эксперт. Затем промежуточные описатели соединяются в один описатель путем применения ряда правил восстановления описателей по условному и циклическому операторам и различным вариантам следования друг за другом простых, условных и циклических конструкций. Для вывода правил восстановления промежуточных описателей авторы использовали аппарат логики Ч. Хоара.

Чтобы восстановить описатель по триггерной связке, необходимо восстановить описатели по каждому триггеру БД, а затем найти описатели с одинаковыми Expr(tables). Для этого, возможно, потребуется выполнить ряд эквивалентных преобразований, чтобы привести несколько описателей к одному виду. Решение о выполнении эквивалентных преобразований принимается экспертом, а сами преобразования выполняются программной системой.

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

Обработка триггеров программой Constraints Validator

Рассмотрим для примера упрощенную БД системы пассажирских перевозок, в которой имеются таблицы coaches (вагоны поезда) и seats (места). Требование целостности состоит в следующем:

Если вагон является купейным, то номер любого места в нем не больше 36.

Номер места хранится в столбце seat_number таблицы seats, тип вагона – в столбце coach_type таблицы coaches.

Требование целостности можно переформулировать следующим образом: ни в какой момент в соединении таблиц seats и coaches не должно быть строк, в которых одновременно указаны купейный тип вагона и номер места больше 36. Формальный описатель данного требования в аналитической форме выглядит так:

,

а в псевдокоде, используемом программой Con­straints Validator, следующим образом: [coach_ty­pe=’Купе’&seats_number>36](seats*coaches)=0.

Данное требование целостности реализовано в БД с помощью связки из двух триггеров: tr_seat_num и tr_coach_seat_num. Ниже приведены коды триггеров на языке Transact-SQL.

create trigger tr_seat_num

   on seats

   for insert, update

   as

   if exists (select * from coaches, seats

         where coach_type = 'Купе'

         and seat_number > 36

         and coaches.id_coach=seats.id_coach)

   rollback tran

create trigger tr_coach_seat_num

   on coaches

   for update

   as

   if exists (select * from coaches, seats

         where coach_type = 'Купе'

         and seat_number > 36

         and coaches.id_coach = seats.id_coach)

   rollback tran

Требуется провести верификацию этих триггеров, то есть проверить, корректно ли они реализуют заданное требование.

На вход программы Constraints Validator подаются файл спецификации с исходным описателем и SQL-скрипт с кодами триггеров. Затем эксперт запускает процесс автоматизированного восстановления описателей по триггерам, которое происходит в следующем порядке. Тело первого триггера начинается с оператора if и содержит единственную конструкцию вида if C rollback tran. Здесь C – это условие exists(select…). Вначале восстанавливается промежуточный описатель Desc(C). Здесь речь идет о том, что существует множество строк, получаемых при применении некоторой последовательности реляционных операций к таблицам coaches, seats, то есть получаем:

.

Запись при помощи используемого в программе псевдокода будет выглядеть следующим образом: [coach_type=’Купе’ & seats_number>36] (seats * coaches) !=0.

Из тела триггера видно: если БД приходит в состояние Desc(C), триггер откатывает транзакцию. В результате Desc(C) перестает быть истиной. Очевидно, что постусловием данной конструкции будет:

или [coach_type=’Купе’ & seats_number>36] (seats * coaches)=0.

Больше в теле триггера операторов нет. Учитывая, что триггер срабатывает на вставку и обновление в таблице seats, имеем описатель по триггеру tr_seat_num:

или [coach_type=’Купе’ & seats_number>36] (seats * coaches) = 0 | ins(seats), upd(seats).

Аналогичным образом Constraints Validator восстановит описатель по триггеру tr_coach_seat_ name, который работает так же, как и tr_seat_num, но реагирует на обновление строк таблицы coaches. Поэтому восстановленный по его коду описатель выглядит так:

или [coach_type=’Купе’ & seats_number>36] (seats * coaches) = 0 | upd(coaches).

Следующая стадия – поиск восстановленных описателей с эквивалентной левой частью (частью до вертикальной черты). Следует обратить внимание, что именно два восстановленных описателя одинаковы в левой части. Беря их за основу, получим описатель реализованного в БД ограничения:

Эквивалентная запись в псевдокоде Constraints Validator будет выглядеть следующим образом:

[coach_type=’Купе’&seats_number>36](seats* coaches) = 0 | ins(seats), upd(seats), (coaches).

Сравним этот описатель с исходным описателем требования в спецификации:

[coach_type=’Купе’ & seats_number>36](seats * coaches)=0.

Строго говоря, описатели не совсем совпадают: исходный описатель распространяется на все триггерные события в таблицах seats и coaches, а восстановленный – только на 3 из них. Следовательно, программа не сможет самостоятельно установить полное соответствие между спецификацией и реализацией и сообщит эксперту лишь о найденном частичном соответствии. Установить, не нарушается ли в реализованной БД условие

 при выполнении операций del(seats), ins(coaches) и del(coaches), – это задача эксперта.

Программа Constraints Validator позволяет автоматизировать процесс тестирования типовых и частично нетиповых ограничений целостности БД. В ней реализованы возможности логико-ал­гебраического моделирования требований целостности, анализа SQL-кода, построения модели реализации функций целостности и сравнения модели реализации со спецификацией. Используемый метод верификации дает возможность проводить анализ БД на соответствие формальным требованиям целостности, находить случайные и умышленные дефекты в ограничениях целостности и триггерах, не прибегая к разработке сложных тестовых сценариев.

Литература

1.   Глухарев М.Л. Современные методы и программные средства тестирования и верификации реляционных баз данных. Инновации на железнодорожном транспорте-2009: докл. юбилейной науч.-технич. конф. (28–29 сентября 2009 г. С.-Петербург). СПб: ПГУПС, 2009. С. 68–73.

2.   Piriyakitpaiboon K. and Suwannasart T. RealGen: A Test Data Generation Tool to Support Software Testing / In the proc. of the second international conference on information and communication technologies (ICT2004). Assumption University, Bangkok, Thailand, Nov. 18–19, 2004.

3.   Alwan A.A., Ibrahim H., Udzir N.I. A Framework for Checking Integrity Constraints in a Distributed Database. 2008. ICCIT 08. Third International Conference on Convergence and Hybrid Information Technology. Vol. 1. Busan, Korea, Nov. 11–13, 2008, pp. 644–650.

4.   Ibrahim H., Gray W.A., and Fiddian N.J. Optimizing Fragment Constraints – a Performance Evaluation / International Journal of Intelligent Systems – Verification and Validation Issues in Databases, Knowledge-Based Systems, and Ontologies. New York, John Wiley & Sons Inc, 2001. 16(3), pp. 285–306.

5.   Tongrak P., Suwannasart T. A Tool for Generating Test Case from Relational Database Constraints Testing / Computer Science and Information Technology (ICCSIT 2009). 2nd IEEE International Conference on Date: Aug. 8–11. Beijing, China, 2009, pp. 435–439.