Анализ специфики обработки неопределенных типов данных

А.С. Синельников, аспирант

УДК 681.324.001
Анализ специфики обработки неопределенных типов данных
для интеллектуальных информационных систем
А.С. Синельников, аспирант
руководители: к.т.н., доцент Е.С. Васяева, к.т.н., доцент Н.С. Васяева
Марийский государственный технический университет, г. Йошкар-Ола,
e-mail: a_sinelnikov@mail.ru

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

Введение
Современные информационные системы, будь то системы управления базами данных (СУБД), системы логического вывода или информационно-поисковые системы, должны корректно функционировать при условии, что некоторые данные в схеме данных отсутствуют или истинность их сомнительна. В литературе [2, 10] для обозначения таких данных принят термин “неопределенные данные (значения)” или null-значения. Это понятие впервые было преложено Э.Ф. Кодом. Системы, которые используют неопределенные значения, называются системами с неполной информацией, а само выражение «база данных с неполной информацией» впервые было введено В. Липским.
Хотя многие известные авторы в этом вопросе не пришли к общему мнению, т.е. каким образом включать неопределенные значения в модели данных (а именно в реляционные), чтобы они не противоречили начальному определению алгебраической модели данных, основанной на двузначной логике, все они в той или иной степени учитывают неопределенный тип данных в своих моделях. В частности, предложена трехзначная (Э.Ф. Кодд) и четырехзначная логики (Н. Белнап) с одним и двумя неопределенными значения соответственно.
В [7] Э.Ф. Кодд впервые затронул проблему неопределенных значений и ввел null-значения в реляционную теорию, дополняя традиционную двухзначную логику с значениями ИСТИНА и ЛОЖЬ третьим значением НЕИЗВЕСТНО. Четырехзначная логика Н. Белнапа основана на двух неопределенных значениях NONE (неопределенность) и BOTH (переопределенность или противоречивость) [10].
Введение null-значения с одной стороны делает возможным применение неопределенных типов данных в реляционной теории, но с другой стороны порождает определенные проблемы [3]. Главные проблемы, порождаемые null-значениями, связаны с тем, что сравнение null-значения с любым другим значением (в том числе и сравнение null=null) дает значение НЕИЗВЕСТНО, а также с тем, что для обозначения разных типов неопределенных данных служит одно значение null, что затрудняет интерпретацию полученной информации. Считается, что при интерпретации значение null необходимо исходить из контекста его применения, что не всегда является возможным. В определенной степени эта проблема решается, если свести типы неопределенных значений в дерево. Такое дерево, описывающее все известные типы неопределенных значений, подробно рассмотрено в работе М.Ш. Цаленко [10]. Применение к null-значению типа неопределенности данных позволяет реализовать гибкую и интеллектуальную обработку таких значений.
Альтернативным подходом к решению проблемы неопределенных данных является использование значений по умолчанию (специальных значений). Сторонником такого подхода является К.Дж. Дейт, который предложил использовать значения по умолчанию вместо null-значений, что позволяет оставаться в пределах двузначной логики [3]. В этом случае система неопределенных данных выносится за пределы самой модели баз данных (БД), что в последнее время рассматривается как недостаток. Другим недостатком является тот факт, что резервирование некоторых значений домена для специального применения сужает область определения реальных значений.
Несмотря на отсутствие стройной теории представления и обработки неопределенных данных, все авторы едины во мнении, что развивать это направление необходимо, поскольку если информационная система поддерживает модель данных, в которую включены неопределенные значения, то она приобретает определенную “интеллектуальность”. При использовании типов неопределенности данных необходимо для каждого типа неопределенности задавать логику, с помощью которой будет происходить обработка этих значений.
Задача представления неопределенных типов данных, а точнее включения неопределенных данных в известные модели данных и знаний, и адаптация традиционных алгоритмов операций над данными к фактору неопределенности является слабо формализованной задачей. Это относится и к задаче поддержки целостности БД, содержащих неопределенные данные. Решение этой задачи позволит в полной мере использовать неопределенный тип данных в схеме современных систем обработки данных.
Упомянутая выше «интеллектуальная» обработка характерна для информационной системы по комплексному исследованию археологических памятников – грунтовых и курганных могильников, специфика предметной области которой описана ниже. Приводимые в данной работе результаты исследований предназначены в первую очередь для использования и апробации в данной системе.
Целью настоящей работы является анализ известных типов неопределенности данных, представленных в виде упомянутого выше дерева [10], и формирование алгоритмического представления операций сравнения полей кортежей и их типов неопределенности при выполнении операций реляционной алгебры. Проводится группировка типов неопределенных значений в зависимости от практической реализации. По результатам анализа специфики предметной области разрабатываемой информационной системы выделяются и обосновываются четыре типа неопределенности, предназначенные для практической реализации.

1. Классификация неопределенных типов данных
Наиболее полным с точки зрения учета всех типов неопределенности является дерево неопределенных значений (рис.1), достаточно подробно описанное М.Ш. Цаленко [10]. Этим деревом представлены различные системные причины неполноты информации. Всего дерево содержит двадцать две вершины, одиннадцать из которых (вершины wi ) являются его листами.
Левая ветвь такого дерева (вершины 2, 4, 5) отображает ситуации отсутствия рассматриваемого свойства у объекта БД. Правая же часть дерева (вершины 3, 6ё22) описывает различные системные ситуации, которые могут вызвать в ответ на запрос пользователя неопределенное значение. Все неопределенные значения, лежащие ниже вершины 8, отражают специфику работы информационной системы: сдвиг по времени между появлением информации во внешнем мире и ее отражением в БД, регламентацию доступа к БД, время, необходимое на осуществление поиска данных и их обработку т.п.
С точки зрения операций реляционной алгебры (РА) целесообразно оперировать группами неопределенных значений, в то время как оценка конкретного типа неопределенности каждой группы должна осуществляться на этапе интерпретации результата выполнения запроса к БД. В связи с этим допущением на всем множестве неопределенных значений естественным образом выделяется семь групп, включающих только листовые вершины исходного дерева:
1 – свойство не присуще объекту (w1, w2);
2 – значение в БД не внесено, т.е. поле БД не заполнено (w5);
3 – значение временно недоступно, идут изменения в БД (w7, w8);
4 – на поле кортежа стоит запрет доступа (w6);
5 – значение доступно только для чтения, т.е. пользователю данные доступны только для просмотра, а изменять значения запрещено (w9);
6 – значение искажено (w10);
7 – истинность значения сомнительна (w11).
В данном случае типы неопределенности w3 и w4 не рассматриваются, поскольку считается, что схема БД уже полностью определена.
Тип данных для каждого поля кортежа или для всего кортежа может устанавливаться как администратором БД, так и автоматически на основе условий ограничения целостности или в процессе формирования результирующего отношения по некоторым правилам. Условия того, какой компонент СУБД может устанавливать и изменять конкретный тип неопределенных значений, должны быть определены на этапе проектирования СУБД для корректной поддержки целостности БД и не противоречивости самих данных. В таблице 1 определено, кто может устанавливать или изменять тип данных: администратор БД (А), система управления посредством проверки условий ограничения целостности (С) или система обработки на этапе выполнения запроса к базе данных (О).
Исходя из семи групп типов неопределенных значений (плюс традиционных тип определенных значений - тип 0, означающий, что значение определено и является истинным), общее число их сочетаний, которые могут встретиться при выполнении операций РА, равно 64. Однако типы данных групп 3 (w7, w8) и 4 (w6) обрабатываются в устройствах чтения/записи массовой памяти и не выдаются на устройства дальнейшей обработки, поэтому число сочетаний типов данных, вошедших в анализ, сокращается до 36.
Для рассмотрения специфики обработки неопределенных значений были взяты все одиннадцать операций РА, а именно унарные операции проекции и селекции и бинарные операции объединения, пересечения, разности, естественного соединения, соединения по условию, композиции, полусоединения, деления и декартового произведения. Операция эквисоединения рассматривалась как частный случай соединения по условию.
Для бинарных операций оба операнда могут иметь неопределенные значения. При строгом определении для унарных операций характерна обработка только одного операнда, поэтому рассматривать все сочетания неопределенных значений нет необходимости. Это утверждение справедливо только для операции проекции без удаления дублей. Для операции селекции условие селекции может быть получено из другого отношения, а не взято непосредственно из запроса к БД, поэтому появление в условии селекции неопределенных значений не исключено. В связи с этим операция селекции рассматривается как бинарная операция с точки зрения неопределенных значений.

2. Анализ признаков выполнения операций реляционной алгебры при обработке неопределенных значений
В ходе анализа операций РА с точки зрения обработки неопределенных значений для каждой обозначенной выше операции были построены таблицы (карты) признаков неопределенности результата (рис. 2), получаемого после выполнения операции РА. Таблицы не строились для операции проекции без удаления дублей и операции декартового произведения, поскольку при выполнении обеих операций анализ конкретных полей кортежей не производится. Операция удаления дублирующих кортежей рассматривалась отдельно. Таким образом, было построено одиннадцать таблиц признаков. При учете идентичности схемы вырабатывания признаков для некоторых операций итоговое число таблиц сокращается до семи (рис. 2).
Таблицы признаков неопределенности результата отражают все сочетания включенных в анализ типов неопределенных значений для отдельных операций РА. Под признаком неопределенности здесь понимается некоторый признак, указывающий на «истинность», «ложность», «противоречивость» и т.д. значения поля кортежа, полученного при выполнении операции РА. Признак неопределенности должен вырабатываться в процессе обработки запроса к БД (см. табл. 1) и влиять на интерпретацию полученного результата. В случае если результирующее отношение должно быть записано в оперативную или массовую память СУБД, то по полученным признакам неопределенности система обработки присваивает полям результирующих кортежей соответствующий тип неопределенных значений согласно рассмотренному выше дереву (рис. 1).
Таблица (карта) признаков неопределенности представляет собой матрицу, в первом столбце (заголовке) которой указаны признаки неопределенности первого операнда отношения R, а в первой строке (заголовке) – второго операнда отношения S. Под операндом понимается текущее проверяемое поле кортежа отношения-операнда (например, rij – значение поля j-го атрибута i-го кортежа отношения R). В ячейках матрицы записывается признак, который должно формировать устройство обработки при данном сочетании типов неопределенности операндов.
Для идентификации различных ситуаций приняты следующие условные обозначения:
· не закрашенная ячейка означает установку признака истинности операции (соответствующее поле кортежа включается в результирующее отношение);
· закрашенная ячейка означает установку признака ложности операции (соответствующее поле кортежа не включается в результирующее отношение);
· обрамление ячейки жирной линией означает проверку на условие не только признаков, но и самих данных;
· значение 7 означает установку (изменение) системой обработки первоначального признака неопределенности на признак 7 «истинность значения сомнительна»;
· символ означает установку признака истинности операции при поиске не по значению полей, а по их типу.
Последнее используется для операции селекции, например, когда необходимо найти все кортежи с незаполненными полями (характерно для оператора is-unk языка запросов к БД SQL).
Для всех рассмотренных операций, кроме операций селекции и соединения по условию, типы неопределенности и поля кортежей операндов проверяются на условие равенства значений. При выполнении операции соединения по условию и операции селекции условие сравнения значений полей кортежей-операндов могут быть любыми (>, <, і, Ј и т.п.).
Если условие сравнения выполняется, то формируется логическая единица, означающая положительный признак операции сравнения значений полей двух отношений-операндов. В противном случае формируется логический нуль. Включение всего проверяемого кортежа в результирующее отношение зависит от результатов сравнения всех его полей.
Кроме того, при выполнении условия поиска полю, потенциально входящему в результирующее отношение, должен быть присвоен какой-либо признак неопределенности. В таблицах на рис. 2 это проиллюстрировано записью в соответствующей клетке номера присваиваемого признака (0-2, 5-7). Как правило, этот признак берется от значения поля одного из операндов. Согласно специфике выполнения операций РА [3, 8, 9] практически для всех операций РА (пересечение, разность, удаление дублей, селекция, естественное соединение, полусоединение, деление) в результирующее отношение включаются поля первого отношения-операнда R. При выполнении операции объединения после проверки значения полей на равенство в результирующее отношение включаются поля второго операнда S. При выполнении операций соединения по условию и эквисоединения в результирующее отношение включаются поля обоих отношений-операндов, а для операции композиции поля сравнения обоих отношений не включаются в результирующее отношение.
Для некоторых сочетаний неопределенных значений при выполнении восьми операций РА (объединение, пересечение, разность, удаление дублей, селекция, естественное соединение, полусоединение, деление) система обработки должна поменять существующий признак неопределенности для поля, которое потенциально должно быть включено в результирующее отношение, изменив его на признак «истинность значения сомнительна» (7). Для отображения таких ситуаций в таблицах на рис. 2 принято условное обозначение «7».
При анализе составленных таблиц можно видеть, что все операции РА по схожести схем анализа признаков неопределенности операндов разделяются на четыре группы, в которые вошли следующие операции:
1) объединение (рис. 2, а), разность, удаление дублей (рис. 2, в);
2) пересечение (рис. 2, б), селекция (рис. 2, г);
3) соединение по условию, эквисоединение (рис. 2, д), естественное соединение, полусоединение, деление (рис. 2, е);
4) композиция (рис. 2, ж).
Различие выполнения операций в рамках выделенных групп заключается в основном лишь в том, какой признак неопределенности система обработки должна присвоить полю, потенциально входящему в результирующее отношение.
При выполнении операции селекции для комбинации признаков «7-7» возможно два варианта проверки (см. рис. 2, г). Если требуется найти все значения, истинность которых сомнительна, то в данном случае проверяется только признак соответствующего поля кортежа. В случае нахождения искомого, данное поле считается потенциально входящим в результирующее отношение и для него берется признак неопределенности поля-операнда «7». Если же выполняется типичная операция фильтрации кортежей по какому-либо условию селекции, то кроме этого проверяется еще и само значение поля на удовлетворение условию поиска.
В таблице для операций соединения по условию и эквисоединения (см. рис. 2, д) типы неопределенности полей, потенциально входящих в результирующее отношение, не проставлены, поскольку оба поля сравнения включаются в результат и их начальные признаки сохраняются.
При выполнении операции композиции оба атрибута сравнения не включаются в результирующее отношение, поэтому следует исключить все «сомнительные» комбинации признаков неопределенности. В противном случае при интерпретации результата для случаев сравнения полей, истинность которых сомнительна или значение которых искажено, невозможно определить реальную картину, так как оба атрибута сравнения из результата будут исключены. По этой же причине признаки неопределенности полей результата в таблице не проставляются (см. рис. 2, ж).
В таблицы 2.1 и 2.2 сведено алгоритмическое представление операций сравнения полей кортежей и их типов неопределенности при выполнении рассматриваемых операций РА. Эту таблицу можно считать таблицей истинности для указанных операций, на основе которой и были получены таблицы формирования признаков результата операций РА с учетом обработки неопределенных значений (рис. 2).
С точки зрения обработки неопределенных типов данных было пересмотрено формальное представление операций реляционной алгебры, данное в [9]. Адаптация алгоритмов выполнения этих операций заключается в том, что в процессе обработки анализируется тип неопределенности операндов и в зависимости от этого не только формируется признак истинности или ложности операции, но и формируется признак неопределенности для отдельного поля кортежа результирующего отношения.
В работе [1] дано формальное представление всех одиннадцати перечисленных операций реляционной алгебры и дополнительно операции удаления дублирующих кортежей.

3. Анализ типов неопределенности для информационной системы по комплексному исследованию могильников
Какие неопределенные значения будет поддерживать та или иная информационная система зависит в первую очередь от специфики предметной области, для которой строится данная система, и от круга задач, для решения которых она предназначена.
В данной работе в качестве одной из задач ставится выбор неопределенных значений, обработка которых будет реализована в создаваемой информационной системе по комплексному исследованию грунтовых и курганных могильников (ниже системе). Предметная область для создаваемой системы описывает археологические памятники, а именно грунтовые и курганные могильники, объекты памятников и находки, полученные в ходе раскопок. База данных системы пополняется как из материалов, полученных в ходе раскопок, проводимых в настоящее время, периодичность которых зависит от полевых сезонов, так и из материалов раскопок предыдущих 50-60 лет, хранящихся в археологических фондах. Различная степень сохранности материала, изменение со временем методик проведения раскопок и методик обработки материала во многом способствует необходимости использования в данной информационной системе неопределенных значений.
Ниже приведено обоснование выбора четырех из одиннадцати типов неопределенных данных wi, являющихся листовыми в рассмотренном ранее дереве неопределенных значений (рис. 1).
Неопределенное значение w1 «свойство не присуще объекту не зависимо от времени» (и никогда не будет получено) характерно для рассматриваемой предметной области по следующим причинам.
1. В систему могут заноситься данные о ранее освоенных памятниках, которые оценивались не по всем параметрам, используемым в настоящее время. За последние годы предложено использовать больше критериев для анализа полученного археологического материала и отсутствующее свойство «старого» памятника уже никогда не может быть получено. Например, в отчете о раскопках есть описание предмета, есть его фотография, а сам предмет был со временем утерян или разрушился полностью, поэтому определить для этого предмета некоторые новые свойства не представляется возможным.
2. Сохранность найденных в раскопе вещей зачастую является достаточно плохим. Особенно это характерно для более ранних эпох. В связи с этим какое-либо свойство объекта может отсутствовать по причине того, что оно просто не сохранилось. Такие данные у объекта, заносимого в БД, уже никогда не могут быть получены. Например,

