1.3.2. Примеры инвертированных списков и инвертированных списков сцепления.

Созданию инвертированных списков была посвящена третья лабораторная работа [1].

Для таблицы ПОСТАВЩИК с целью ускорения поиска информации для исправления записи и удаления должен быть создан инвертированный список по полю КОД ПОСТАВЩИКА.

Код поставщика	Номера записей в таблице ПОСТАВЩИК, которые этому значению соответствуют
50	1
75	2
100	0
200	3
215	4

Еще раз отметим, что инвертированный список должен быть упорядочен по тому полю, для которого он создан. В приведенной выше таблице упорядочение проведено по полю КОД ПОСТАВЩИКА. Нумерация строк в основной таблице ПОСТАВЩИК ведется с 0.

Если в основную таблицу ПОСТАВЩИК введена новая запись, то в инвертированный список она должна быть поставлена так, чтобы он оставался отсортированным.

Например, пусть введена запись:

120

Сувенир

Краснодар

Она стала последней в таблице ПОСТАВЩИК.

Инвертированный список по полю КОД ПОСТАВЩИКА изменится так:

Код поставщика	Номера записей в таблице ПОСТАВЩИК, которые этому значению соответствуют
50	1
75	2
100	0
120	5
200	3
215	4

Если из таблицы ПОСТАВЩИК удалена запись с ключом 75, то в самой таблице и в инвертированном списке рекомендуется эту запись пометить:

Таблица ПОСТАВЩИК:

Код поставщика	Имя	Город
100	Свобода	Москва
50	Апрель	Москва
*	Калина	Екатеринбург
200	Аист	Санкт-Петербург
215	Невская косметика	Санкт-Петербург

Инвертированный список:

Код поставщика	Номера записей в таблице ПОСТАВЩИК, которые этому значению соответствуют
50	1
*	2
100	0
120	5
200	3
215	4

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

Инвертированные списки сцепления строятся для того, чтобы соединить таблицы по каким-то полям. Например, таблицы ПОСТАВЩИК и ПОСТАВКА могут быть соединены по полю КОД ПОСТАВЩИКА. Отметим, что описании этих полей в программе должно быть одинаковым.

Для одного соединения строятся две таблицы: инвертированный список сцепления от таблицы ПОСТАВЩИК к таблице ПОСТАВКА (далее ИСС 1), и инвертированный список сцепления от таблицы ПОСТАВКА к таблице ПОСТАВЩИК (далее ИСС 2).

ИСС 1 имеет столько строк, сколько таблица ПОСТАВЩИК, и один столбец, в котором записаны номера строк из таблицы ПОСТАВКА, в которых встретился тот же код поставщика, что и в таблице ПОСТАВЩИК.

Например: имеем следующие таблицы ПОСТАВЩИК и ПОСТАВКА:

Таблица ПОСТАВЩИК:

Код поставщика	Имя	Город
100	Свобода	Москва
50	Апрель	Москва
75	Калина	Екатеринбург
200	Аист	Санкт-Петербург
215	Невская косметика	Санкт-Петербург

Таблица ПОСТАВКА:

Код поставщика	Код товара	Количество
215	20	100
100	15	1000
200	40	500
75	10	1500
100	20	500
215	100	400
200	50	400

ИСС 1:

1,4

-1

3

2,6

0,5

ИСС 2

4

0

3

2

0

4

3

-1 в ИСС 1 означает, что данный поставщик в настоящее время не осуществляет поставок.

Если в таблицу ПОСТАВЩИК последней добавлена запись

120

Сувенир

Краснодар

То ИСС 1 изменится так:

ИСС 1:

1,4

-1

3

2,6

0,5

-1

ИСС 2 не изменится.

Если в таблицу ПОСТАВКА последней добавлена запись:

120

50

400

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

ИСС 1:

1,4

-1

3

2,6

0,5

7

ИСС 2

4
0
3
2
0
4
3
5

Если из таблицы ПОСТАВЩИК удалена запись с кодом поставщика 75, то таблица будет иметь вид:

Таблица ПОСТАВЩИК:

Код поставщика	Имя	Город
100	Свобода	Москва
50	Апрель	Москва
*	Калина	Екатеринбург
200	Аист	Санкт-Петербург
215	Невская косметика	Санкт-Петербург

Удаление поставщика требует для сохранения целостности базы данных автоматического удаления из таблицы ПОСТАВКА всех поставок этого поставщика. Согласно ИСС 1 поставка данного поставщика имеется только в строке 3 таблицы ПОСТАВКА (нумерация идет c0);

Таблица ПОСТАВКА:

Код поставщика	Код товара	Количество
215	20	100
100	15	1000
200	40	500
75	10	1500
100	20	500
215	100	400
200	50	400

Нужно пометить 2 строку в таблице ИСС1, 3 строки в ИСС 2 и в таблице ПОСТАВКА (нумерация идет с 0).

Таблица ПОСТАВКА:

Код поставщика	Код товара	Количество
215	20	100
100	15	1000
200	40	500
*	10	1500
100	20	500
215	100	400
200	50	400

ИСС 1:

1,4

-1

*

2,6

0,5

7

ИСС 2

4
0
3
*
0
4
3
5

Если поставщик поставляет несколько товаров, то в ИСС 1 в соответствующей строке будет несколько номеров. Например, поставщик 215 поставляет два товара, что отражено в ИСС 1. Надо будет записать в таблицу ПОСТАВКА в первую и четвертую строки символ * (нумерация идет с 0), в ИСС 1 на нулевой строке поставить *, а в ИСС 2 в первой и четвертой строке также поставить *.

Запрос, использующий две таблицы:

Найти имена поставщиков, поставляющих товар по заданному коду товара.

Сначала в инвертированном списке по коду товара для таблицы ПОСТАВКА методом деления отрезка пополам находим строку, в которой записан этот код.

Например, для таблицы ПОСТАВКА

Код поставщика	Код товара	Количество
215	20	100
100	15	1000
200	40	500
75	10	1500
100	20	500
215	100	400
200	50	400

Инвертированный список по коду товара будет:

10	3
15	1
20	0, 4
40	2
50	6
100	5

Если нас интересуют поставщики товара с кодом 20, то мы определим, что поставки этого товара записаны в строках 0 и 4 таблицы ПОСТАВКА. Если бы нас интересовали коды поставщиков или их количество, то ответ уже получен. Но нас интересуют имена поставщиков.

Обращаемся к ИСС 2 и выбираем информацию из 0 и 4 строк:

ИСС 2

4

0

3

2

0

4

3

Из таблицы ПОСТАВЩИК берем 4 и 0 строки:

Таблица ПОСТАВЩИК:

Код поставщика	Имя	Город
100	Свобода	Москва
50	Апрель	Москва
75	Калина	Екатеринбург
200	Аист	Санкт-Петербург
215	Невская косметика	Санкт-Петербург

Имена поставщиков “Невская косметика” и “Свобода”.