close

Вход

Забыли?

вход по аккаунту

?

Теоретические основы многоальтернативных систем управления базами данных в условиях неполноты информации

код для вставкиСкачать
На правах рукописи
АЧКАСОВ Александр Владимирович
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МНОГОАЛЬТЕРНАТИВНЫХ
СИСТЕМ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ В УСЛОВИЯХ
НЕПОЛНОТЫ ИНФОРМАЦИИ
Специальность: 05.13.11 – Математическое и программное
обеспечение вычислительных машин,
комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
доктора технических наук
Воронеж–2016
Работа выполнена в ФГБОУ ВО «Воронежский государственный технический университет»
Научный консультант:
Подвальный Семен Леонидович,
заслуженный деятель науки Российской Федерации,
доктор технических наук, профессор
Официальные оппоненты: Бутакова Мария Александровна,
доктор технических наук, профессор, ФГБОУ ВО
«Ростовский государственный университет путей
сообщения», декан факультета «Информационные
технологии управления», профессор кафедры «Информатика»;
Никульчев Евгений Витальевич,
доктор технических наук, профессор, ФГБОУ ВО
«Московский государственный университет технологий и управления им. К.Г. Разумовского (ПКУ)»,
проректор по научной работе и информатизации;
Соснин Петр Иванович,
доктор технических наук, профессор, ФГБОУ ВО
«Ульяновский государственный технический университет», зав. кафедрой «Вычислительная техника»
Ведущая организация:
ФГБОУ ВО «Липецкий государственный технический университет»
Защита диссертации состоится «05» декабря 2016 г. в 11.00 на заседании
диссертационного совета Д 212.037.01 при Воронежском государственном техническом университете по адресу: 394026, г. Воронеж, Московский просп., 14.
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВО «Воронежский государственный технический университет» и на сайте www.vorstu.ru.
Автореферат разослан «02» сентября 2016 г.
Ученый секретарь
диссертационного совета
Барабанов Владимир Федорович
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
Практическое применение методов управления распределенными базами данных приобретает всё большую популярность, их исследованию
посвящено большое количество работ. Многообразие методов и способов
их описания порождает проблему исследования поведения таких систем и
различных запросов, как в части типизации, так и масштаба.
Изучение неполноты и неопределённости информации в БД уже давно интересует разработчиков БД. В последнее время наблюдается рост интереса к этой проблеме, вызванный потребностью в обработке обширных
массивов данных, часто неполных и содержащих неопределённости, сформированных при обработке научных и сенсорных данных, фильтрации и
извлечении данных и т.п.
В настоящее время широкое распространение получили так называемые вероятностные подходы к управлению базами данных, достоверность и полнота информации в которых неабсолютны. В результате и запросы к БД, и отношения получили некую степень неопределённости, результаты запроса оказываются не единственными, и возникает задача выбора из множества результатов нескольких наиболее адекватных для дальнейшего их исследования.
Стандартная семантика, используемая в большинстве работ – это семантика возможных миров. Проблема «k лучших» запросов была всесторонне изучена в рамках мультимедийных баз данных, межплатформенных
систем, фильтрации данных, базовых технологий в темпоральных базах
данных и т.д. В проблеме «k лучших» запросов каждому кортежу присваивается оценка, и пользователям требуется k кортежей с наивысшими оценками. Таким образом, СУБД становятся многоальтернативными, и проблема максимально точной оценки альтернатив выступает на первый план.
В последнее время проблему «k лучших» запросов изучали в рамках
вероятностных баз данных. Однако, в сущности, эти работы решают две
различных в корне проблемы «k лучших» запросов. В ряде работ предполагается наличие оценочной функции для сортировки кортежей. Данные о
вероятностях дают понять, насколько вероятно появление кортежей в базе
данных. Напротив, в других работах критерий оценки в запросе «k лучших» – это вероятность, соответствующая каждому ответу на запрос. Однако во многих приложениях необходимо иметь дело одновременно и с
вероятностью, и с оценкой кортежа.
Таким образом, актуальной является задача создания теоретических
основ многоальтернативных систем управления базами данных в условиях
неполноты информации, а также разработка и практическое применение
алгоритмического и программного обеспечения, реализующего новые или
модифицированные семантики вероятностного многоальтернативного вы-
2
бора СУБД.
Диссертационная работа выполнена в рамках основного научного
направления Воронежского государственного технического университета
«Вычислительные комплексы и проблемно-ориентированные системы
управления».
Цель работы заключается в создании основ многоальтернативных
систем управления базами данных в условиях неполноты информации, а
также разработки и практического применения алгоритмического и программного обеспечения, реализующего новые или модифицированные семантики вероятностного многоальтернативного выбора СУБД.
Для достижения поставленной цели в диссертационной работе сформулированы следующие задачи:
- ввести и обосновать новую семантику «k лучших всюду» для многоальтернативных запросов типа «k лучших» в вероятностных базах данных;
- разработать алгоритмы оценки «k лучших» запросов на основе инъективных оценочных функций с использованием семантики «k лучших
всюду» в простых и общих вероятностных базах данных;
- ввести и обосновать понятие вынужденного событийного отношения для последующей редукции семантики «k лучших всюду» от общего
случая до «k лучших всюду» для простых вероятностных отношений;
- создать обобщение семантики «k лучших всюду» для обычных
функций оценок выборки при использовании равной политики распределения;
- предложить концепцию полностью динамической структуры данных для эффективного функционирования «k-лучших» запросов в вероятностных базах данных управления системами специального назначения,
связанную с рейтингом кортежей, у которых есть и оценка, и вероятность
для каждого кортежа;
- разработать алгоритм поиска приблизительных наборов «k лучших» для заранее неизвестного содержания отношений, основанный на
доступе к обучающей информации;
- осуществить проектирование и разработку специального проблемно-ориентированного программного обеспечения, обеспечивающего интеграцию с широким кругом систем принятия решений и сопровождения
жизненного цикла.
Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы методы математического моделирования, оптимизации, теории вероятностей и математической статистики, технологии объектно-ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.11: п. 4 «Системы управления базами данных и знаний»;
3
п.9 «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
- новая семантика «k лучших всюду» для многоальтернативных запросов типа «k лучших» в вероятностных базах данных, основанная на постулатах точности, корректности и стабильности, которая возвращает k
наиболее высоко оцененных кортежей согласно их вероятности оказаться в
«k лучших» ответах из возможных слов;
- алгоритмы оценки «k лучших» запросов на основе инъективных
оценочных функций с использованием семантики «k лучших всюду» в
простых и общих вероятностных базах данных, обеспечивающие полиномиальность по времени;
- понятие вынужденного событийного отношения, отличающееся
использованием инъективной оценочной функции и одноатрибутного
вспомогательного отношения, обеспечивающее редукцию семантики «k
лучших всюду» от общего случая до «k лучших всюду» для простых вероятностных отношений;
- обобщение семантики «k лучших всюду» для обычных функций
оценок, отличающееся использованием нового понятия «политика распределения» и обеспечивающее построение алгоритма, основанного на динамическом программировании, для оценки выборки при использовании
равной политики распределения;
- концепция полностью динамической структуры данных для эффективного функционирования «k-лучших» запросов в вероятностных базах
данных управления системами специального назначения, связанная с рейтингом кортежей, у которых есть и оценка, и вероятность для каждого кортежа, которая может извлекать «k-лучших» кортежей за время O(k log N )
и получать обновления с оценкой O(log N ) ;
- двухпараметрический алгоритм для поиска приблизительных наборов «k лучших» для заранее неизвестного содержания отношений, основанный на доступе к обучающей информации из того же распределения,
что и скрытое отношение, и обеспечивающий оценку вероятности того,
что полная оценка элемента будет достаточно высокой, чтобы войти в текущий набор «k лучших»;
- доказательство существования структур данных, решающих проблему поиска «k лучших» документов: размером O (n ) в модели оперативной памяти – с трудоёмкостью O (k ) ; в модели внешней памяти размером
O (nh ) , h ≤ log * n – с трудоёмкостью O ( p/B + log Bn + log (h) n + k/B ) операций
ввода/вывода;
- структура специального проблемно-ориентированного программного обеспечения, содержащая интегрированные модули контроля, кор-
4
рекции, верификации и визуализации модели транслируемых данных, отличающаяся интеграцией с широким кругом систем принятия решений и
сопровождения жизненного цикла;
- структура специального программного обеспечения, позволяющего
определить правильность выбора элементной базы, оценить характеристики сбоеустойчивости бортовой аппаратуры космических аппаратов и комплектующих при воздействии отдельных тяжёлых заряженных частиц и
высокоэнергетичных протонов космического пространства.
Практическая значимость заключается в создании специализированного программного обеспечения на основе предложенных структурных
и функциональных схем с использованием концепции бесшовной интеграции с системами поддержки, планирования и сопровождения жизненного
цикла и ориентацией на сохранение функциональной целостности четырёхуровневой модели клиент-серверной архитектуры развёртывания данных решений при производстве изделий специального назначения.
Программное обеспечение представляет собой серию специализированных программных межмодульных интерфейсов, которые позволят интегрировать не все модули из решения поддержки жизненного цикла, а
внедрять только необходимую часть, обеспечив корректное функционирование с уже установленным программным обеспечением. Предложенные
средства направлены на обеспечение взаимодействия как систем планирования, сопровождения, поддержки, так и решений управления жизненного
цикла продукции.
Реализация и внедрение результатов работы. Результаты исследований используются в акционерном обществе "Сигнальные микросистемы"
(г. Воронеж), акционерном обществе "Воронежский Завод Полупроводниковых Приборов - Сборка", открытом акционерном обществе "Научноисследовательский институт электронной техники" (г. Воронеж), акционерном обществе "Научно-исследовательский институт полупроводникового машиностроения" (г. Воронеж) при разработке и сопровождении программного обеспечения изделий электронной техники специального назначения.
Основные результаты работы внедрены в учебный процесс Воронежского государственного технического университета в рамках дисциплин:
«Вычислительные машины, системы и сети», «Базы данных», при выполнении курсового и дипломного проектирования.
Апробация работы. Основные положения диссертационной работы
докладывались и обсуждались на следующих конференциях: I РоссийскоБелорусской конференции «Элементная база отечественной радиоэлектроники» (Минск, 2013); международной научно-практической конференции
«Актуальные направления научных исследований XXI века: теория и
практика» (2013); XX и XXI Международной открытой научной конференции «Modern informatization problems in economics and safety» (Yelm,
5
WA, USA, January 2015, 2016); Международной летней и зимней научных
школах «Парадигма» (Варна, Болгария, 2015, 2016); XXI Международной
открытой научной конференции «Modern informatization problems in the
technological and telecommunication systems analysis and synthesis» (Yelm,
WA, USA, January 2016), а также на конференциях профессорскопреподавательского состава Воронежского государственного технического
университета (Воронеж, 2012-2016).
Публикации. По теме диссертационного исследования опубликовано 52 печатные работы, из них 24 статьи в изданиях, рекомендованных
ВАК РФ, патент, 6 свидетельств о регистрации программы для ЭВМ, 21
статья в журналах и материалах Международных и Всероссийских конференций и форумов. В работах, опубликованных в соавторстве и приведённых в конце автореферата, лично соискателю принадлежат: семантика «k
лучших всюду» для многоальтернативных запросов типа «k лучших» в вероятностных базах данных, основанная на постулатах точности, корректности и стабильности [23, 39, 49]; алгоритмы оценки «k лучших» запросов
на основе инъективных оценочных функций с использованием семантики
«k лучших всюду» в простых и общих вероятностных базах данных [37,
41, 43]; понятие вынужденного событийного отношения, отличающееся
использованием инъективной оценочной функции и одноатрибутного
вспомогательного отношения [9, 50, 52]; обобщение семантики «k лучших
всюду» для обычных функций оценок, отличающееся использованием нового понятия «политика распределения» [18, 40, 45]; концепция полностью
динамической структуры данных для эффективного функционирования «kлучших» запросов в вероятностных базах данных управления системами
специального назначения, связанная с рейтингом кортежей, у которых есть
и оценка, и вероятность для каждого кортежа [8, 21, 24]; теоретические и
практические результаты в области полиномиальных оценок и связанных с
ними преобразований [1, 6, 11, 17, 25]; структура специального проблемноориентированного программного обеспечения, отличающаяся интеграцией
с широким кругом систем принятия решений и сопровождения жизненного
цикла [2, 3, 13, 14, 15, 19, 26, 27, 28, 31, 33, 36, 42, 44, 51]; компоненты
специального и математического программного обеспечения, предоставляющие и реализующие основные теоретические результаты исследования
[4, 5, 7, 10, 12, 16, 20, 22, 29, 30, 34, 35, 38, 47].
Структура и объём работы. Диссертационная работа состоит из
введения, пяти глав, заключения. Работа содержит 285 страниц. Список
использованной литературы включает 290 наименований.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность работы, научная новизна,
практическая значимость, сформулированы цель и задачи исследования.
6
В первой главе рассмотрена предметная область и известный к
настоящему времени в научной литературе научно-методический аппарат
анализа вероятностных баз данных и инструментов их проектирования и
сопровождения. Обоснована актуальность работы, сформулирована цель
исследования, задачи, совокупность которых приводит к достижению
поставленной цели. Дизайн исследования представлен на рис. 1.1.
Рис. 1.1. Дизайн исследования
7
Во второй главе рассматривается специфика исследования мультивариантных запросов и отношений в условиях неполноты информации как
основа теории многоальтернативных систем управления БД.
Определение 2.1 (Вероятностное отношение). Вероятностное отношение R p – это тройка (R, p, C), где R является вспомогательным детерминистским отношением, p – вероятностная функция, p : R → (0,1] и C
– раздел R, такой что ∀ С i ∈C, ∑ t∈Ci p(t) ≤1 .
Определение 2.2 (Простое вероятностное отношение). Вероятностное отношение R p = (R, p, C) является простым, если раздел C содержит только единичное множество.
Определение 2.3 (Возможный мир). Дано вероятностное отношение R p = (R, p, C) , детерминистское отношение W – возможный мир R p ,
если:
1 W – это подмножество вспомогательного отношения, т.е. W ⊆ R ;
2 Для каждого подмножества в разделе C не более одного кортежа
из C i находится в W, т.е. ∀ C i ∈C, C i ∩ W ≤1 ;
3 Вероятность того, что W (определяемое соотношением (1)) больше нуля, т.е., Pr (W ) > 0 , определяется как
Pr (W ) = ∏t∈W p(t )∏Ci ∈C' (1− ∑ t ∈Ci p(t ))
(2.1)
где C' = {C i ∈C W ∩ C i = o/ }.
Обозначим через pwd (R p ) множество всех возможных миров R p .
Определение 2.4 (Набор ответов «k лучших» при использовании
Детерминистского Отношения). Пусть дано детерминистское отношение R, неотрицательное число k и функция оценки s для R, тогда набор
ответов для «k лучших» запросов при использовании R есть набор кортежей T, которые отвечают условиям:
1. T ⊆ R ;
2. Если R < k, T = R , в обратном случае T = k ;
3. ∀ t ∈T ∀ t'∈R − T. t f s t' or t ~ s t' .
На основании данных определений сформируем семантику для «k
лучших» запросов. Ответом для «k лучших» запросов служит вероятностное отношение Rp = (R, p, C) , которое должно быть набором кортежей, связанных с их вспомогательным отношением R. Сформулируем три требования, которые служат стандартом для категоризации различных семантик.
Введём обозначение: Ans k,s (R p ) – коллекция всех наборов ответов «k лучших» для вероятностного отношения R p и оценивающей функции s.
8
Требование Т1. Точное k: Когда R p достаточно велико ( C ≥ k ), размер каждого набора ответов S «k лучших» запросов равен k;
C ≥ k ⇒ ∀S ∈ Ansk,s ( R p ) : S = k  .
Требование Т2. Истинность: Для каждого набора ответов S «k лучших» запросов и любых двух кортежей t 1 , t 2 ∈R , если оценка и вероятность для t 1 больше, чем они же для t 2 и t 2 ∈S , тогда
t 1 ∈S ;
∀S∈Ans k,s (R p )∀ t 1 , t 2 ∈R.s (t 1 ) > s (t 2 ) ∧ p (t 1 ) > p (t 2 ) ∧ t 2 ∈S ⇒ t 1 ∈S .
Динамический постулат:
∪ Ans k,s (R p ) обозначает объединение всех наборов ответов «k лучших» запросов при R p = (R, p, C) и функции оценки s. Для любого t∈R t –
выигравший, если t ∈∪ Ans k,s (R p ), и t – проигравший, если
t ∈R - ∪ Ans k,s (R p ) .)
Требование Т3. Стабильность: Повышение оценки/вероятности
победителя не превратит его в проигравшего.
Пусть оценочная функция s' такая, что s' (t ) > s (t ) и для каждого
t'∈R - {t}, s' (t') = s (t') , тогда t ∈∪ Ans k,s (R p )⇒ t ∈∪ Ans k,s' (R p ).
Пусть вероятность p' такая, что p' (t ) > p (t ) и
t'∈R - {t}, p' (t') = p (t') ,
тогда
для каждого
t ∈∪ Ans k,s (R p )⇒ t ∈∪ Ans k,s (R p )' ) ,
где
(R p ) ' = (R, p' , C) .
Понижение оценки проигравшего не превратит его в победителя.
Пусть оценочная функция s' такая, что s' (t ) < s (t ) и для каждого
t'∈R - {t}, s' (t') = s (t') , тогда t ∈R - ∪ Ans k,s (R p )⇒ t ∈R - ∪ Ans k,s' (R p ) .
Пусть вероятность p' такая, что p' (t ) < p (t ) и для каждого
t'∈R - {t}, p' (t') = p (t') , тогда t ∈R - ∪ Ans k,s (R p )⇒ t ∈R - ∪ Ans k,s ( (R p )' ) , где
(R p ) ' = (R, p' , C) .
На основании трех семантических требований, которые используются для анализа и категоризации различных «k лучших» семантик в вероятностных базах данных, разработаем новые семантики ответов для «k лучших» запросов в вероятностных отношениях, которые назовем «k лучших
всюду». Данный ответ возвращает k наиболее высоко оцененных кортежей
согласно их вероятности оказаться в «k лучших» (k первых) ответов из
возможных слов. Новая семантика будет базироваться на следующих двух
определениях.
Определение 2.5 (Вероятность «k лучших всюду»). Пусть есть вероятностное отношение R p = (R, p, C) , неотрицательное число k и инъек-
9
тивная оценочная функция s для R p . Для любого кортежа t в R вероятность «k лучших всюду» t обозначается как Pk,s
Rp
(t )
и равна сумме веро-
ятностей всех возможных миров отношения R p , набор ответов «k лучших» которых содержит t.
p
P R k, s (t ) = ∑ W ∈pwd (R p ) Pr (W )
(2.2)
t ∈ top k, s ( W )
Определение 2.6 (Набор ответов «k лучших всюду» для вероятностного отношения). Пусть R p = (R, p, C) – вероятностное отношение, k –
неотрицательное число и s – инъективная оценочная функция для R p , тогда набор ответов «k лучших всюду» для R p есть набор из T кортежей,
удовлетворяющих следующим условиям:
1) T ⊆ R ;
2) Если R < k, T = R , в противном случае T = k ;
3) ∀ t ∈T, ∀ t'∈R − T, Pk, s (t )≥ Pk, s (t') .
Таким образом, предложена новая семантика для «k лучших» запросов
в вероятностных базах данных, названная «k лучших всюду», которая в
большей степени удовлетворяет сформулированным требованиям.
Поскольку существует несколько подходов для определения «k лучших» семантик, далее ставится задача подбора наиболее подходящей из
них на основании правильной комбинации условий и их применении. В
частности:
• U-Topk: возвращает наиболее вероятные «k лучших» ответов, которые принадлежат к возможному слову;
• U-kRanks: для i =1, 2,K, k , возвращает наиболее вероятный i-й кортеж из всех возможных слов;
• PT-k возвращает каждый кортеж, вероятность присутствия которого
в «k лучших» ответов возможных слов как минимум pτ .
Требования Т1, Т2 и Т3 лежат в основе анализа различных семантик.
В табл. 2.1 “ ∨ ” показывает, что требование удовлетворяет данной семантике, “×” – не удовлетворяет. “ ∨ /×” – требование удовлетворяет данной
семантике в случае простых вероятностных отношений, но не в общем
случае.
Таблица 2.1. Требования, удовлетворяющие различным семантикам
Семантики
Точное k Корректность Стабильность
«k лучших всюду»
∨ /×
∨
∨
PT-k
×
∨ /×
∨
U-Topk
×
∨ /×
∨
U-kRanks
×
×
×
10
В результате создан табличный инструмент для выбора различных семантик. С его помощью пользователи могут подобрать наиболее подходящую семантику, основываясь на правильной комбинации условий и их
применении.
Следующим этапом является оценка «k лучших» запросов. В работе
доказано следующее утверждение.
Утверждение 2.1. Пусть дано простое вероятностное отношение
p
R = (R, p, C) и инъективная оценочная функция s для R p , когда
R = {t 1 , t 2 ,K, t n } и t 1 f s t 2 f sK f s t n , тогда верным будет следующее рекуррентное отношение запросов в семантике «k лучших всюду»:


k =0
0

(2.3)
q ( k,i ) = 
p ( ti )
1≤ i ≤ k

p ( ti −1 )
+ q ( k -1,i -1) p ( ti ) в противном случае
 q ( k,i -1)
p
t
(
)
i −1

Уравнение (2.3) лежит в основе двух алгоритмов, первый из которых
предназначен для оценки «k лучших всюду», а второй – для вычисления вероятности в семантике «k лучших всюду» с использованием простого вероятностного отношения в инъективной оценочной функции. Показано, что
алгоритмы являются полиномиальными (использованы технические результаты, связанные с полиномиальными преобразователями, в т.ч. патент).
Алгоритм 2.1.
Дано: R p = (R, p, C) , k
Цель: отсортировать кортежи в R по убыванию функции оценки s
1: Инициализируем выборку фиксированной мощности (k +1) - Ans из
(t, prob ) пар, которая сравнивает пары по их значению prob, т.е. вероятности «k лучших всюду» для t;
2: Вычисляем вероятности «k лучших всюду», используя Алгоритм 2.2, т.е.
q (0 K k,1K R ) = Ind_Topk_S ub (R p , k ) ;
3: for i =1 to R do
4:
Добавить (t i , q (k, i )) в Ans;
5:
if Ans > k then
6:
удалить пару с наименьшим значением prob из Ans;
7:
end if
8: end for
9: return {t i (t i , q (k, i ))∈ Ans};
Алгоритм 2.2.
Дано: R p = (R, p, C) , k
11
Цель: отсортировать кортежи в R по убыванию функции оценки s
1: q (0,1) = 0;
2: for k =1 to k do
3:
q (k' ,1) = p (t 1 );
4: end for
5: for i = 2 to R do
6:
for k'= 0 to k do
7:
if k'= 0 then
q (k' , i ) = 0
8:
9:
else
p (t )
10: q (k' , i ) = p (t )(q (k' , i - 1) i −1 + q (k' -1, i -1)) ;
p (t i −1 )
11: end if
12: end for
13: end for
14: return q (0K k,1K R )
Показано, что А1 – полиномиальный по сложности алгоритм оценки
«k лучших» запросов с использованием семантики «k лучших всюду» в
простых вероятностных базах данных с использованием инъективной оценочной функции.
Далее проведён теоретический пространственно-временной анализ
предложенных алгоритмов, в результате чего разработана следующая оптимизация базового алгоритма по времени.
Пороговый алгоритм
(1) Пройти по списку T и заполнить все поля в таблице ДП. В частности, для t = t j , просчитать записи в j-м столбце вплоть до k-й строки. Добавить t j к набору ответов Ans на запрос типа «k лучших» в случае, если
выполнено любое из следующих условий:
(а) У Ans менее чем k кортежей, то есть Ans < k ;
(б) Вероятность t j в семантике «k лучших всюду», она же q (k, j) ,
больше, чем нижний предел Ans, он же LB Ans , где LB Ans = min t i ∈Ansq (k, i ) .
Во втором случае также необходимо отбросить кортеж с наименьшей вероятностью по семантике «k лучших всюду».
(2) После того, как просмотрено не менее k кортежей в T, просматривается список P, чтобы найти первую p, чей кортеж t ещё не был найден.
Примем p = p , тогда можем использовать p , чтобы оценить порог, то есть
верхнюю границу (UP) вероятности любого ненайденного кортежа по семантике «k лучших всюду». Примем t = t i ,
12


p (t )
UP =  q (k, i ) i + q (k - 1, i ) p
p (t i )


(3) Если UP > LB Ans , Ans может измениться в будущем, поэтому возвращаемся к шагу (1). Иначе можно остановить алгоритм и выдать значение Ans.
Таким образом, на основании теоретического пространственновременного анализа разработаны эффективные эвристики, которые улучшают производительность базовых алгоритмов.
Поскольку в общем случае вероятностных отношений каждая часть
раздела C может содержать более одного кортежа, необходимо ввести некоторую функцию, которая будет однозначно идентифицировать часть
раздела, к которой принадлежит данный кортеж. Для этого введено следующее определение.
Определение 2.7 (Вынужденное событийное отношение). Пусть
дано вероятностное отношение R p = (R, p, C) , инъективная оценочная
функция s для R p и кортеж t ∈C id(t) ∈C , тогда отношение событий, по-
рожденное кортежем t и обозначенное как E p = (E, p E , C E ) , будет вероятностным отношением, чьё вспомогательное отношение E имеет только
один атрибут, событие Event. Отношение E и функция вероятностей p E
определены следующими двумя правилами:
− Правило 1: t e t ∈E и p E (t et )= p (t ) ;
− Правило 2: ∀ C i ∈C ∧ C i ≠ C id(t) .
(∃ t'∈C i ∧ t' f s t )⇒ (t eC ∈E )
i
и p E (t eC i )=
∑ p(t')
t'∈C i
t' f s t
Утверждение 2.2. Вынужденное событийное отношение является
простым вероятностным отношением.
С помощью вынужденных событийных отношений можно сузить «k
лучших всюду» от общего случая до «k лучших всюду» для простых вероятностных отношений.
Утверждение 2.3. Пусть R p = (R, p, C) – вероятностное отношение, s
– инъективная оценочная функция, t∈R , а E p = (E, p E , C E ) – отношение со-
( { }
{{ }})
бытий, порожденное t. Определим Q p = E - t et , p E , C E − t e t . Тогда вероятность t по «k лучших всюду» удовлетворяет следующим условиям:
p
Pk,Rs (t ) = p(t ) ∑ Pr (We )
(2.4)
( )
We ∈ pwd Q p
We < k
Таким образом, введено понятие вынужденного событийного отношения, отличающееся использованием инъективной оценочной функции и
одноатрибутного вспомогательного отношения, обеспечивающее редук-
13
цию семантики «k лучших всюду» от общего случая до «k лучших всюду»
для простых вероятностных отношений.
Третья глава посвящена оценке эффективности запросов для вероятностных отношений в СУБД. Первый раздел завершает теоретическую
оценку эффективности запросов для вероятностных отношений в СУБД.
Для этого определение 2.5 обобщено с применением обработки связей с
помощью политики распределения.
Определение 3.1 (Вероятность «k лучших всюду» для Обобщенной
Оценивающей Функции). Рассмотрим вероятностное отношение
R p = (R, p, C) , неотрицательное число k и оценивающую функцию s для R p .
Для любого кортежа t в R вероятность «k лучших всюду» кортежа t обозначается как P R (t ) и равна сумме вероятностей (частичных) всех возможных миров отношения R p , набор ответов «k лучших» содержит t.
Rp
Pk,s
( t ) = ∑ p α ( t, W )Pr ( W )
(3.1)
W∈pwd( R )
t∈all k,s ( W )
Определение 3.2 (Политика Равного Распределения). Пусть есть
вероятностное отношение R p = (R, p, C) , неотрицательное k и оценивающая функция s для R p . Тогда для возможного мира W ∈ pwd(R p ) и кортежа t ∈ W , пусть a = {t'∈ W t' f s t} и b = {t'∈ W t' ~ s t}
1, если a < k и a + b ≤ k

(3.2)
α (t, W ) =  k - a
<
+
>
,
если
a
k
и
a
b
k
 b
На основании этих двух определений предложен алгоритм для оценки выборки при использовании равной политики распределения.
Дано: R p = (R, p, C) , k
Необходимо: кортежи в R должны быть отсортированы не по возрастанию, а по оценочной функции s.
1: Инициализируем фиксированную (k+1) очередь из Ans of(t,prob) пар,
которые соотносятся c другими парами по вероятности (prob), т.е. вероятность «k лучших всюду» для t;
2: Возьмем таблицу DP для вычисления Tk',[i ] , k' = 0, K , k - 1 , i = 1, K , n - 1 ,
k'≤ i с помощью Алгоритма 2, т.е.
q(0K k,1K R ) = Ind_Topk_Sub(R p , k ) ;
3: for l=1 to R do
4:
m = jl − i l ;
5:
if m == 1 then
6:
Добавить (t l , q(k, l)) в Ans;
14
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
else
Возьмем таблицу DP для вычисления Pk - k'B ,s l (t l ) , т.е., Pl (k - k') ,
k' = 0, K , k - 1
q tie (0K m,1K m ) = Ind_Topk_Gen_Sub(R sp (t l )), t l , m) ;
for k' ' = 0 to m − 1 do
p
q (k' '+1, m ) − q tie (k' ' , m )
;
Tk'R',s[m( t -l 1)] = tie
p(t l )
end for
for k' ' = 1 to k do
m
 k'' p
k' ' R sp ( t l ) 
Pl (k' ') = p(t l ) ∑ Tj-R1,s [(mt l-)1] + ∑
Tj-1,[m -1]  ;
j
j
=
1
j
=
k'
'
+
1


end for
Rp
(t )
Pk, s (t l ) = 0;
for k'= 0 to k − 1 do
q (k'+1, i l + 1) − q (k' , i l + 1)
Tk',[i l ] =
;
p(t i l +1 )
Rp
Pk,s (t l ) = Pk,s (t l ) + Tk',[i l ]Pl (k - k') ;
18:
19:
end for
20:
Добавить (t l , P R (t l )) в Ans;
21: end if
22: if Ans > k then
23:
удалить пару с наименьшим значением prob из Ans;
24: end if
25: end for
26: return {t i (t i , prob ) ∈ Ans};
Rp
Rp
Таким образом, обобщена семантика «k лучших всюду» для обычной
оценочной функции, отличающаяся использованием нового понятия «политика распределения» и обеспечивающая построение алгоритма, основанного на динамическом программировании, для оценки выборки при использовании равной политики распределения.
Непосредственно связанной с этой задачей является задача эффективного функционирования «k лучших» запросов в вероятностных базах
данных путём определения рейтинга кортежа. Учитывая неопределённость
отношений T динамической коллекции кортежей, таких, что каждый кортеж t i ∈ T связан с вероятностью членства значения Pr (t i ) > 0 , и оценку
рейтинга score(t i ) , определим следующую оценочную функцию:
15
ψ (t i ) = ∑ α r -1 × Pr (t i , r ) .
(3.3)
r
где α является константой и Pr (t i , r ) обозначает вероятность кортежа t i
занять позиции r во всех возможных мирах * (* Pr ( t i , r ) = 0, если r > i ).
Исследуем лучший запрос на Т, который формирует основу для
структуры данных. Пусть дано отношение T = {t 1 , t 2 ,K, t N }. Разобьём его
на группы подотношений Tl = {t 1 , t 2 ,K, t [N/2 ] } и Tr = {t [N/2 ]+1 , t [N/2 ]+ 2 ,K, t N }.
Кроме того, пусть t l и t r представляют лучший ответ на Tl и Tr с рангом e
ψ Tl (t l ) и ψ T r (t r ) соответственно, где ψ Tl (t l ) вычисляется только с учётом
t j ∈ Tl и ψ T r (t r ) вычисляется только с учётом t j ∈ Tr .
Для t i ∈ Tl , ψ T (t i ) = m i
l
∏ cj
j< i
t j∈Tl
и для t i ∈ Tr , ψ T (t i ) = m i
r
∏ cj .
j< i
t j∈Tr
После получения простой замкнутой формы выражения для расчёта
ψ (t i ) кортежа t i необходимо обеспечить поддержание динамической коллекции кортежей так, что для данного запроса k мы получаем «k лучших» в
смысле ранга кортежа. Будем использовать структурный подход для решения этой задачи. Структура представляет собой такое бинарное дерево поиска Δ, где каждый лист соответствует кортежу в неопределённом отношении Т. Листья на дереве отсортированы в порядке убывания оценки, т.е.
l 1 , l 2 ,K, l N дерева представляют кортежи t 1 , t 2 ,K, t N в том же порядке
слева направо, таким образом, score (t i ) > score (t i+1 ) . Пусть TU представляет собой подсвязь, содержащую кортежи, связанные с листьями поддерева
с корнем в узле u , т.е. TU = {t u' , t u'+1 ,K, t u'' }, l u' представляет самый левый
лист узла и l u'' представляет самый правый лист узла на каждый узел u ,
мы храним тройку (top u , M u , C u ) так, что:
• top u – кортеж (в листе l u* ) с самим высоким рангом среди кортежей из подотношения TU . Здесь u' ≤ u* ≤ u' ' .
• M u – вклад всех кортежей TU по отношению к рангу кортежа top u .
M u = m u* ∏ c i
u' ≤ i < u*
• C u является вкладом всех кортежей TU по отношению к кортежу
t i , так что i > u' ' , где l u'' является самым правым листом поддерева с корнем в узле u .
C u = ∏ ci
u' ≤ i < u''
Теорема 3.1. Структура данных Δ поддерживает динамические коллекции таких кортежей, что «1 лучший» кортеж, t 1 = top root и ψ (t 1 ) = M root .
16
Таким образом, при операции объединения «1 лучший» кортеж t 1
будет распространяться на корневой узел в top root , t 1 может быть извлечён
за конечное время. Для того, чтобы извлечь «2 лучших» кортеж t 2 , будем
использовать следующую стратегию. После получения t 1 положим
ψ (t 1 ) = 0 . В результате следующий ранг, набранный кортежем t 2 , будет
распространяться в top root вместо t 1 . Это может быть достигнуто путём
выполнения операции обновления листа на лист l j (лист, представляющий
текущую top root = t j ); с ним m j имеет нулевое значение, c j остается неизменным, операция обновления влияет только на вычисление ранг t j , оставляя ранг всех других кортежей в неизмененном виде. Повторяя ту же
процедуру, можно получить «k лучших» кортежей с высокими значениями
ранга.
Теорема 3.2. «k лучших» в смысле ранга кортежей могут быть получены за O(K log N ) время.
Теорема 3.3. Коллекция неопределённых данных может быть сохранена с помощью структуры динамических данных линейного размера, которые могут извлекать Тоp-K ранжированные кортежи за O(K log N ) время и поддерживать вставку или удаление кортежа t O(d log N ) раз, где d
является числом кортежей, которые связаны с t.
Таким образом, представлена концепция полностью динамической
структуры данных для эффективного функционирования «k лучших» запросов в вероятностных базах данных управления системами специального назначения, связанная с рейтингом кортежей, у которых есть и оценка, и
вероятность для каждого кортежа, которая может извлекать «k лучших»
кортежей за время O(k log N ) и получать обновления с оценкой O(log N ) .
Для оценки эффективности предлагаемой структуры данных проведена серия экспериментов. На вход подается синтетический набор данных,
содержащий 100 000 кортежей. Суммарная оценка в каждом кортеже выбирается случайно равномерно из [0,100000], и эта вероятность равномерно распределена в (0.5 × 10 -5 ,1.5 × 10 −5 ). Число кортежей, участвующих в
каждом х-кортеже, следует равномерно распределить на интервале (2,10).
Наряду с синтетическими наборами данных использованы данные открытой БД (http://nsidc.org/data/g00807).
Оценка производительности запросов структуры данных представлена на рис. 3.1.
На рис. 3.2 и 3.3 проиллюстрирована эффективность структуры данных в обработке кортежей вставок и удалений.
Таким образом, оценена эффективность предлагаемой структуры
данных по результатам экспериментов с использованием синтетических и
реальных данных.
17
Следующей задачей является оценка приблизительных «k лучших»
запросов в отношениях, в которых заранее неизвестны значения. Целью
является разработка алгоритма, который находит приближенный набор «k
лучших» значений с высокой точностью и с низкими затратами. Укрупнённая схема алгоритма представлена на рис. 3.4.
Рис. 3.1. Производительность «k лучших» запросов для реальных и
синтетических данных
Рис. 3.2. Обработка: затраты для реальных данных
Алгоритм использует параметр α , который определяет, когда оставшиеся значения в строке X i⋅ можно пропустить. Когда же
Pr (X i⋅ w T ≥ δ X i,1:h w 1:h ) < α , переходим к следующей строке. Наиболее
значимой частью алгоритма является метод оценки вероятности
T
18
Pr (X i⋅ w T > δ X i,1:h w 1:h ) .
T
(
)
Предлагаемый
метод
оценки
вероятности
Pr xw T > δ x 1:h w 1T:h заключается в следующем:
Рис. 3.3. Обработка: затраты для синтетического набора данных
Рис. 3.4. Укрупнённая схема алгоритма
1. Обучающие данные (матрица X , элементы которой известны); для
каждой строки вычисляется полная оценка и привязывается к оценкам
19
префиксов для каждой возможной длины префикса h . То есть для каждого
h вычисляется набор X h с помощью формулы:
X h = {(X i,1:h w 1T:h , X i⋅ w T )}i =1 .
2. Используя формулы
∑(a,b )∈X h K (a, s h )b
µ (s h ) =
∑(a,b )∈X h K (a, s h )
n
(3.4)
(3.5)
и
σ (s h ) =
∑(a,b )∈X K(a, s h )b
∑(a,b )∈X K(a, s h )
h
2
− µ (s h )
2
(3.6)
h
вычисляются наборы Tµ и Tσ с помощью зависимостей:
Tµ = {(X i,1:h w 1:h , µ (X i,1:h w 1:h ))}i =1
n
и
Tσ = {(X i,1:h w 1:h ,σ (X i,1:h w 1:h )) }i =1 .
3. Обучаются модели
µˆ (s h ) ~ q1µ s h + q 0µ
n
(3.7)
(3.8)
(3.9)
и
σˆ (s h ) ~ q1σ s h + qσ0 ,
(3.10)
помещая линию регрессии по точкам в Tµ и Tσ соответственно. Параметры q 0µ , q1µ , q σ0 и q1σ – стандартные оценки для коэффициентов функции линейной регрессии, полученные из наборов (3.7) и (3.8).
4. Во время запроса используется совокупная плотность вероятности
функции N (µˆ (X i,1:h w 1T:h ),σˆ (X i,1:h w 1T:h )) для оценки вероятности того, что
X i⋅ w T >δ .
Таким образом, предложен и исследован двухпараметрический алгоритм для поиска приблизительных наборов «k лучших» для заранее неизвестного содержания отношений, основанный на доступе к обучающей
информации из того же распределения, что и скрытое отношение, и обеспечивающий оценку вероятности того, что полная оценка элемента будет
достаточно высокой, чтобы войти в текущий набор «k лучших».
Для обоснования эффективности разработанного алгоритма проведена серия экспериментов, в которых сравним его с базовым алгоритмом
MP. Эксперименты проводились на синтетических и реальных данных.
Синтетические данные генерируются набором образцов из каждой X ij для
нормального распределения с нулевым средним значением и дисперсией.
Реальные данные состоят из набора запросов из контекста. Сравнение производилось по следующим критериям:
20
- временные затраты;
- сравнение порядков действий;
- чувствительность к параметру α;
- взаимосвязь весов и затрат;
- влияние k.
Результаты экспериментов, приведённые в работе, показывают, что
предложенный алгоритм с большим отрывом превосходит базовый с точки
зрения стоимости. В то время как MP алгоритм достигает очень высокой
точности, он делает это при высокой стоимости.
В завершение исследована трудоёмкость операций ввода/вывода для
оперативной и внешней памяти. Доказаны следующие теоремы.
Теорема 3.4. В оперативной памяти существует структура данных
размером порядка O (n ) , которая решает проблему извлечения «k лучших»
документов с трудоёмкостью O (k ) , независимо от p.
Теорема 3.5. В модели внешней памяти существует структура данных длиной O (nh ) , которая решает проблему поиска «k лучших» документов c трудоёмкостью O ( p/B + log B n + log (h) n + k/B ) операций ввода/вывода
для
любого
h ≤ log * n .
Это
означает,
что
оптимальный
O ( p/B + log B n + k/B ) -запрос может быть достигнут с использованием ли-
нейной O (n log * n ) -структуры.
Таким образом, получено доказательство существования структур
данных, решающих проблему поиска «k лучших» документов: размером
O (n ) в модели оперативной памяти – с трудоёмкостью O (k ) ; в модели
внешней памяти размером O (nh ) , h ≤ log * n – с трудоёмкостью
O ( p/B + log Bn + log (h) n + k/B ) операций ввода/вывода.
Четвертая глава посвящена решению задач бесшовной интеграции
систем поддержки, сопровождения, планирования и управления жизненным циклом продукции специального назначения на основе локальных и
сетевых хранилищ данных. Функциональная схема взаимодействия основных подсистем приведена на рис. 4.1.
Графический интерфейс системы разработан с применением архитектуры Model-view-controller (MVC). Выделены следующие основные
блоки разрабатываемой интерактивной системы:
Модель. Содержит в себе базу данных и представляет собой данные
и правила, используемые для работы с этими данными, что является концепцией управления приложением.
Представление данных, вид. Отвечает за визуализацию данных.
Контроллер – формирует связь между пользователем и системой;
обеспечивает контроль ввода данных пользователем и использует модель и
представление для реализации необходимой ответной реакции.
21
Преимуществом такой архитектуры, в сравнении с другими, является
высокая гибкость программного средства, чёткое разделение логики представления и логики приложения. Ещё одним плюсом такого подхода является возможность разработки модулей для системы сторонними разработчиками.
Рис. 4.1. Функциональная схема взаимодействия отдельных подсистем
Предложенные структурные и функциональные схемы специализированного программного обеспечения разработаны на основании концепции бесшовной интеграции с системами поддержки, планирования и сопровождения жизненного цикла и ориентацией на сохранение функциональной целостности четырёхуровневой модели клиент-серверной архитектуры развёртывания данных решений.
Программное обеспечение представляет собой серию специализированных программных межмодульных интерфейсов, которые позволяют
интегрировать не все модули из решения поддержки жизненного цикла, а
внедрять только необходимую часть, обеспечивая корректное функционирование с уже установленным программным обеспечением. Предложенные
средства направлены на обеспечение взаимодействия как систем планиро-
22
вания, сопровождения, поддержки, так и решений управления жизненным
циклом продукции.
Далее в работе определяется принцип разрешения конфликтов в условиях неполностью определённых данных у пользователей: рассматривая
сеть приоритетных доверительных отображений, найти те значения, которыми располагает (и доверяет) каждый пользователь. Определение разрешения конфликта основано на устойчивом решении, которое является глобальным присвоением для пользователей таких значений, чтобы все доверительные отображения были удовлетворены, и каждое значение происходило от величины, которая была указана в явном виде некоторым пользователем.
Определение 4.1 (Явное убеждение b 0 ). Явное убеждение является
частично определённой функцией пользователей по значениям b 0 (x ) –
значение, которое задается определённым пользователем x .
Определение 4.2 (Доверительное отображение). Доверительное
отображение – это тройка m = (z, p, x ) , где z, x – пользователи, а p – целое число. Смысл в том, что пользователь x доверяет значению пользователя z с приоритетом p . Мы именуем z родителем x , и x ребенком z .
Определение 4.3 (Доверительная сеть ДС). Доверительная сеть является взвешенным графом ДС = (U, E, b 0 ) , где U – множество пользователей, Е – множество приоритетных доверительных отображений и b 0
– явное убеждение.
Бинарные доверительные сети (БДС) – это ДС, где каждый узел x
имеет не более двух входящих рёбер, и явные убеждения b 0 (x ) определены только для корневых узлов x (узлов без родителей, но с явными убеждениями). Кроме того, предполагается, что каждый узел в БДС досягаем по
пути от какого-то корневого узла.
Отличительной особенностью разработанного Алгоритма 4.1 разрешения конфликтов является то, что он принимает на вход БДС и вычисляет множество возможных значений poss(x ) для каждого узла х. При этом
наборы определённых значений cert(x ) определяются по следующим правилам: cert(x ) = { a }, если poss(x ) = { a }, иначе cert(x ) = o/ . Алгоритм поддерживает закрытый набор всех узлов x , для которых poss(x ) уже вычислены. Этот набор инициализируется со всеми корневыми узлами, т.е. всеми узлами с явными убеждениями (I). Открытый набор содержит все другие узлы. Во время основного цикла (М) алгоритм выполняет два шага:
Шаг 1 (S1) «жадно» распространяет poss(x ) по приоритетным вершинам,
закрывая узлы назначения. Шаг 2 (S2) обрабатывает случай, когда больше
нельзя пройти ни одной предпочтительной вершины. Показано, что Алгоритм 4.1 работает за время O (n 2 ) и корректно вычисляет множество возможных кортежей для всех узлов x в БДС. Таким образом, приведен алго-
23
ритм урегулирования конфликтов с квадратичной по числу узлов трудоёмкостью.
Следующим важным результатом является формирование парадигм
для обработки ограничений в разрешении конфликтов. Парадигма формально определена в виде совокупности последовательных наборов убеждений, которые считаются в действительной или нормальной форме.
Агностика. Единственными допустимыми наборами убеждений в
этой парадигме являются единичные позитивные {v +} и наборы отрицаний {v−, w-,K}. Пользователь, после того как узнает значение объекта, не
хочет знать каких-либо ограничений, даже если они согласуются с этим
значением.
Эклектика. Любой последовательный набор убеждений является действительным. В этой парадигме пользователь принимает все ограничения,
которые соответствуют заданному значению. Таким образом, {a+, b-, c -}
являются действительным набором убеждений.
Скептика. Допустимы следующие наборы убеждений): все множества только с негативными убеждениями и все множества, которые содержат
ровно одно положительное убеждение и все негативные убеждения в соответствии с ним, то есть они имеют вид {v +} ∪ ( ⊥ − {v −}) . Таким образом,
когда пользователь принимает положительное убеждение v + , парадигма
также принимает ограничение, которое исключает все другие значения.
Парадигма выбирается системным администратором и применяется ко
всем пользователям. Устойчивое решение в доверительной сети зависит от
выбранной парадигмы.
Теорема (Агностическая/ Эклектическая Сложности). Пусть σ – Агностик или Эклектик (парадигма). Тогда введём следующие утверждения:
(а): Проверка, возможно ли положительное убеждение в данном узле x в
БДС, является NP-полной. (б): Проверка, является ли положительное
убеждение определённым в данном узле x в БДС, является со-NP-полной.
Таким образом, описаны три парадигмы для обработки ограничений в
разрешении конфликтов и доказано, что две из них сложные.
Рассмотрим расширение Алгоритма 4.1 в виде Алгоритма 4.2.
Фаза предварительной обработки (Р) находит все узлы, которые либо
имеют явные отрицательные убеждения или у которых приоритетные родители обладали явными отрицательными убеждениями. Для этого алгоритм начинает с узла x , где явное убеждение обладает только отрицательными значениями, и продолжает работу со всеми узлами, чьи приоритетные родители имеют только отрицательные убеждения. Фаза инициализации (I) снова создает наборы закрытых и открытых узлов и закрывает узлы
с явными положительными убеждениями. Шаг 1 (S1): в основном цикле
(М) перебираются все предпочтительные рёбра z → x и соответственно
обновляется repPoss(x ) . Шаг 2 (S2) заключается в следующем.
24
Алгоритм находит минимально связную компоненту S из открытых
узлов (как и раньше), но он не может просто заполнить её положительными значениями в ожидании входа S. Причина в том, что некоторые узлы в
S могут быть достигнуты из закрытых узлов через приоритетные вершины.
Именно эти вершины были опущены в Шаге 1. Таким образом, некоторые
узлы в компоненте S могут быть вынуждены принимать отрицательные
убеждения, и это предотвращает значение v + , находящееся в ожидании
входа S, от достижения всецелого множества S. Вместо этого вычисляется,
какое значение подмножества из S может быть достигнуто, и добавляется
v + во множество возможных значений для этих узлов. Для всех недоступных узлов добавляется ⊥ во множество возможных значений, потому
r
что в Скептической парадигме {v -} ∪S {v +} =⊥ .
Теорема 4.1. (Скептический алгоритм разрешения) Алгоритм 2 работает за время O(n 2 ) и вычисляет множество возможных значений для
Скептической парадигмы.
Таким образом, для скептической парадигмы предложен алгоритм,
работающий с квадратичной по числу узлов трудоёмкостью.
В завершении показывается, что при определённых условиях множество возможных значений может быть вычислено в объёме для всей совокупности объектов k 1 , k 2 ,K, k n .
Пусть TN1 ,K, TN n являются доверительными сетями для каждого из
n объектов. Сделаем следующие два допущения:
1) Множество доверительных отображений одинаково для каждого
объекта k i , т.е. пользователь x доверяет пользователю z в глобальном
масштабе, для всех объектов.
2) Если пользователь обладает явным убеждением для объекта k i ,
тогда пользователь обладает явным убеждением для каждого из объектов.
Адаптация приведённых выше алгоритмов к массовому вычислению
множества возможных кортежей с помощью запросов SQL осуществляется
следующим образом.
Пусть POSS(X, K, V ) обозначает отношение, представляющее возможные значения: запись (x, k, v ) означает, что v является возможным
значением для пользователя x и объекта k . Затем, на этапе 1 модифицированного алгоритма, при прохождении приоритетных вершин z → x мы
выполняем следующую массовую вставку:
вставить в POSS
выбрать ' x' как X, t.K, t.V
от
POSS t
где
t.X = ' z'
На этапе 2, когда выполняется «заполнение» сильно связной компоненты ССК с убеждениями, поступающими от пользователей z1 ,K, z k , мы
выполняем следующие массовые вставки для каждого x i ∈ SCC :
25
вставить в POSS
выбрать дискретный " x i " , как X, t.K, t.V
от
POSS t
где
t.X = ' z1 ' или … t.X = ' z k '
Проведена экспериментальная оценка алгоритмов:
1) Какова наблюдаемая производительность выполнения как для
квадратичного алгоритма разрешения конфликтов (RA), так и для алгоритма массового обновления?
2) Каков подход в сравнении с вычислениями стабильных моделей с
использованием продвинутых методов линейных программ?
Результаты эксперимента показаны на рис. 4.2.
Рис. 4.2. Результаты эксперимента
Для синтетического набора данных, как показано в диссертации,
DLV работает в экспоненциальном времени, в то время как RA работает в
практически линейном времени.
В пятой главе рассмотрены особенности и результаты алгоритмической программной реализации проектов прикладных подсистем на основе
вероятностных СУБД.
Исследованы потоковые сервисы и СУБД применительно к обработке массивов конструкторской документации в производстве изделий микроэлектроники специального назначения. Разработка проблемноориентированной интерактивной системы автоматизированного проектирования технологических процессов позволяет более глубоко исследовать
предметную область, что является первым шагом на пути к получению
наиболее эффективных проектных решений. При таком подходе появляется возможность создания и использования графических баз данных составных частей процессов, содержащих элементы, характерные для каждо-
26
го из этапов проектирования. Вместе с тем многовариантность выбора
конструкторских элементов приводит к исследованной в главах 2-4 задаче
многоальтернативного выбора.
Использование интерактивных систем проектирования в совокупности с базами графических данных элементов систем позволяет оперативно
получать и оценивать промежуточные проектировочные решения и оперативно управлять ходом процесса проектирования.
Автоматизированная система проектно-технологического комплекса
(АС ПТК) имеет гибкую организацию и возможность адаптации под изменяющиеся прикладные задачи; каждый программно-аналитический модуль
(ПАМ) обеспечивает проведение всех необходимых видов расчётов; возможность увеличения количества пользователей при росте объёма обрабатываемой информации; круглосуточный доступ к единому информационному пространству в течение всего периода эксплуатации. Структура АС
ПТК (общие принципы) приведена на рис. 5.1.
Рис. 5.1. Модульная структура АС ПТК (общие принципы)
Структура межмодульного взаимодействия с учётом выбора в качестве интерфейса интеграции системы 1С:PDM приведена на рис. 5.2.
Далее рассмотрены особенности архитектуры БД распределенной
системы оценки стойкости полупроводниковых изделий в защищенном
исполнении. Модель работы базы данных на основе передачи данных по
HTTPS показана на рис. 5.3. Модель разделена на три уровня. Первый уровень – пользовательский интерфейс с содержанием трех блоков: один для
27
Управление структурой изделия
Управление технологией
Согласование и утверждение
Управление изменениями
ANSYS Geometry
Interface
PLM-Компонента для
Autodesk Inventor
Модуль
верификации, анализа и
корректировки ошибок
уровня пользователей (L1), второй – для пользователей-владельцев проекта
(L2), а третий – для уровня администраторов (L3). Также на данном уровне
предоставляется возможность расширить возможности пользователей посредством присвоения им специальных привилегий при необходимости.
Рис. 5.2. Организация межмодульного взаимодействия ПАМ (общие принципы)
Представленные результаты исследований заложены в основу построения информационного хранилища распределенной системы оценки
стойкости полупроводниковых изделий к воздействию заряженных частиц
космического пространства. Структура системы включает (рис. 5.4):
- программную среду схемотехнического моделирования и проектирования, включающую в себя программу математического моделирования работы электрических схем PSpice и систему проектирования схемотехнических решений на основе Р-CAD, Protel и др.;
28
- внешнюю информационную среду поддержки моделирования и
проектирования, содержащую перечень ГОСТов и требований, предъявляемых техническими условиями в рамках разрабатываемого проекта;
Рис. 5.3. Архитектура уровневого доступа к БД
Рис. 5.4. Структура автоматизированной информационной системы моделирования и оценки характеристик стойкости радиоэлектронной аппаратуры
29
- встроенную информационную среду поддержки моделирования и
проектирования, содержащую справочную систему с интегрированной или
загружаемой библиотекой компонентов, обеспечивающую быстрый доступ
к различной справочной информации (критичные параметры и эксплуатационные характеристики);
- встроенную среду интеграции проектов, представляющую собой
связующее звено между программной средой схемотехнического моделирования и проектирования и справочной системой программного комплекса;
- подсистему оценки характеристик сбоеустойчивости бортовой аппаратуры космических аппаратов к единичным эффектам при воздействии
отдельных заряженных частиц космического пространства с возможностью оценки вероятности сбоя блока космического аппарата, включающую
модуль проверки конфигурации разрабатываемого блока на соответствие
требованиям стойкости.
Синтез структуры интегрированной базы данных полупроводниковых изделий привел к содержанию рис. 5.5.
Основные результаты работы внедрены в учебный процесс Воронежского государственного технического университета в рамках дисциплин «Вычислительные машины, системы и сети», «Базы данных», при проведении курсового и дипломного проектирования.
Рис. 5.5. Укрупнённая структура интегрированной базы данных
30
Результаты исследований используются в акционерном обществе
"Сигнальные микросистемы" (г. Воронеж), акционерном обществе "Воронежский Завод Полупроводниковых Приборов - Сборка", открытом акционерном обществе "Научно-исследовательский институт электронной техники" (г. Воронеж), акционерном обществе "Научно-исследовательский
институт полупроводникового машиностроения" (г. Воронеж) при разработке и сопровождении программного обеспечения изделий электронной
техники специального назначения.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В рамках проведённых научных исследований при выполнении диссертационной работы получены следующие основные результаты, которые
в совокупности можно квалифицировать как серьезное научное достижение
в виде теоретических основ многоальтернативных систем управления базами данных в условиях неполноты информации:
1. Предложена новая семантика «k лучших всюду» для многоальтернативных запросов типа «k лучших» в вероятностных базах данных,
основанная на постулатах точности, корректности и стабильности, которая
возвращает k наиболее высоко оцененных кортежей согласно их вероятности оказаться в «k лучших» ответах из возможных слов.
2. Создан табличный инструмент для выбора различных семантик. С
его помощью пользователи могут подобрать наиболее подходящую семантику, основываясь на правильной комбинации условий и их применении.
3. Предложены алгоритмы оценки «k лучших» запросов на основе
инъективных оценочных функций с использованием семантики «k лучших
всюду» в простых и общих вероятностных базах данных, обеспечивающие
полиномиальность по времени.
4. Проведён теоретический пространственно-временной анализ
предложенных алгоритмов. Разработаны эффективные эвристические алгоритмы, улучшающие производительность базовых алгоритмов.
5. Введено понятие вынужденного событийного отношения, отличающееся использованием инъективной оценочной функции и одноатрибутного вспомогательного отношения, обеспечивающее редукцию семантики «k лучших всюду» от общего случая до «k лучших всюду» для простых вероятностных отношений.
6. Обобщена семантика «k лучших всюду» для обычных функций
оценок, отличающаяся использованием нового понятия «политика распределения» и обеспечивающая построение алгоритма, основанного на динамическом программировании, для оценки выборки при использовании
равной политики распределения.
7. Представлена концепция полностью динамической структуры
данных для эффективного функционирования «k лучших» запросов в вероятностных базах данных управления системами специального назначе-
31
ния, связанная с рейтингом кортежей, у которых есть и оценка, и вероятность для каждого кортежа, которая может извлекать «k лучших» кортежей за время O(k log N ) и получать обновления с оценкой O(log N ) .
8. Оценена эффективность новой структуры данных по результатам
экспериментов с использованием синтетических и реальных данных.
9. Предложен и исследован двухпараметрический алгоритм для поиска приблизительных наборов «k лучших» для заранее неизвестного содержания отношений, основанный на доступе к обучающей информации
из того же распределения, что и скрытое отношение, и обеспечивающий
оценку вероятности того, что полная оценка элемента будет достаточно
высокой, чтобы войти в текущий набор «k лучших».
10. Эксперименты показывают, что предложенный алгоритм с большим отрывом превосходит базовый с точки зрения стоимости. В то время
как MP алгоритм достигает очень высокой точности, он делает это при высокой стоимости.
11. Доказано, что в оперативной памяти существует структура данных размером порядка O (n ) , которая решает проблему извлечения «k
лучших» документов с трудоёмкостью O (k ) независимо от p.
12. Доказано, что в модели внешней памяти существует структура
данных длиной O (nh ) , которая решает проблему поиска «k лучших» документов c трудоёмкостью O ( p/B + log Bn + log (h) n + k/B ) операций ввода/вывода для любого
h ≤ log * n . Это означает, что оптимальный
O ( p/B + log Bn + k/B) -запрос может быть достигнут с использованием ли-
нейной O ( n log * n ) -структуры.
13. Осуществлено проектирование механизмов взаимодействия информационной системы с подсистемами управления жизненным циклом на
основе идеологии бесшовной интеграции.
14. Предложена
структура
специального
проблемноориентированного программного обеспечения, содержащая интегрированные модули контроля, коррекции, верификации и визуализации модели
транслируемых данных, отличающаяся интеграцией с широким кругом
систем принятия решений и сопровождения жизненного цикла.
15. Предложенные структурные и функциональные схемы специализированного программного обеспечения разработаны на основании концепции бесшовной интеграции с системами поддержки, планирования и
сопровождения жизненного цикла и ориентацией на сохранение функциональной целостности четырёхуровневой модели клиент-серверной архитектуры развёртывания данных решений.
16. Программное обеспечение представляет собой серию специализированных программных межмодульных интерфейсов, которые позволяют интегрировать не все модули из решения поддержки жизненного цикла,
32
а внедрять только необходимую часть, обеспечивая корректное функционирование с уже установленным программным обеспечением. Предложенные средства направлены на обеспечение взаимодействия как систем планирования, сопровождения, поддержки, так и решений управления жизненным циклом продукции.
17. Определено принципиальное решение задачи урегулирования
конфликта, названное устойчивым решением, и приведен алгоритм, который работает с квадратичной по числу узлов трудоёмкостью.
18. Описаны три парадигмы для обработки ограничений в разрешении конфликтов и доказано, что две из них сложные. Предложен алгоритм,
который работает с квадратичной по числу узлов трудоёмкостью.
19. В ходе проведённой оценки характеристик сбоеустойчивости бортовой аппаратуры космических аппаратов и комплектующих полупроводниковых изделий с использованием программного комплекса выявлено,
что разработанное математическое обеспечение позволяет определять характеристики стойкости комплектующих полупроводниковых изделий с
высокой точностью и предоставляет разработчику возможность оперативно определить правильность выбора элементной базы.
20. Предложена концепция модульной структуры информационной
системы моделирования и оценки характеристик стойкости радиоэлектронной аппаратуры, учитывающая специфику разработки аппаратуры
специального назначения.
21. Разработана структурная схема программного обеспечения, позволяющего определить правильность выбора элементной базы, оценить
характеристики сбоеустойчивости бортовой аппаратуры космических аппаратов и комплектующих при воздействии отдельных тяжёлых заряженных частиц и высокоэнергетичных протонов космического пространства.
22. Получен патент на изобретение, 6 свидетельств о государственной регистрации программы.
23. Осуществлено внедрение на предприятиях электронной промышленности.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ
В СЛЕДУЮЩИХ РАБОТАХ:
Публикации в изданиях, рекомендованных ВАК РФ
1. Анализ вычислительных алгоритмов полиномиального преобразования
булевых функций/ А.А. Акинин, А.В. Ачкасов, С.Л. Подвальный, С.В. Тюрин //
Системы управления и информационные технологии 2013. №3.1(53). С.108-112.
2. К технологии раннего распараллеливания разработки мультиверсионного программного обеспечения информационных систем / О.Я. Кравец, А.В.
Ачкасов, В.В. Скляров // Экономика и менеджмент систем управления, 2014, т.
№1.1(11). С. 136-144.
3. Принципы построения системы интерактивного проектирования технологических процессов/ В.Ф.Барабанов, А.М.Нужный, А.Д.Поваляев, Н.И. Гре-
33
бенникова, А.В.Ачкасов // Вестник Воронежского государственного технического университета. 2014. Т. 10. № 5. С. 10-13.
4. Актуализация межмодульных взаимодействий на основе обработки
мультиверсионных элементов данных / О.Я.Кравец, Г.И.Шахворостов, А.В. Ачкасов // Вестник Воронежского государственного технического университета.
2014. Т. 10. № 3-1. С. 22-26.
5. Разработка модели базы данных распределенной системы оценки
стойкости полупроводниковых изделий в защищенном исполнении / Е.С. Пашковская, М.Е.Пашковский, А.В.Барабанов, А.В.Ачкасов // Вестник Воронежского государственного технического университета. 2014. Т. 10. № 4. С. 22-24.
6. Алгоритм векторно-бинарной последовательной минимизации полиномов Рида-Маллера / А.А.Акинин, Ю.С.Акинина, А.В.Ачкасов, С.В.Тюрин //
Вестник Воронежского государственного технического университета. 2014. Т.
10. № 5. С. 25-29.
7. Моделирование процессов функционирования беспроводной сети с
временным разделением каналов / С.В.Тюрин, И.В.Шмарин, А.В.Ачкасов //
Вестник Воронежского государственного технического университета. 2014. Т.
10. № 5. С. 59-63.
8. Повышение эффективности функционирования единого корпоративного информационного пространства с использованием мультиверсионной обработки данных // А.В.Ачкасов, О.Я.Кравец, В.В.Скляров // Системы управления и
информационные технологии 2014. №1(55). С.43-47.
9. Моделирование минимизации межинтерфейсных потерь при многофазном проектировании / А.В.Ачкасов, О.Я.Кравец, Е.С.Подвальный // Радиотехника 2014 №3. С.116-119.
10. Особенности адаптивного управления группой мобильных объектов /
А.В.Ачкасов, О.Я.Кравец, Е.С.Подвальный // Радиотехника 2014 №3. С.110-114.
11. Системный анализ вычислительных алгоритмов полиномиального
преобразования булевых функций // А.А. Акинин, А.В. Ачкасов, С.Л. Подвальный, С.В. Тюрин // Радиотехника 2014 №3. С.104-108.
12. Методы и алгоритмы моделирования тепловых полей в трехмерной
сборке интегральных схем / В.Ф.Барабанов, С.Л.Подвальный, А.В. Ачкасов,
М.Н.Аралов // Радиотехника 2014 №6. С.82-87.
13. Математическое и программное обеспечение исследования межмодульных интерфейсов информационных систем / А.В.Ачкасов, Л.М. Минаков //
Экономика и менеджмент систем управления, 2014 №2.3 (12) С. 348-354.
14. Моделирование и групповое проектирование межмодульных интерфейсов на основе ориентированного взвешенного мультиграфа / А.В.Ачкасов,
В.С. Кобелев // Экономика и менеджмент систем управления, 2014 №2.3 (12) С.
442-450.
15. Особенности анализа и проектирования механизмов межмодульного
взаимодействия в переходных режимах функционирования на основе волновых
алгоритмов / О.Я.Кравец, Е.С.Подвальный, А.В.Ачкасов // Радиотехника 2014
№6. С.88-92.
16. Проектирование и испытания микросхем для систем сбора и обработки
информации / В.А.Скляр, А.В.Ачкасов, К.В.Зольников // Радиотехника 2014 №6.
С.94-98.
17. Polynomial transformation of Boolean functions: analysis of computational
algorithms / A.A. Akinin, A.V. Achkasov, S.L. Podval`nyi, S.V. Tyurin // Automation
34
and Remote Control 2014 №7. С.1301-1309.
18. Числовая проекция семантической информации / В.Ф. Барабанов, А.М.
Нужный, А.Д. Поваляев, Н.И. Гребенникова, А.В. Ачкасов // Вестник Воронежского государственного технического университета. 2014 Т.10 №5. С.10-13.
19. Организация графических баз данных для интерактивного проектирования технологических процессов / А.А. Акинин, А..Ю. Акинина, А.В. Ачкасов,
С.В. Тюрин // Вестник Воронежского государственного технического университета. 2014 Т.10 №5. С.25-29.
20. Алгоритм запуска сторонних приложений из системы 1С:PDM / С.В.
Тюрин, И.В. Шмарин, А.В. Ачкасов // Радиотехника 2014 №3. С.59-63.
21. Особенности интеграции потоковых сервисов и интерфейсов передачи
данных в распределенных программных системах / А.В.Ачкасов, О.Я.Кравец //
Системы управления и информационные технологии. 2015. Т. 61. № 3.1. С. 109-114.
22. Программная реализация многовариантного математического моделирования тепловых полей / М.Н.Аралов, А.В.Ачкасов, В.Ф.Барабанов,
С.Л.Подвальный // Вестник Воронежского государственного технического университета. 2015. Т. 11. № 1. С. 32-34.
23. Проблемы оценки запросов типа «k лучших» в вероятностных базах
данных/ А.В.Ачкасов, О.Я.Кравец // Экономика и менеджмент систем управления. 2015. Т. 16. № 2.3. С. 320-329.
24. Концепция полностью динамической структуры данных для эффективного функционирования k-лучших запросов в вероятностных БД управления системами специального назначения / А.В.Ачкасов, О.Я. Кравец // Экономика и менеджмент систем управления. 2015. Т. 17. № 3. С. 10-17.
Патенты на изобретения, свидетельства о государственной регистрации программ для ЭВМ
25. Патент РФ. Способ реализации логических преобразователей/
Ю.С.Акинина, А.В.Ачкасов, С.В. Тюрин №2541905 от 20.02.2015.
26. Барабанов В.Ф., Кенин С.Л., Сафронов В.В., Сукачев А.И., Ачкасов
А.В. Межмодульная и информационная интеграция SAP - 1C. - Свидетельство о
государственной регистрации программы для ЭВМ. М.: ФИПС, 2014. №
2014616316 от 19.06.2014.
27. Подвальный С.Л., Кенин С.Л., Сафронов В.В., Барабанов В.Ф., Ачкасов А.В. Межмодульная и информационная интеграция SAP – Teamcenter. Свидетельство о государственной регистрации программы для ЭВМ. М.: ФИПС,
2014. № 2014616315 от 19.06.2014.
28. Подвальный С.Л., Кравец О.Я., Сафронов В.В., Барабанов В.Ф., Ачкасов А.В. Настраиваемый интерактивный интегратор гетерогенных проектов. Свидетельство о государственной регистрации программы для ЭВМ. М.: ФИПС,
2014. № 2014616318 от 19.06.2014.
29. Барабанов В.Ф., Тюрин С.В., Пашковская Е.С., Локтева М.В., Ачкасов
А.В. Моделирование и численная оценка стойкости изделий специального назначения при воздействии заряженных частиц. - Свидетельство о государственной регистрации программы для ЭВМ. М.: ФИПС, 2014. № 2014616334 от
19.06.2014.
30. Подвальный С.Л., Кравец О.Я., Пашковский М.Е., Барабанов В.Ф., Ачкасов А.В. Моделирование и численная оценка стойкости изделий специального
назначения при воздействии электромагнитных полей. - Свидетельство о государственной регистрации программы для ЭВМ. М.: ФИПС, 2014. № 2014616317
35
от 19.06.2014.
31. Локтева М.В., Кравец О.Я., Нгуен Сон Лам, Хоанг Жанг, Ачкасов А.В.
Система управления электронной очередью заданий на обслуживание. - Свидетельство о государственной регистрации программы для ЭВМ. М.: ФИПС, 2015.
№ 2015660855 от 12.10.2015.
Монографии
32. Основы специального математического и программного обеспечения
многоальтернативных систем управления вероятностными базами данных: Монография/ А.В. Ачкасов. – Воронеж: Издательство «Научная книга, 2016. – 280 с.
33. Hardness simulation and evaluation for electronic products in the space:
Monograph/ A.V.Achkasov, V.F.Barabanov, M.E.Pashkovskiy; Ed. by S.L. Podvalniy. – Yelm, WA, USA: Science Book Publishing House, 2013. - 172 p.
34. Проектирование математического и программного обеспечения отказоустойчивых сложных функциональных блоков микроэлектроники специального
назначения: Монография/ А.В. Ачкасов, В.А. Смерек; под ред. С.Л. Подвального. –
Воронеж: Издательство «Научная книга, 2014. – 160 с.
Статьи и материалы конференций
35. Разработка микросхемы для систем сбора и обработки данных /
В.А.Скляр, А.В.Ачкасов, К.В.Зольников // Моделирование систем и процессов.
2013. № 1. С. 40-44.
36. Обеспечение стойкости микроконтроллеров к воздействию тяжёлых заряженных частиц / В.К.Зольников, А.И.Яньков, В.А.Смерек, А.В.Ачкасов // В сб.:
Элементная база отечественной радиоэлектроники. Тр. I Российско-Белорусской
конф., посв. 110-летию со дня рождения О.В. Лосева. 2013. С. 60-64.
37. Межмодульное взаимодействие в распределенных информационных
системах с нестабильной структурой / А.В.Ачкасов, О.Я.Кравец // Информационные технологии моделирования и управления. 2014. Т. 86. № 2. С. 146-157.
38. Моделирование воздействия ТЗЧ в активных областях элементов микросхем при проектировании / К.В.Зольников, В.А.Смерек, А.В.Ачкасов,
В.А.Скляр // Моделирование систем и процессов. 2014. № 1. С. 15-17.
39. Features of creation, development and optimization of the information
system constructed on distributed database / A.V.Achkasov, O.Ja.Kravets // Modern
informatization problems in economics and safety: Proc. of the XX-th Int. Open
Science Conf. (Yelm, WA, USA, January 2015). 2015. С. 7-15.
40. Потоковые сервисы и СУБД применительно к обработке массивов
конструкторской документации / А.В.Ачкасов, В.Ф.Барабанов, С.Л.Подвальный
// Информационные технологии моделирования и управления. 2015. Т. 93. № 3.
С. 262-269.
41. Estimation of requests like "k of the best" / A.V.Achkasov, O.Ja.Kravets //
Modeling and Information Technologies: Selected Papers. Yelm, WA, USA, 2015. С.
28-45.
42. Development of the job oriented software concept for system components of
a seamless data integration / S.L.Podvalny, V.F.Barabanov, A.V.Achkasov // Modeling
and Information Technologies: Selected Papers. Yelm, WA, USA, 2015. С. 104-114.
43. Оценка запросов в семантике «k лучших всюду» / А.В.Ачкасов,
О.Я.Кравец // Международна научна школа "Парадигма". Лято-2015. Сборник
научни статии в 8 томах. 2015. С. 34-52.
44. Разработка концепции проблемно-ориентированного программного
обеспечения компонент системы бесшовной интеграции данных / С.Л. Подваль-
36
ный, В.Ф.Барабанов, А.В.Ачкасов // Международна научна школа "Парадигма".
Лято-2015. Сборник научни статии в 8 т. Т. 1. 2015. С. 226-238.
45. Конфликты по данным в современных СУБД: разрешение на основе доверенных отображений / О.Я.Кравец, А.В.Ачкасов // Информационные технологии моделирования и управления. 2015. Т. 94. № 4. С. 326-335.
46. Структура и функционирование вероятностных БД управления системами специального назначения на основе концепции k-лучших запросов / А.В.
Ачкасов // Информационные технологии моделирования и управления. 2015. Т.
94. № 4. С. 364-373.
47. Потоковые сервисы и СУБД применительно к обработке массивов
конструкторской документации / А.В.Ачкасов, Т.И.Сергеева // Информационные
технологии моделирования и управления. 2015. Т. 96. № 6. С. 536-545.
48. Конфликты по данным в современных СУБД: разрешение конфликтов
с ограничениями/ А.В.Ачкасов // Информационные технологии моделирования и
управления. 2015. Т. 95. № 5. С. 454-468.
49. Finding information in the database, based on the use of k-best queries /
A.V.Achkasov, O.Ja.Kravets // Modern informatization problems in economics and
safety: Proc. of the XXI-th Int. Open Science Conf. Yelm, WA, USA, 2016. С. 3-15.
50. Numerical study of the effectiveness of requests for probabilistic relationship in a database incomplete information/ A.V.Achkasov, O.Ja.Kravets // Modern informatization problems in simulation and social technologies: Proc. of the XXI-th Int.
Open Science Conf. Yelm, WA, USA, 2016. С. 124-144.
51. Intermodular and information integration of SAP and application specific
subsystems / A.V.Achkasov, V.F.Barabanov, S.L.Podvalny // Modern informatization
problems in the technological and telecommunication systems analysis and synthesis:
Proc. of the XXI-th Int. Open Science Conf. Yelm, WA, USA, 2016. С. 249-258.
52. Управление на процеса на събиране на данни в условия на големи измерения и непълнота на информацията / А.В.Ачкасов, С.Л.Подвальный // Парадигма (България). 2016. Т. 1. №1. С.3-21.
Подписано в печать 29.08.2016.
Формат 60х84/16. Бумага для множительных аппаратов.
Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 0000
ООО «Цифровая полиграфия»
394036, Россия, г. Воронеж, ул. Ф. Энгельса, 52
Документ
Категория
Без категории
Просмотров
7
Размер файла
1 080 Кб
Теги
теоретические, условия, данных, базами, многоальтернативных, система, неполноты, основы, управления, информация
1/--страниц
Пожаловаться на содержимое документа