Классика баз данных - статьи

       

Поиск в HTML-таблицах


Майкл Кафаррела и Элон Хэлеви

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

Первая задача WebTables состоит в получении высококачественных отношений при обходе Web. Процедура получения отношений состоит из двух шагов. На первом шаге WebTables отфильтровывает HTML-таблицы, не содержащие реляционных данных (например, таблицы, используемые для компоновки страниц). На втором шаге для таблиц, прошедших через реляционный фильтр, WebTables формирует метаданные схемы, такие как типы и имена столбцов. У разработчиков HTML нет возможности надежным образом указать, является ли таблица реляционной, или формально определить реляционные метаданные. Система WebTables должна полагаться на совокупность неявных подсказок. Например, в таблицах, используемых для компоновки страниц, часто содержатся очень длинные и насыщенные текстом ячейки, а таблицы с реляционными данными обычно содержат более короткие ячейки, не слишком различающиеся по длине. Аналогично, одним из признаков того, что разработчик таблицы вставил в нее «строку-заголовок», является то, что первая строка состоит только из строк символов, а у остальных строк столбцы имеют другие типы.

Вторая проблема проекта WebTables состоит в разработке средства запросов, обеспечивающего простой доступ более чем к сотне миллионов уникальных баз данных, обладающих более двумя миллионами уникальных схем.
Авторы создают «поисковую машину для структурированных данных», при использовании которой пользователи вводят текстовый поисковый запрос, и поисковая машина возвращает не список URL, а список баз данных, упорядоченный в порядке уменьшения релевантности. После того как пользователь выбрал релевантную базу данных, он может применить более традиционные средства структурированных запросов (такие как выборка, проекция и т.д.). Кроме того, поисковая машина может автоматически применить некоторые структурированные операции, не дожидаясь действий пользователя. Например, WebTables может проанализировать содержимое таблицы и попытаться сгенерировать ее некоторое наглядное представление, соответствующее данной предметной области и являющееся «интересным». Это представление отображается в результате запроса вслед за ссылкой на данную таблицу.

Наконец, в проекте WebTables совокупность восстановленных баз данных используется для построения ряда новых приложений. Пока разрабатываются два таких приложения. Первое из них – это автоматическое восполнение схемы (schema autocomplete). Пользователь вводит один или несколько желательных атрибутов данных (например, «name»), а приложение автоматически предлагает вариант оставшейся части схемы (например, «address», «city», «zip», «phone» и т.д.). Второе предложение – нахождение синонимов (synonym finding). Это средство автоматически определяет, какие имена атрибутов таблиц являются синонимами (например, «song» и «title», «telephone» и «tel-#»). Затем эти данные могут использоваться для улучшения сопоставления схем. Оба эти инструмента основываются на статистике использования имен атрибутов, вычисляемой на совокупности восстановленных баз данных.

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


Можно улучшить эффективность существующих шагов (например, точность восстановления отношений и качество ранжирования баз данных), расширить набор допустимых входных данных (обрабатывая не только простые HTML-таблицы, но также и HTML-списки и электронные таблицы Excel) и построить новые приложения (например, приложение, обеспечивающее варианты возможных данных, «вертикальный» аналог приложения автоматического восполнения схемы). Имеется также ряд вопросов, связанных с представлением Web, ориентированным на данные. Например, исследуется возможность автоматического нахождения соединений между структурированными данными, восстановленными из разных Web-страниц. Например, для нахождения информации о том, где находятся мировые лидеры, можно было бы соединить таблицу стран и их столиц с таблицей стран и их премьер-министров.

Проекты WebTables и Deep-Web Crawl являются частями более обширного исследования в областях пространств данных [] и интеграции неполных и неточных данных в качестве основы построения систем пространств данных. Некоторые ранние работы в этих областях описаны в [, , ].


Содержание раздела