Таблица 2.1
Алгоритмическое представление операций сравнения полей кортежей и их типов неопределенности при выполнении операций РА

1. Алгоритмы операций реляционной алгебры с учетом неопределенных типов данных /Васяева Е.С.// Тр. науч. конф. по итогам н.-и. работ Мар. гос. техн. ун-та. Йошкар-Ола, 19-23 марта, 2001. Секц. информ. методы, технологии и системы/ Мар. гос. техн. ун-т. - Йошкар-Ола, 2001. - C. 2-13. - Библиогр.: 9 назв. - Рус. - Деп. в ВИНИТИ 11.02.02 № 277-В2002.
2. Дейт К. Дж. Руководство по реляционной СУБД DB2. - М.: Финансы и статистика, 1988. - 320 с.
3. Дейт К.Дж. Введение в системы баз данных.- К: Диалектика, 1998.- 670 с.
4. Зиндер Е.З. Проектирование баз данных: новые требования, новые подходы// СУБД.- 1996.- №3.- с.10-22.
5. Использование поразрядного отображения при реализации бинарных операций реляционной алгебры/ Васяева Е.С.; Марийск. государ. техн. унив.- Йошкар-Ола, 1998.- 8 с. Библиогр.: 4 назв. - Рус. - Деп. в ВИНИТИ 15.04.98 № 1132-В98.
6. Калиниченко Л.А., Рывкин В.М. Машины баз данных и знаний. М.: Наука. Гл. ред. физ.-мат. лит., 1990. – 226 с.
7. Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики. СУБД, № 1, 1996.
8. Ульман Дж. Основы систем баз данных. - М.: Финансы и статистика, 1983. - 334 с.
9. Формальное представление операций реляционной алгебры, ориентированное на аппаратурную реализацию/ Васяева Е.С., Васяева Н.С., Власов А.А.; Марийск. политехн. институт.- Йошкар-Ола, 1995.- 8 с. Библиогр.: 4 назв.- Рус.- Деп. в ВИНИТИ 12.07.95, № 2144-В95.
10. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука. Гл. ред. физ-мат. лит., 1989. - 288 с. - (Проблемы искусственного интеллекта).


Материал взят с сайта www.abitu.ru