III. Лабораторная работа 3. Инвертированные списки.

За основу должна быть взята одна из таблиц из курсового проекта [1].

Например, таблица КНИГА (шифр, автор, название книги, год_выпуска).

Заполненная таблица имеет вид :

Номер строки	Шифр	Автор	Название книги	Год_выпуска
0	900	Иванов А.	Дома и люди	2005
1	600	Эйдельман Н.	Первый декабрист	1990
2	300	Дёмин В.	Гиперборейские тайны.Т.1	2007
3	400	Кузьминская Т.	Моя жизнь дома и в ясной поляне	1987
4	500	Пыляев М.	Старая Москва	1990
5	200	Низовский А.	Зачарованные клады России	2007
Номер строки	Шифр	Автор	Название книги	Год_выпуска
6	700	Широкова Н.	Мифы кельтских народов	2004
7	800	Акунин Б.	Коронация	2005
8	100	Дёмин В.	Гиперборейсик тайны. Т.2	2007
9	1000	Акунин Б	Алмазная колесница	2003

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

Таким образом, инвертированный список по столбцу шифр будет таким:

Значение	Номера строк
100	8
200	5
300	2
400	3
500	4
600	1
700	6
800	7
900	0
1000	9

Поскольку шифр является ключом, то во втором столбце будет всегда один номер строки.

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

Значение	Номера строк
Акунин Б	7,9
Дёмин В.	2, 8
Иванов А.	0
Кузьминская Т.	3
Низовский А.	5
Пыляев М.	4
Широкова Н.	6
Эйдельман Н.	1

Инвертированный список по столбцу год_выпуска.

Значение	Номера строк
1987	3
1990	1,4
2003	9
2004	6
2005	0,7
2007	2,5,8

Во втором столбце, в общем случае, находится массив из номеров строк.

Можно в инвертированном списке записывать номер только первой строки в исходной таблице. Остальные строки в исходной таблице собираются в цепочку.

Например. Если создан инвертированный список по столбцу год_выпуска, то он будет таким:

Значение	Номера строк
1987	3
1990	1
2003	9
2004	6
2005	0
2007	2

А исходная таблица будет иметь вид:

	Шифр	Автор	Название книги	Год_выпуска	Цепочки одинаковых значений
0	900	Иванов А.	Дома и люди	2005	7
1	600	Эйдельман Н.	Первый декабрист	1990	4
2	300	Дёмин В.	Гиперборейские тайны.Т.1	2007	5
3	400	Кузьминская Т.	Моя жизнь дома и в ясной поляне	1987	-1
4	500	Пыляев М.	Старая Москва	1990	-1
5	200	Низовский А.	Зачарованные клады России	2007	8
6	700	Широкова Н.	Мифы кельтских народов	2004	-1
7	800	Акунин Б.	Коронация	2005	-1
8	100	Дёмин В.	Гиперборейские тайны. Т.2	2007	-1
9	1000	Акунин Б.	Алмазная колесница	2003	-1

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

Более подробно о такой организацией таблиц можно прочитать в [1].