Find file
Fetching contributors…
Cannot retrieve contributors at this time
911 lines (764 sloc) 62.3 KB
\chapter{Практика: База данных для MP3}
\label{ch:27}
\thispagestyle{empty}
В~этой главе мы заново рассмотрим идею, впервые упомянутую в главе~\ref{ch:03},~--
пос\-трое\-ние базы данных, расположенной в памяти, на основе базовых типов данных Lisp.
Сейчас нашей целью является хранение информации, которую вы извлечёте из коллекции файлов
в формате MP3 при помощи библиотеки ID3v2 из главы~\ref{ch:25}. Вы затем будете
использовать эту базу данных в главах~\ref{ch:28} и~\ref{ch:29} как часть потокового
MP3-сервера с веб-интерфейсом. Конечно, сейчас вы уже можете использовать некоторые из
языковых конструкций, известных со времени изучения главы~\ref{ch:03}, чтобы создать более
совершенный код.
\section{База данных}
Основной проблемой базы данных из главы~\ref{ch:03} является то, что есть только одна
таблица~-- список, сохранённый в переменной \lstinline{*db*}. Другой проблемой является то,
что код ничего не знает о типах значений, сохранённых в разных колонках. В
главе~\ref{ch:03} вы просто использовали функцию общего назначения \lstinline{EQUAL} для
сравнения значений в колонках при выборе строк из базы данных, но у вас были бы проблемы,
если бы вы хотели сохранить значения, которые не сравниваются с помощью\lstinline{EQUAL},
или если бы вы хотели сортировать строки в базе данных, поскольку нет такой функции
сравнения, похожей на \lstinline{EQUAL}.
Сейчас вы будете решать обе проблемы путём определения класса \lstinline{table}, который будет
описывать отдельные таблицы базы данных. Каждый экземпляр класса \lstinline{table} будет
состоять из двух слотов: один~-- для хранения данных, а второй~-- для хранения информации о
колонках таблицы, которую смогут использовать функции для работы с базой данных. Класс
выглядит примерно вот так:
\begin{myverb}
(defclass table ()
((rows :accessor rows :initarg :rows :initform (make-rows))
(schema :accessor schema :initarg :schema)))
\end{myverb}
Так же как и в главе~\ref{ch:03}, вы можете представлять отдельные строки в виде списков
свойств, но сейчас вы создадите абстракцию, которая позволит вам изменять внутренее
представление без особых трудностей. И в данной версии вы будет сохранять данные в
векторе, а не в списке свойств, поскольку некоторые операции, которые вы будете
поддерживать, например произвольный доступ к строкам по числовому индексу и возможность
сортировки таблицы, могут быть более эффективно реализованы с помощью векторов.
\begin{lrbox}{\chtwosevenone}
\begin{minipage}{\linewidth}
\begin{myverb}
(defpackage :com.gigamonkeys.mp3-database
(:use :common-lisp
:com.gigamonkeys.pathnames
:com.gigamonkeys.macro-utilities
:com.gigamonkeys.id3v2)
(:export :*default-table-size*
:*mp3-schema*
:*mp3s*
:column
:column-value
:delete-all-rows
:delete-rows
:do-rows
:extract-schema
:in
:insert-row
:load-database
:make-column
:make-schema
:map-rows
:matching
:not-nullable
:nth-row
:random-selection
:schema
:select
:shuffle-table
:sort-rows
:table
:table-size
:with-column-values))
\end{myverb}
\end{minipage}
\end{lrbox}
\textintable{Пакет}{Объявление пакета для разрабатываемого вами в этой главе кода будет
выглядеть следующим образом:\\[-3pt]
\noindent{}\usebox{\chtwosevenone}\\
Раздел \lstinline{:use} даёт возможность доступа к функциям и макросам, чьи имена
экспортированы из пакетов, созданных в главах~\ref{ch:15}, \ref{ch:08} и~\ref{ch:25}, а
секция \lstinline{:export} используется для объявления функций, реализуемых данным пакетом,
которые будут использоваться в главе~\ref{ch:29}.
}
Функция \lstinline{make-rows}, используемая для инициализации слота \lstinline{rows}, может быть
прос\-той обёрткой для функции \lstinline{MAKE-ARRAY}, которая создаёт пустой вектор с изменяемым
размером и указателем заполнения.
\begin{myverb}
(defparameter *default-table-size* 100)
(defun make-rows (&optional (size *default-table-size*))
(make-array size :adjustable t :fill-pointer 0))
\end{myverb}
Для представления схемы таблицы вам необходимо определить ещё один класс~--
\lstinline{column}, каждый экземпляр которого будет содержать информацию об одной колонке в
таблице: её название, способ сравнения значений в колонке на равенство и порядок
расположения, значение по умолчанию, а также функцию, которая будет использоваться для
нормализации значения при вставке данных в таблицу и при запросе данных из таблицы. Слот
\lstinline{schema} будет хранить список объектов типа \lstinline{column}. Определение класса будет
выглядеть примерно вот так:
\begin{myverb}
(defclass column ()
((name
:reader name
:initarg :name)
(equality-predicate
:reader equality-predicate
:initarg :equality-predicate)
(comparator
:reader comparator
:initarg :comparator)
(default-value
:reader default-value
:initarg :default-value
:initform nil)
(value-normalizer
:reader value-normalizer
:initarg :value-normalizer
:initform #'(lambda (v column) (declare (ignore column)) v))))
\end{myverb}
Слоты \lstinline{equality-predicate} и \lstinline{comparator} объекта \lstinline{column} хранят функции,
которые будут использоваться для сравнения значений данной колонки на равенство и порядок
расположения. Например, для колонки, которая будет хранить строковые значения, мы можем
использовать функции \lstinline{STRING=} в качестве значения \lstinline{equality-predicate} и
\lstinline{STRING<} для \lstinline{comparator}, тогда как колонки, хранящие числа, могут
использовать функции \lstinline{=} и \lstinline!<!.
Слоты \lstinline{default-value} и \lstinline{value-normalizer} используются при вставке и при
запросе данных (слот \lstinline{value-normalizer}). Когда вы вставляет строку в базу данных и
для определённой колонки не указано значение, то вы можете использовать значение,
хранящееся в слоте \lstinline{default-value} данной колонки. Затем значение (значение по
умолчанию или указанное пользователем) нормализуется путём передачи его и объекта,
описывающего колонку в БД, в качестве параметров функции, указанной в слоте
\lstinline{value-normalizer}. Вы передаёте объект типа \lstinline{column}, поскольку для функции
\lstinline{value-normalizer} могут понадобиться некоторые данные, связанные с объектом
\lstinline{column}. (Вы увидите пример такого использования в следующем разделе.) Вы также
должны нормализовывать значения, передаваемые в запросах, до их сравнения с объектами в
базе данных.
Таким образом, \lstinline{value-normalizer} отвечает за возврат значения, которое может быть
спокойно передано функциям \lstinline{equality-predicate} и \lstinline{comparator}. Если
\lstinline{value-normalizer} не может найти подходящее возвращаемое значение, то она
сгенерирует ошибку.
Другой причиной для нормализации значений до их сохранения в БД является возможность
уменьшить потребление памяти и процессора. Например, если у вас есть колонка, которая
должна хранить строковые значения, но количество значений, которые будут сохранены,
является ограниченным~-- например, колонка \lstinline{genre} (жанр) в базе данных
MP3-файлов,~-- то вы можете уменьшить потребление памяти и увеличить скорость работы путём
использования функции \lstinline{value-normalizer} для интернирования (intern) строк
(преобразовать все вызовы \lstinline{STRING=} к одному объекту-строке). Так что вам нужно
будет иметь столько строковых объектов, сколько у вас имеется различающихся строк, вне
зависимости от того, сколько строк у вас в таблице, и вы тогда сможете использовать для
сравнения функцию \lstinline{EQL}, а не \lstinline{STRING=}, которая является более
медленной\footnote{Общим основанием для интернирования объектов явялется то, что когда вам
нужно сравнивать определённое значение много раз, то стоит выполнить его интернирование,
несмотря на некоторые затраты на эту операцию. Функция\lstinline{value-normalizer}
запускается один раз, когда вы вставляете значение, и, как вы увидите далее, один раз в
начале каждого запроса. Поскольку запрос может приводить к выполнению
\lstinline{equality-predicate} для каждой из строк таблицы, то общие затраты на
интернирование значений быстро приближаются к нулю.}\hspace{\footnotenegspace}.
\section{Определение схемы базы данных}
Таким образом, чтобы создать экземпляр таблицы, вам необходимо создать список объектов
\lstinline{column} objects. Вы можете создать такой список вручную, используя функции
\lstinline{LIST} и \lstinline{MAKE-INSTANCE}. Но вы скоро заметите, что вы часто создаёте множество
объектов \lstinline{column} с одинаковыми комбинациями функций \lstinline{comparator} и
\lstinline{equality-predicate}. Это происходит от того, что комбинация функций сравнения по
существу определяет тип колонки. Было бы хорошо, если бы был способ определить имена для
этих типов, что позволит вам просто указывать, что конкретная колонка является строковой,
вместо того чтобы указывать \lstinline{STRING<} и \lstinline{STRING=} в качестве функций сравнения.
Одним из способов решения этой проблемы является определение обобщённой функции
\lstinline{make-column}, например вот так:
\begin{myverb}
(defgeneric make-column (name type &optional default-value))
\end{myverb}
Теперь вы можете определять методы данной обобщённой функции, специализированные для типа,
с использованием \lstinline{EQL}, которые будут возвращать объекты \lstinline{column} со слотами,
заполненными соответствующими значениями. Вот определения для методов, которые определяют
типы колонок с именами \lstinline{string} и \lstinline{number}:
\begin{myverb}
(defmethod make-column (name (type (eql 'string)) &optional default-value)
(make-instance
'column
:name name
:comparator #'string<
:equality-predicate #'string=
:default-value default-value
:value-normalizer #'not-nullable))
(defmethod make-column (name (type (eql 'number)) &optional default-value)
(make-instance
'column
:name name
:comparator #'<
:equality-predicate #'=
:default-value default-value))
\end{myverb}
Следующая функция~-- \lstinline{not-nullable},~-- используется в качестве значения
\lstinline{value-normalizer} для строковых колонок и просто возвращает переданное значение для
всех случаев, кроме тех, когда ей передают значение \lstinline{NIL}, когда она сигнализирует об
ошибке:
\begin{myverb}
(defun not-nullable (value column)
(or value (error "Column ~a can't be null" (name column))))
\end{myverb}
Это важно, поскольку вызовы \lstinline{STRING<} и \lstinline{STRING=} будут выдавать ошибку, если им
будет передан \lstinline{NIL}; лучше перехватить неправильные значения до того, как они будут
вставлены в таблицу, а не тогда, когда мы будем их использовать\footnote{Как всегда, в
книгах по программированию правильная обработка ошибок является поводом для сокращения;
при разработке в реальных условиях вы, скорее всего, определите специальный тип ошибки и
будете использовать его вместо стандартного:
\begin{myverb}
(error 'illegal-column-value :value value :column column)
\end{myverb}
Затем вы можете подумать о том, где вы можете добавить код перезапуска, который позволит
вам восстановить последствия такой ошибки. И в заключение, в почти любом приложении, вы
должны установить обработчики событий, которые позволят выбрать соответствующий код
перезапуска.}\hspace{\footnotenegspace}.
Еще одним типом колонки, который понадобится для базы данных MP3, является
\lstinline{interned-string}, чьи значения интернируются, как это обсуждалось выше. Поскольку
вам нужна хэш-таблица, в которую вы будете интернировать значения, вы должны определить
подкласс \lstinline{column}~-- \lstinline{interned-values-column}, который добавит ещё один слот,
чьим значением будет хэш-таблица, которая будет использоваться для интернирования.
Для реализации интернирования вам потребуется указать в качестве \lstinline{:initform} для
слота \lstinline{value-normalizer} функцию, которая будет интернировать значение в хэш-таблицу,
которая хранится в колонке \lstinline{interned-values}. И поскольку одна из самых главных
причин интенирования значений~-- возможность использования \lstinline{EQL} в качестве функции
равенства, то вы также должны добавить \lstinline!#'eql! в качестве значения \lstinline{:initform}
для слота \lstinline{equality-predicate}.
\begin{myverb}
(defclass interned-values-column (column)
((interned-values
:reader interned-values
:initform (make-hash-table :test #'equal))
(equality-predicate :initform #'eql)
(value-normalizer :initform #'intern-for-column)))
(defun intern-for-column (value column)
(let ((hash (interned-values column)))
(or (gethash (not-nullable value column) hash)
(setf (gethash value hash) value))))
\end{myverb}
Затем вы можете определить метод \lstinline{make-column}, специализированный для имени
\lstinline{interned-string}, который будет возвращать экземпляр \lstinline{interned-values-column}.
\begin{myverb}
(defmethod make-column (name (type (eql 'interned-string)) &optional default-value)
(make-instance
'interned-values-column
:name name
:comparator #'string<
:default-value default-value))
\end{myverb}
С помощью данных методов, определённых для \lstinline{make-column}, вы теперь можете определить
функцию \lstinline{make-schema}, которая создаёт список объектов типа \lstinline{column} из списка
описаний колонок, каждое из которых содержит имя колонки, имя типа колонки, и
необязательно, значение по умолчанию.
\begin{myverb}
(defun make-schema (spec)
(mapcar #'(lambda (column-spec) (apply #'make-column column-spec)) spec))
\end{myverb}
Например, с помощью следующего кода вы можете определить схему для таблицы, которая будет
использоваться для хранения данных, извлечённых из файлов MP3:
\begin{myverb}
(defparameter *mp3-schema*
(make-schema
'((:file string)
(:genre interned-string "Unknown")
(:artist interned-string "Unknown")
(:album interned-string "Unknown")
(:song string)
(:track number 0)
(:year number 0)
(:id3-size number))))
\end{myverb}
Чтобы создать саму таблицу для хранения информации о файлах MP3, вы должны передать
\lstinline{*mp3-schema*} в качестве аргумента \lstinline{:schema} функции \lstinline{MAKE-INSTANCE}.
\begin{myverb}
(defparameter *mp3s* (make-instance 'table :schema *mp3-schema*))
\end{myverb}
\section{Вставка значений}
Сейчас вы готовы к тому, чтобы определить вашу первую операцию для работы с таблицами~--
\lstinline{insert-row}, которая получает список свойств (plist) имён и значений и таблицу,
добавляет строку к таблице. Большая часть работы выполняется в дополнительной функции
\lstinline{normalize-row}, которая создаёт список свойств для всех колонок таблицы, используя
нормализованные значения и значения по умолчанию, которые получаются из слотов
\lstinline{names-and-values}, если значение было указано, или \lstinline{default-value}, если
значение для конкретной колонки не было указано.
\begin{myverb}
(defun insert-row (names-and-values table)
(vector-push-extend (normalize-row names-and-values (schema table)) (rows table)))
(defun normalize-row (names-and-values schema)
(loop
for column in schema
for name = (name column)
for value = (or (getf names-and-values name) (default-value column))
collect name
collect (normalize-for-column value column)))
\end{myverb}
Создание дополнительной функции \lstinline{normalize-for-column}, которая получает значение и
объект \lstinline{column} и возвращает нормализованное значение, оправдано тем, что вам будет
проводить нормализацию значений при запросах к таблице.
\begin{myverb}
(defun normalize-for-column (value column)
(funcall (value-normalizer column) value column))
\end{myverb}
Теперь вы готовы к объединению кода базы данных с кодом из предыдущих глав, чтобы
построить базу данных, содержащую информацию, выделенную из файлов MP3. Вы можете
определить функцию \lstinline{file->row}, которая будет использовать функцию \lstinline{read-id3} из
библиотеки \lstinline{ID3v2} для выделения тегов ID3 из файла и превращения их в список
свойств, который будет передан функции \lstinline{insert-row}.
\begin{myverb}
(defun file->row (file)
(let ((id3 (read-id3 file)))
(list
:file (namestring (truename file))
:genre (translated-genre id3)
:artist (artist id3)
:album (album id3)
:song (song id3)
:track (parse-track (track id3))
:year (parse-year (year id3))
:id3-size (size id3))))
\end{myverb}
Вам не нужно беспокоиться о нормализации значений, поскольку это будет сделано в
\lstinline{insert-row}. Однако вы должны сконвертировать строки, возвращённые функциями
\lstinline{track} и \lstinline{year}, в числа. Число \lstinline{track} (номер композиции)~-- это тег ID3,
который иногда сохраняется как число в виде строки и иногда как число, за которым следует
(через знак слэш) ещё одно число, обозначающее количество композиций в альбоме. Поскольку
нам нужен только номер композиции, то вы должны использовать аргумент \lstinline{:end} при
вызове функции \lstinline{PARSE-INTEGER}, для того чтобы указать что разбор должен
осуществляться только до знака слэш, если он есть\footnote{Если какой-то из файлов MP3
содержит неправильные данные в записях \lstinline{track} и \lstinline{year}, то
\lstinline{PARSE-INTEGER} может сигнализировать об ошибке. Один из способов обойти это
поведение~-- передать функции \lstinline{PARSE-INTEGER} параметр \lstinline{:junk-allowed}, равный
\lstinline{T}, который заставит функцию игнорировать любой <<мусор>>, который следует за
числом, и вернуть \lstinline{NIL}, если число не было найдено в строке. Или если вы хотите
попрактиковаться в использовании системы условий и перезапусков, то можете определить
специальное значение \lstinline{error} и использовать его в качестве сигнала из этих функций,
в том случае если данные неправильно оформлены, а также установить несколько точек
перезапуска, чтобы позволить этим функциям обработать данные ошибки.}\hspace{\footnotenegspace}.
\begin{myverb}
(defun parse-track (track)
(when track (parse-integer track :end (position #\/ track))))
(defun parse-year (year)
(when year (parse-integer year)))
\end{myverb}
В~заключение вы можете собрать все эти функции вместе с \lstinline{walk-directory} из
библиотеки переносимых имён файлов, а также функцией \lstinline{mp3-p} из библиотеки
\lstinline{ID3v2}, чтобы определить функцию, которая загружает в базу данных MP3 информацию,
извлечённую из файлов MP3, которые были найдены в определённом каталоге (и всех его
подкаталогах).
\begin{myverb}
(defun load-database (dir db)
(let ((count 0))
(walk-directory
dir
#'(lambda (file)
(princ #\.)
(incf count)
(insert-row (file->row file) db))
:test #'mp3-p)
(format t "~&В~базу данных загружено ~d файлов." count)))
\end{myverb}
\section{Выполнение запросов к базе данных}
После того как загрузите данные в базу данных, вам необходимо найти способ выполнять
запросы к ней. Для приложения, работающего с файлами MP3, вам понадобятся более сложные
функции выполнения запросов, чем те, которые были использованы в главе~\ref{ch:03}. Сейчас
вам нужна не только возможность извлекать строки, отвечающие определённым критериям, но
также и возможность делать выборку только определённых колонок и, возможно, сортировать
строки по определённой колонке. В~соответствии с теорией реляционных баз данных
результатом запроса будет новая таблица, содержащая строки и колонки.
В~качестве образца для функции выполнения запросов~-- \lstinline{select}, был взят оператор
\lstinline{SELECT} из языка SQL. Эта функция принимает пять именованных параметров:
\lstinline{:from}, \lstinline{:columns}, \lstinline{:where}, \lstinline{:distinct} и \lstinline{:order-by}.
Аргумент \lstinline{:from} указывает объект \lstinline{table}, для которого вы хотите выполнить
запрос. Аргумент \lstinline{:columns} указывает то, какие колонки должны быть включены в
результат. В~качестве значения должен быть указан список имён колонок, имя одной колонки
или \lstinline{T} (значение по умолчанию), указывающее, что должны быть включены все колонки.
Аргумент \lstinline{:where} (если он указан), должен быть функцией, которая получает строку и
возвращает истинное значение, если эта строка должна быть включена в результаты. Немного
спустя вы напишете две функции~-- \lstinline{matching} и \lstinline{in}, которые возвращают
функции, допустимые для использования в качестве аргумента \lstinline{:where}. Аргумент
\lstinline{:order-by} (если он указан) должен быть списком имён колонок; результаты будут
отсортированы по соответствующим колонкам. Так же как и для аргумента \lstinline{:columns}, вы
можете указать лишь одну колонку, просто используя её имя, что эквивалентно списку из
одного элемента. В~заключение аргумент \lstinline{:distinct} является логическим значением,
которое указывает, должны ли мы удалять дублирующиеся строки из результата. Значением
по умолчанию для \lstinline{:distinct} является \lstinline{NIL}.
Вот несколько примеров использования \lstinline{select}:
\begin{myverb}
;; Выбрать все строки где колонка :artist равна "Green Day"
(select :from *mp3s* :where (matching *mp3s* :artist "Green Day"))
;; Получить отсортированный список артистов, исполняющих песни в жанре "Rock"
(select
:columns :artist
:from *mp3s*
:where (matching *mp3s* :genre "Rock")
:distinct t
:order-by :artist)
\end{myverb}
Реализация \lstinline{select} вместе со вспомогательными функциями выглядит примерно так:
\begin{myverb}
(defun select (&key (columns t) from where distinct order-by)
(let ((rows (rows from))
(schema (schema from)))
(when where
(setf rows (restrict-rows rows where)))
(unless (eql columns 't)
(setf schema (extract-schema (mklist columns) schema))
(setf rows (project-columns rows schema)))
(when distinct
(setf rows (distinct-rows rows schema)))
(when order-by
(setf rows (sorted-rows rows schema (mklist order-by))))
(make-instance 'table :rows rows :schema schema)))
(defun mklist (thing)
(if (listp thing) thing (list thing)))
(defun extract-schema (column-names schema)
(loop for c in column-names collect (find-column c schema)))
(defun find-column (column-name schema)
(or (find column-name schema :key #'name)
(error "No column: ~a in schema: ~a" column-name schema)))
(defun restrict-rows (rows where)
(remove-if-not where rows))
(defun project-columns (rows schema)
(map 'vector (extractor schema) rows))
(defun distinct-rows (rows schema)
(remove-duplicates rows :test (row-equality-tester schema)))
(defun sorted-rows (rows schema order-by)
(sort (copy-seq rows) (row-comparator order-by schema)))
\end{myverb}
Конечно, самыми интересными частями \lstinline{select} является реализация функций
\lstinline{extractor}, \lstinline{row-equality-tester} и \lstinline{row-comparator}.
Как вы можете заключить из того, как эти функции используются, каждая из этих функций
должна возвращать новую функцию. Например, функция \lstinline{project-columns} использует
значение, возвращённое функцией \lstinline{extractor} в качестве аргумента функции \lstinline{MAP}.
Поскольку \lstinline{project-columns} предназначена для возврата набора строк с только
определёнными значениями колонок, вы можете заключить, что \lstinline{extractor} возвращает
функцию, которая получает строку в качестве аргумента, и возвращает новую строку, которая
содержит только колонки, указанные в переданной ей схеме. Вот как мы можем реализовать
эту функцию:
\begin{myverb}
(defun extractor (schema)
(let ((names (mapcar #'name schema)))
#'(lambda (row)
(loop for c in names collect c collect (getf row c)))))
\end{myverb}
Отметьте то, как вы можете выполнить задачу по извлечению имён из схемы за пределами тела
замыкания: поскольку замыкание может быть вызвано несколько раз, вы захотите, чтобы в нем
выполнялось как можно меньше действий при каждом вызове.
Функции \lstinline{row-equality-tester} и \lstinline{row-comparator} реализуются аналогичным
образом. Для того чтобы принять решение о равенстве двух строк, вам необходимо применить
соответствующие функции сравнения каждой из колонок к значениям соответствующих колонок.
Из материала главы~\ref{ch:22} мы знаем, что \lstinline{LOOP} всегда возвращает \lstinline{NIL},
когда пара значений не проходит тест, в противном случае \lstinline{LOOP} вернёт \lstinline{T}.
\begin{myverb}
(defun row-equality-tester (schema)
(let ((names (mapcar #'name schema))
(tests (mapcar #'equality-predicate schema)))
#'(lambda (a b)
(loop for name in names and test in tests
always (funcall test (getf a name) (getf b name))))))
\end{myverb}
Расположение двух строк по порядку~-- более сложная задача. В~Lisp функции сравнения
возвращают истинное значение, если первый аргумент должен быть расположен перед вторым
аргументом, или \lstinline{NIL} в противном случае. Таким образом, \lstinline{NIL} может означать,
что второй аргумент должен быть расположен перед первым аргументом, или оба аргумента
равны. Мы также хотим, чтобы функции сравнения строк вели себя точно так же~-- возвращали
\lstinline{T}, если первая строка должна быть перед второй, и \lstinline{NIL} в противном случае.
Таким образом, для сравнения двух строк вы должны сравнить значения тех колонок, по
которым вы будете проводить сортировку, используя соответствующую функцию сравнения для
каждой из колонок. Сначала вызывается функция сравнения со значением из первой строки в
качестве первого аргумента. Если функция сравнения вернёт истинное значение, то это
означает, что первая колонка точно должна распологаться перед второй колонкой, так что вы
можете сразу вернуть значение \lstinline{T}.
Но если функция сравнения вернула \lstinline{NIL}, то вам нужно определить, почему это
произошло~-- либо второе значение должно быть поставлено перед первым, либо они равны. Так
что вам необходимо снова вернуть функцию сравнения, но поменять аргументы мес\-та\-ми. Если
функция сравнения вернёт истинное значение, то это означает, что вторая строка должна
стоять перед первой, и вы можете сразу вернуть \lstinline{NIL}. В~противном случае
значения в данной колонке равны, и вам необходимо перейти к следующей колонке. Если вы
проверите все колонки и не получите однозначного сравнения в пользу одной из строк, то эти
строки равны, и вы должны вернуть \lstinline{NIL}. Функция, которая реализует такой
алгоритм, будет выглядеть следующим образом:
\begin{myverb}
(defun row-comparator (column-names schema)
(let ((comparators (mapcar #'comparator (extract-schema column-names schema))))
#'(lambda (a b)
(loop
for name in column-names
for comparator in comparators
for a-value = (getf a name)
for b-value = (getf b name)
when (funcall comparator a-value b-value) return t
when (funcall comparator b-value a-value) return nil
finally (return nil)))))
\end{myverb}
\section{Функции отбора}
Аргумент \lstinline{:where} функции \lstinline{select} может быть любой функцией, которая принимает
в качестве аргумента строку и возвращает истинное значение, если она должна быть включена
в результаты. Однако на практике вам редко понадобится вся мощь вручную написанного кода
для выражения критериев запроса. Так что вы должны лишь реализовать две функции:
\lstinline{matching} и \lstinline{in}, которые будут создавать функции запроса, которые позволят вам
создавать общие виды запросов, а также возьмут на себя заботу об использовании
соответствующих функций равенства и нормализации для каждой из колонок.
Конструктором для \lstinline{query-function} будет функция \lstinline{matching}, которая
возвращает функцию, которая будет сравнивать строку с конкретными значениями колонок. Вы
увидели, как она может быть использована в предыдущих примерах \lstinline{select}.
Например, такой вызов \lstinline{matching}:
\begin{myverb}
(matching *mp3s* :artist "Green Day")
\end{myverb}
\noindent{}вернёт функцию, которая будет выбирать строки, в которых значение колонки \lstinline{:artist}
равно \lstinline{"Green Day"}. Вы также можете передавать множество имён колонок и
значений~-- возвращаемая функция будет возвращать истинное значение только тогда, когда
все колонки имеют заданные значения. Например, следующий вызов вернёт замыкание, которое
будет принимать строки, в которых артист равен \lstinline{"Green Day"} и альбом равен
\lstinline{"American Idiot"}:
\begin{myverb}
(matching *mp3s* :artist "Green Day" :album "American Idiot")
\end{myverb}
Вам необходимо передать функции \lstinline{matching} объект \lstinline{table}, поскольку функции
необходим доступ к схеме таблицы для получения функций сравнения и нормализации для тех
колонок, для которых выполняется отбор данных.
Вы строите функцию, возвращаемую функцией \lstinline{matching} из меньших функций, каждая из
которые отвечает за проверку значения одной из колонок. Для того чтобы создать эти
функции, вы должны определить функцию \lstinline{column-matcher}, которая получает объект
\lstinline{column} и ненормализованное значение и возвращает функцию, которая получает строку
и возвращает истинное значение в том случае, если значение заданной колонки соответствует
нормализованному значению заданного аргумента.
\begin{myverb}
(defun column-matcher (column value)
(let ((name (name column))
(predicate (equality-predicate column))
(normalized (normalize-for-column value column)))
#'(lambda (row) (funcall predicate (getf row name) normalized))))
\end{myverb}
Затем вы создаёте список функций \lstinline{column-matching} для заданных имён и значений,
переданных функции \lstinline{column-matchers}:
\begin{myverb}
(defun column-matchers (schema names-and-values)
(loop for (name value) on names-and-values by #'cddr
when value collect
(column-matcher (find-column name schema) value)))
\end{myverb}
Теперь вы можете реализовать \lstinline{matching}. Снова заметьте, что вы делаете как можно
больше работы за пределами замыкания, чтобы выполнить эти операции один раз при создании
замыкания, а не при его вызове для каждой из строк таблицы.
\begin{myverb}
(defun matching (table &rest names-and-values)
"Build a where function that matches rows with the given column values."
(let ((matchers (column-matchers (schema table) names-and-values)))
#'(lambda (row)
(every #'(lambda (matcher) (funcall matcher row)) matchers))))
\end{myverb}
Эта функция выглядит как небольшой клубок замыканий, но стоит пристальней посмотреть на
неё, для того чтобы получить <<наслаждение>> от возможности программирования с функциями
как объектами первого класса.
Задачей \lstinline{matching} является возврат функции, которая будет выполняться для каждой
строки в таблице, для того чтобы определить, должна ли эта строка быть включена в
результат или нет. Так что функция \lstinline{matching} возвращает замыкание, принимающее один
параметр~-- строку \lstinline{row}.
Теперь вспомните, что функция \lstinline{EVERY} принимает фунцию-предикат в качестве первого
аргумента и возвращает истинное значение, только если функция будет возвращать истинное
значение для каждого из элементов списка, который передан \lstinline{EVERY} в качестве второго
аргумента. Однако в нашем случае список, переданный \lstinline{EVERY}, является списком
функций~-- функций отбора для конкретных колонок. Все, что вам нужно знать,~-- это то,
что каждая функция отбора колонки, при запуске для строки, для которой вы проводите
проверку, возвращает истинное значение. Так что в качестве функции-предиката для
\lstinline{EVERY} вы передаёте ещё одно замыкание, которое применит \lstinline{FUNCALL} к функции
отбора колонки, передав ей параметр \lstinline{row}.
Другой полезной функцией отбора является \lstinline{in}, которая возвращает функцию, которая
отбирает строки, где значение определённой колонки входит в заданный набор значений.
Функция \lstinline{in} будет принимать два аргумента~-- имя колонки и таблицу, которая
содержит значения, с которыми вы будете сравнивать. Предположим, например, что вы хотите
найти все песни в базе данных MP3, у которых названия совпадают с названиями песен,
исполняемых \textit{Dixie Chicks}. Вы можете написать это выражение \lstinline{where},
используя функцию \lstinline{in} и вспомогательный запрос, например вот так\footnote{Этот
запрос также вернёт вам все песни, исполненяемые \textit{Dixie Chicks}. Если вы захотите
ограничить этот запрос, чтобы он содержал только артистов, отличных от \textit{Dixie
Chicks}, то вам нужна более сложная функция \lstinline{:where}. Поскольку аргументом
\lstinline{:where} может быть любая функция, то это можно сделать; вы можете удалить
собственные песни \textit{Dixie Chicks}' с помощью вот такого запроса:
\begin{myverb}
(let* ((dixie-chicks (matching *mp3s* :artist "Dixie Chicks"))
(same-song (in :song (select :columns :song :from *mp3s* :where dixie-chicks)))
(query #'(lambda (row) (and (not (funcall dixie-chicks row))
(funcall same-song row)))))
(select :columns '(:artist :song) :from *mp3s* :where query))
\end{myverb}
Однако это не особо удобно. Если вы пишете приложение, которому требуется выполнять много
сложных запросов, то вы можете захотеть придумать более выразительный язык запросов.}\hspace{\footnotenegspace}:
\begin{myverb}
(select
:columns '(:artist :song)
:from *mp3s*
:where (in :song
(select
:columns :song
:from *mp3s*
:where (matching *mp3s* :artist "Dixie Chicks"))))
\end{myverb}
Хотя запросы более сложные, но реализация \lstinline{in} намного проще, чем реализация
\lstinline{matching}.
\begin{myverb}
(defun in (column-name table)
(let ((test (equality-predicate (find-column column-name (schema table))))
(values (map 'list #'(lambda (r) (getf r column-name)) (rows table))))
#'(lambda (row)
(member (getf row column-name) values :test test))))
\end{myverb}
\section{Работа с результатами выполнения запросов}
Поскольку \lstinline{select} возвращает другую таблицу, вам необходимо немного подумать о том,
как вы будете осуществлять доступ к отдельным значениям. Если вы уверены, что никогда
не измените способ представления данных в таблице, то вы можете просто сделать структуру
таблицы частью API и указать, что класс \lstinline{table} имеет слот \lstinline{rows}, который
является вектором, содержащим списки свойств, и для доступа к данным в таблице использовать
стандартные функции Common Lisp для работы с векторами и списками свойств. Но
представление данных~-- это внутренняя деталь, которую вы можете захотеть изменить.
Также вы можете не захотеть, чтобы другие разработчики напрямую работали с данными,
например вы можете захотеть, чтобы никто не мог с помощью \lstinline{SETF} вставить в строку
ненормализованное значение. Так что хорошей идеей может быть определение нескольких
абстракций, которые будут обеспечивать нужные вам операции. Так что если вы захотите
изменить внутреннее представление данных, то вам нужно будет изменить только реализацию
этих функций и макросов. И хотя Common Lisp не позволяет вам полностью запретить доступ к
<<внутренним>> данным, путём предоставления официального API вы, по крайней мере, сможете
указать, где проходит граница, разграничивающая внешнее и внутреннее представления.
Вероятно, наиболее часто используемой операцией с результатами запроса будет итерация по
отдельным строкам и выделение значений конкретных колонок. Так что вам нужно
предоставить возможность для выполнения эти операций без прямого доступа к вектору строк
или использования \lstinline{GETF} для получения значения колонки внутри строки.
Реализация этих операций является тривиальной~-- данные функции являются лишь обертками
вокруг кода, который бы вы написали, если бы у вас не было этих абстракций. Вы можете
предоставить два способа итерации по строкам таблицы: макрос \lstinline{do-rows}, который
обеспечивает базовый способ организации циклов, и функцию \lstinline{map-rows}, которая создаёт
список, содержащий результаты применения заданной функции к каждой строке
таблицы\footnote{Версия \lstinline{LOOP}, реализованная в M.I.T., до стандартизации Common Lisp
включала механизм для расширения грамматики \lstinline{LOOP}, который бы позволял
реализовывать итерацию по новым структурам данных. Некоторые реализации Common Lisp,
которые унаследовали эту реализацию \lstinline{LOOP}, могут до сих пор иметь такую возможность,
что делает \lstinline{do-rows} и \lstinline{map-rows} не особо нужными.}\hspace{\footnotenegspace}.
\begin{myverb}
(defmacro do-rows ((row table) &body body)
`(loop for ,row across (rows ,table) do ,@body))
(defun map-rows (fn table)
(loop for row across (rows table) collect (funcall fn row)))
\end{myverb}
Для получения значения конкретной колонки внутри строки вы должны реализовать функцию
\lstinline{column-value}, которая будет принимать в качестве аргументов строку таблицы и
название колонки и будет возвращать соответствующее значение. Опять же, это лишь
тривиальная обертка вокруг кода, который бы вы и так написали. Но если вы позже измените
внутреннее представление данных, то пользователи \lstinline{column-value} не будут об этом
знать.
\begin{myverb}
(defun column-value (row column-name)
(getf row column-name))
\end{myverb}
Хотя \lstinline{column-value} является достаточной абстракцией доступа к значениям колонок, вам
довольно часто нужно получать одновременный доступ к значениям сразу нескольких колонок.
Так что мы реализуем макрос \lstinline{with-column-values}, который будет связывать набор
переменных со значениями, извлечёнными из строки, используя соответствующие именованные
параметры. Так что вместо использования такого кода:
\begin{myverb}
(do-rows (row table)
(let ((song (column-value row :song))
(artist (column-value row :artist))
(album (column-value row :album)))
(format t "~a by ~a from ~a~%" song artist album)))
\end{myverb}
\noindent{}вы можете просто написать следующим образом:
\begin{myverb}
(do-rows (row table)
(with-column-values (song artist album) row
(format t "~a by ~a from ~a~%" song artist album)))
\end{myverb}
И снова реализация не является очень сложной, если вы используете макрос \lstinline{once-only}
из главы~\ref{ch:08}.
\begin{myverb}
(defmacro with-column-values ((&rest vars) row &body body)
(once-only (row)
`(let ,(column-bindings vars row) ,@body)))
(defun column-bindings (vars row)
(loop for v in vars collect `(,v (column-value ,row ,(as-keyword v)))))
(defun as-keyword (symbol)
(intern (symbol-name symbol) :keyword))
\end{myverb}
И в заключение вы должны предоставить функции для получения количества строк в таблице, а
также для доступа к конкретной строке, используя числовой индекс.
\begin{myverb}
(defun table-size (table)
(length (rows table)))
(defun nth-row (n table)
(aref (rows table) n))
\end{myverb}
\section{Другие операции с базой данных}
И в заключение вы реализуете несколько дополнительных операций с базой данных, которые
будут использованы в главе~\ref{ch:29}. Первые две из них являются аналогами выражения
\lstinline{DELETE} языка SQL. Функция \lstinline{delete-rows} используется для удаления из таблицы
строк, соответствующих некоторому критерию. Так же как и \lstinline{select}, она принимает
именованные аргументы \lstinline{:from} и \lstinline{:where}. Но, в отличие от \lstinline{select}, эта
функция не возвращает новую таблицу~-- вместо этого она изменяет таблицу, переданную в
качестве аргумента the \lstinline{:from}.
\begin{myverb}
(defun delete-rows (&key from where)
(loop
with rows = (rows from)
with store-idx = 0
for read-idx from 0
for row across rows
do (setf (aref rows read-idx) nil)
unless (funcall where row) do
(setf (aref rows store-idx) row)
(incf store-idx)
finally (setf (fill-pointer rows) store-idx)))
\end{myverb}
В~интересах повышения производительности вы можете также реализовать отдельную функцию
для удаления всех строк из таблицы.
\begin{myverb}
(defun delete-all-rows (table)
(setf (rows table) (make-rows *default-table-size*)))
\end{myverb}
Оставшиеся функции для работы с базой данных не имеют аналогов среди операций с
реляционными базами данных, но они будут полезны при написании приложения, использующего
базу данных MP3. Первой среди них является функция, которая сортирует строки таблицы,
изменяя её.
\begin{myverb}
(defun sort-rows (table &rest column-names)
(setf (rows table) (sort (rows table) (row-comparator column-names (schema table))))
table)
\end{myverb}
С другой стороны, в приложении, работающем с базой данных MP3, вам может понадобиться
функция, которая перемешивает строки в таблице, используя функцию \lstinline{nshuffle-vector}
из главы~\ref{ch:23}.
\begin{myverb}
(defun shuffle-table (table)
(nshuffle-vector (rows table))
table)
\end{myverb}
И в заключение снова для приложения, работающего с базой данных MP3, вы должны реализовать
функцию, которая будет выбирать \lstinline{N} произвольных строк, возвращая результат в виде
новой таблицы. Эта функция также использует \lstinline{nshuffle-vector} вместе с версией
\lstinline{random-sample}, основанной на \textit{алгоритме~S} из книги <<Искусство
программирования>>, (т.2. Получисленные алгоритмы~-- 3 изд.) Дональда Кнута, который мы
обсуждали в главе~\ref{ch:20}.
\begin{myverb}
(defun random-selection (table n)
(make-instance
'table
:schema (schema table)
:rows (nshuffle-vector (random-sample (rows table) n))))
(defun random-sample (vector n)
"Based on Algorithm S from Knuth. TAOCP, vol. 2. p. 142"
(loop with selected = (make-array n :fill-pointer 0)
for idx from 0
do
(loop
with to-select = (- n (length selected))
for remaining = (- (length vector) idx)
while (>= (* remaining (random 1.0)) to-select)
do (incf idx))
(vector-push (aref vector idx) selected)
when (= (length selected) n) return selected))
\end{myverb}
Имея данный код, вы будете готовы создать (в главе~\ref{ch:29}) веб-интерфейс для
просмотра коллекции файлов в формате MP3. Но до этого вам необходимо реализовать часть
сервера, которая будет транслировать поток музыки в формате MP3, используя протокол
Shoutcast, что и является темой следующей главы.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pcl-ru"
%%% TeX-open-quote: "<<"
%%% TeX-close-quote: ">>"
%%% End: