3. Списки и базы данных

3.1. Список как структура данных

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

1. Такие программы быстро становятся очень длинными и трудными для сопровождения.
2. Необходима чрезмерно большая работа по вводу фактов.
3. Программы не удовлетворяют требованиям гибкости и трудны для модификации. Каждый раз, когда вводится новый аргумент, необходимо модифицировать все отношения, которые его используют.
4. Такие программы занимают очень много места в памяти.
5. Достаточно трудно, а в определенных случаях и невозможно обнаружить и извлечь нужную порцию информации. В больших базах данных пользователям потребуется знать имена и определения всех отношений, предназначенных для работы с ними.
6. Принципы, положенные в основу построения программы, в большей степени определяют то, как программа будет использоваться. В частности, от них во многом будут зависеть используемые типы данных.

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

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

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

1. (a b с d)
2. (a be def ghi)
3. (1 2 3 4)
4. (Adam Eve Joe Tom)
5. (a2 Jim evergreen 25)
6. (menu roll rota portfolio)
7. ((a b с ()) (what is next ?) (This is a list) (о ( ) zero null))

Каждый из этих списков содержит по четыре члена. Для некоторых списков связь между членами устанавливается легко, в то время как трудно, например, установить связь между элементами пятого списка. Шестой список состоит из элементов, являющихся названиями типов списков; седьмой - это список, состоящий из списков. В седьмом списке выделяется пустой список, обозначаемый ( ). Пустым называется список, не содержащий ни одного элемента. Отметим, что список (( )) не является пустым: он содержит один член - пустой список. Понятие "список" имеет много общего с понятием "множество". Так же как и множество, список можно задать, либо указав все его элементы (например, кошки, собаки, крысы, мыши), либо определив правило формирования его членов (например, все положительные числа меньше 20).

При обработке списков часто используются два следующих отношения: APPEND и ON. Рассмотрим сначала отношение ON:

X isa list-type if

X ON (menu roll rota portfolio)

Диалог между пользователем и системой, основанной на использовании этого отношения, может выглядеть так:

all (x: х isa list-type)

[ответов (больше) нет]

Заметим, что числа, непосредственно предшествующие буквам, вчитаются самостоятельными термами, т. е. в ответ на запрос

будет напечатано а2, ЗЬ, 33, с, 44, d4, 555.

В микроПрологе предусмотрен специальный оператор конструирования списков; он обозначается | . Выражение

означает, что имеется конструкция, состоящая из элемента X, за которым следует список Y. Выражение

означает, что за элементами X и Y следует список Z. Другими словами, конструктор списков позволяет расчленить список (X|Y на голову X и хвост Y.

Отношение APPEND служит для объединения двух списков. Например,

which (x: APPEND ((abc) (def) x))

No (more) answers

В рамках стандартного синтаксиса определение отношения ON будет выглядеть так:

((ON X (X|Y))

(ON X Z)),

означая:

1. X находится в отношении ON со списком, голова которого равна X.

2. X находится в отношении ON со списком, состоящим из головы Y и хвоста Z, если X находится в отношении ON с Z.

Отношение APPEND определяется так:

((APPEND ( ) X X))

((APPEND (X Y) Z (X x)) (APPEND Y Z x))

Это означает:

1. Результатом объединения пустого списка ( ) с любым списком X является список X.

2. Если результатом объединения списков Y и Z является список х, то результатом объединения списков X|Y и Z будет список X|х, т. е. отношение APPEND используется как для объединения, так и для расчленения списков.

Например, в ответ на запрос

будет получено (John Joe Alan Bill), т. е. производится объединение двух списков.

Далее, ответом на запрос

является (А В С),

т. е. списку х будет присвоено значение (А В С).

Наконец, запрос

приведет к тому, что х получит значение (Joe).

Упражнение 3.1

Определить, что будет получено в ответ на следующие запросы:

а) all (x: x ON (1/24) ( ) а2 2а)

б) all (х: х ON (ab abc (a (Joe Ted) John) def)

Упражнение 3.2

Определить результаты:

a) which (x: APPEND ((THIS IS) (A LIST) x))

б) which (x: APPEND (x (IS) (WHAT IS)))

в) which (x: APPEND ((THIS) x (THIS IS)))

г) which (x y: APPEND ((a b) (c d e f) (x j y)))

д) which (x y: APPEND ((x | y) (e f) (ab cd e f)))