Иерархический метод индексирования базы предикатов




НазваниеИерархический метод индексирования базы предикатов
Дата публикации13.04.2013
Размер66,1 Kb.
ТипДокументы
pochit.ru > Информатика > Документы




Косьмина Я.О.

http://darviarush.narod.ru
Индексация предикатов в Прологе
В настоящее время популярность Пролога продолжает оставаться на относительно высоком уровне не только на Западе, но и в России [1]. Пролог - универсальный язык [2] и на нём можно создавать любые приложения, начиная от программ искусственного интеллекта и заканчивая базами данных. Причём программа на Прологе сама является базой данных, и программисту для работы с этой базой не нужно изучать дополнительно, скажем, SQL. В базах данных для ускорения поиска применяется индексация данных [3]. Однако индексация базы данных в Прологе затруднена переменными предикатов, которые не могут выступать ключами ввиду невозможности предсказать их значения.

Подавляющее большинство интерпретаторов Пролога используют последовательный метод доступа к предикатам, хотя велись работы по индексации правил базы предикатов [4], тем не мнение эта область давно не развивается, развиваются объектно-ориентированные версии пролога [6] и интеграция Пролога с реляционными СУБД [5].

В данной статье рассматриваются способы индексирования предикатов по всем фактам и правилам независимо от переменных.
^ Термы и переменные

Предикат состоит из фактов и правил. Факт представляет собой структуру - терм, а правило состоит из заголовка-терма и, необязательно, тела правила [1]. Тело правила нас не интересует - индексироваться должен заголовок - имя с параметрами. Cам терм состоит из имени и 0-ля или более параметров:
m(x(z), f)
Вложенные термы представляются указателями:
m(x(z), f) -> m 1024 1678

1024 -> x 900

900 -> z

1678 -> f
Таким образом, при произведении унификации, можно сравнивать только указатели, не сравнивая сами структуры. Вроде всё в порядке, но опять нам мешают переменные: терм m(f(A)) будет иметь указатель отличный от указателя на терм m(f(x)), где x является атомом. Поэтому придётся 1-й бит в указателе использовать для определения - есть ли в терме переменные или нет, и если они есть, то унифицировать (сравнивать) термы до идентификаторов термов без переменных:
m(A,x(z)) -> -1234

-1234 -> m 0 9000

9000 -> x 8901

8901 -> z
^ Иерархический метод индексирования базы предикатов

Ключом в методе будет выступать имя предиката, а в информационном поле будет находиться проиндексированное множество термов для 1-х аргументов термов с этим именем, и т.д. (рис. 1).



Специальный идентификатор (end) указывает, когда заканчивается терм. Он необходим, чтобы обозначить все предикаты (рис. 2).

m.

m(k).

m(k, d).


Кроме того, потребуется указатель на аргументы каждого вложенного терма (рис. 3):



m(x(f,e),r) ->
Этот подход основан на иерархической базе данных. Назовём его И-методом (иерархическим).

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


Сбалансированное дерево
В И-методе для ускорения поиска предпочтительнее использовать сбалансированное дерево (рис. 4).

(end)

(end)



m
m.


k
m(k).


(end)

d

(a)

(b)

(c)
m(k, d).


(d)

Рис. 4. Сбалансированное дерево в узлах дерева базы предикатов


Поиск будет осуществляться следующим образом. Допустим, у нас есть база предикатов (рис. 4), поставлена цель m(A) – найти все записи с именем m и любым одним аргументом. В корневом сбалансированном дереве (рис. 4(a)) производится поиск ключа m, ключу m соответствует дерево (b), в нём производится последовательное считывание всех записей, кроме ключа (end), в данном случае цели соответствует только факт m(k). После нахождения ключа k производится поиск в дереве (с) ключа (end), чтобы узнать – завершается на этом найденный факт или нет.

Теперь оценим ЭХ и ЭД (эффективность доступа) этого метода.

Напомним, что эффективность хранения - это отношение полезных данных ко всем данным, а эффективность доступа обратно пропорциональна количеству обращений к памяти, необходимых для доступа к элементу.

Последовательный метод:
ЭХп = 1

ЭДп = 2/n
где n – количество записей.

Однако это для нахождения 1-й записи. Пролог-машина же должна найти все факты и правила, термы-заголовки которых соответствуют поставленной цели, поэтому:
ЭДп = 1/n.
При использовании бинарного дерева для индексации базы предикатов,

допустим, что указатель и ключ равны по величине, тогда:
ЭХб = 1/3

ЭДб = log n
И-метод при тех же условиях:
ЭХи = 1/4

ЭДи = ЭДб/k
где k – среднее количество аргументов в заголовочном терме. Для большинства Пролог-программ k = 3.
^ Комбинаторный метод индексирования базы предикатов

Поскольку цель представляет собой маску:

m(x,A,z)
то можно индексировать терм, по имени и аргументам в отдельности и в комбинации:
m(x,y)
m, x, y, mx, xy, my, mxy
Чтобы полученные ключи были по величине одинаковы (для быстрого сравнения), поля складываются через бинарную операцию xor (исключающее “или”):
(указатель на m) xor (указатель на x),
полученный результат и будет ключом. Поиск терма будет производится по Б-дереву.

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











данные







данные


а)

б)


Рис. 5. Индексация данных:

а) одним сбалансированным деревом

б) несколькими сбалансированными деревьями



Нужно заметить, что количество ключей резко возрастает даже при небольшом увеличении количества аргументов терма, согласно формуле комбинаторики [7, с. 107]:

, где n – это количество аргументов терма
Таким образом, для комбинаторного метода ЭХ и ЭД:

ЭДк = ЭДб = log n
Выводы

Нельзя однозначно сказать какой из рассмотренных методов лучше, поскольку комбинаторный метод обладает хотя и более высокой скоростью доступа, но лишь за счёт непомерной неэффективности хранения данных. Кроме того, по этой причине он вряд ли найдёт применение где-то в базах данных, помимо Пролога при большом количестве полей в таблицах. А вот в Прологе количество аргументов в термах в среднем равно 3, и редко превышает 4. Поэтому, иерархический метод нужно использовать, когда важна эффективность хранения, а комбинаторный – когда важна эффективность доступа.

В статье был рассмотрен способ обхода проблемы переменных и предложены два возможных метода построения базы предикатов. Использование изложенных методов в базе предикатов должно существенно повысить скорость работы с ней.
^ Список источников
1. Адаменко А., Кучуков А. Логическое программирование и Visual Prolog. Серия "В подлиннике". - СПб.: БХВ-Петербург, 2003 - 992 с.: ил.

2. Карпова Т. Базы данных: модели, разработка, реализация. – СПб.: Питер, 2001. – 304с., ил.

3. Пролог в России / http://www.russianenterprisesolutions.com/techno/prorus.html

4. Ta Chen, I. V. Ramakrishnan, R. Ramesh: Multistage Indexing Algorithms for Speeding Prolog Execution. ICLP 1992: 639-653, final version: SPE 24(12): 1097-1119 (1994)

5. IF/Prolog / http://www.ifcomputer.co.jp/en/manuals5.2/home.html.

6. Шапиро Э., Такеути А. Объектно-ориентированное программирование в Параллельном Прологе. // Язык Пролог в пятом поколении ЭВМ. – М.: Мир, 1988. – С. 71

7. Е.П. Нелин, Алгебра в таблицах, - Харьков: “Мир детства”, 1998.

Похожие:

Иерархический метод индексирования базы предикатов iconЛабораторная работа №1 По предмету: «Искусственный интеллект.»
Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов...
Иерархический метод индексирования базы предикатов iconСистема классификационных схем для индексирования документов в области физики
Такой тезаурус построен для области физики полупроводников и смежных проблем. Тезаурус оказался полезен для облегчения процесса индексирования...
Иерархический метод индексирования базы предикатов iconИдеализация, знаковое моделирование, формализация, метод мысленного...
Научный метод – это система регулятивных принципов и приемов, с помощью которых достигается объективное познание действительности,...
Иерархический метод индексирования базы предикатов iconУрок-практикум по теме «Разработка базы данных «9 класс»
«Разработка базы данных “9 класс”». В разработке представлены все этапы урока. Урок рекомендуется провести после изучения темы «Базы...
Иерархический метод индексирования базы предикатов iconКлассы, содержащие массивы встроенных типов данных
Изучение особенностей определения класса, содержащего указатели на встроенные типы данных. Определение конструкторов, деструктора,...
Иерархический метод индексирования базы предикатов iconПроектная деятельность как условие развития творческих способностей...
Метод проектов не является принципиально новым в мировой педагогике. Этот метод возник во второй половине X ix века в школах США...
Иерархический метод индексирования базы предикатов iconМетод проектов: история и теория вопроса
Метод проектов широко известен и издавна используется в мировой педагогической практике. Впервые он был описан в книге «Метод проектов»...
Иерархический метод индексирования базы предикатов iconТема Язык логики
Задание: Определите семантическую категорию языка и запишите её с использованием языка логики предикатов
Иерархический метод индексирования базы предикатов icon«Мораль»
Методы: словесный, частично поисково-исследовательский, метод сравнительного анализа, метод гипотез
Иерархический метод индексирования базы предикатов iconТехнологическая карта дисциплины «Алгебра и математическая логика»
Элементы математической логики (высказывания, логические операции; логическое следствие, методы доказательств; предикаты, кванторы;...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2019
контакты
pochit.ru
Главная страница