Способ и система согласования схем баз данных web

Способ и система согласования схем баз данных web

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Описываемая технология в целом относится к определению схемы базы данных web.

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Всемирная паутина ("web") предоставляет значительные объемы информации, которая доступна через web-страницы. Web-страницы могут содержать либо статический контент (информационно значимое содержимое), либо динамический контент. Статический контент обычно относится к информации, которая может оставаться одинаковой по многим доступам к web-страницам. Динамический контент обычно относится к информации, которую хранят в базе данных web и добавляют к web-странице в ответ на поисковый запрос. Динамический контент представляет то, что упоминается как глубокая web или скрытая web.

Многие услуги поисковой машины дают возможность пользователям осуществлять поиск статического контента web. После того как пользователь подает поисковый запрос или запрос, который включает в себя поисковые термины, услуги поисковой машины идентифицируют web-страницы, которые могут быть связанными с этими поисковыми терминами. Эти web-страницы являются результатом поиска. Чтобы быстро идентифицировать связанные web-страницы, услуги поисковой машины могут поддерживать соответствие ключевых слов web-страницам. Это соответствие может быть сформировано посредством "ползания" (crawling, процесс автоматического подбора web-страниц в целях поиска) по web с целью идентификации ключевых слов каждой web-страницы. Для осуществления "ползания" по сети услуги поисковой машины могут использовать перечень корневых web-страниц для идентификации всех web-страниц, которые являются доступными через эти корневые web-страницы. Ключевые слова для любой конкретной web-страницы могут быть идентифицированы с использованием различных широко известных методик информационного поиска, например идентификация слов из заголовка, слов, поставляемых в метаданных web-страницы, выделенных слов и так далее.

Эти услуги поисковой машины, однако, обычно не предусматривают поиск динамического контента, который также считается контентом, в отношении которого отсутствует возможность осуществления "ползания". Одна проблема, связанная с поиском динамического контента, состоит в том, что является трудным или невозможным непосредственно получать схемы соответствующих баз данных web без взаимодействия с web-сайтом, который обеспечивает базу данных web. Схема задает информацию или атрибуты, которые хранятся в базе данных. Например, база данных web для продавца книг может содержать схему для каталога ее книг (то есть, базы данных web), которая включает в себя атрибут «заглавие» (title) и атрибут «автор» (author) для каждой книги. Без знания схемы услугам поисковой машины будет очень трудно осуществит "ползание" в отношении контента базы данных web, чтобы определить, какая информация является доступной для поиска. Даже если бы схема базы данных web была известна, услугам поисковой машины все равно потребовалось бы определять, как осуществить "ползание" в отношении базы данных web, чтобы извлечь ее контент. Предположив, что поисковая машина может извлекать контент из баз данных web, услугам поисковой машины все еще потребуется идентифицировать, когда атрибуты различных схем представляют семантически эквивалентные атрибуты. Например, web-сайты продавца книг могут содержать каталоги, которые описывают, является ли книга книгой в мягкой обложке, книгой в твердом переплете или компакт-диском. Web-сайт одного продавца книг может именовать этот атрибут "типом", а web-сайт другого продавца книг может именовать этот же самый атрибут "форматом". Чтобы предоставить возможность эффективного поиска динамического контента по многим web-сайтам, услуги поисковой машины должны понимать смысл или семантику атрибутов баз данных web.

Желательно иметь методику, которая позволила бы автоматически идентифицировать схемы, ассоциированные с базами данных web, и идентифицировать атрибуты различных схем, которые представляют семантически один и тот же контент.

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

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

ПЕРЕЧЕНЬ ЧЕРТЕЖЕЙ

Фиг.1 - схема, иллюстрирующая различные схемы базы данных web для продавца книг.

Фиг.2 - иллюстрация внутрисайтового и межсайтового согласования в одном варианте осуществления.

Фиг.3 - иллюстрация одного прохода разбиения системы согласования схем в одном варианте осуществления.

Фиг.4 - блок-схема, иллюстрирующая компоненты системы согласования схем в одном варианте осуществления.

Фиг.5 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента внутрисайтового согласования в одном варианте осуществления.

Фиг.6 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента формирования куба в одном варианте осуществления.

Фиг.7 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента обновления куба в одном варианте осуществления.

Фиг.8 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента проецирования куба в одном варианте осуществления.

Фиг.9 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента вычисления EMI в одном варианте осуществления.

Фиг.10 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента формирования матрицы соответствия в одном варианте осуществления.

Фиг.11 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента межсайтового согласования в одном варианте осуществления.

Фиг.12 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента вычисления оценки подобия векторов в одном варианте осуществления.

Фиг.13 - блок-схема последовательности операций, иллюстрирующая обработку данных для компонента перекрестной проверки в одном варианте осуществления.

ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Обеспечены способ и система идентификации схем баз данных web. В одном варианте осуществления система согласования схем формирует отображение между интерфейсной схемой и результирующей схемой базы данных web, которую используют для представления основной схемы базы данных. Интерфейсная схема базы данных web представляет атрибуты базы данных, которые могут использоваться для поиска. Результирующая схема базы данных web представляет атрибуты базы данных, которые выводятся на экран дисплея в качестве части результата поиска. Отображение указывает, какие интерфейсные атрибуты имеют тот же смысл (также называют «соответствует» или «совпадает»), что и результирующий атрибут. Система согласования схем также формирует отображение интерфейсных атрибутов и результирующих атрибутов базы данных web на глобальные атрибуты глобальной схемы, семантика которых известна. Используя эти отображения, услуги поисковой машины могут формулировать запросы с использованием глобальных атрибутов, отображать эти запросы на соответствующие интерфейсные атрибуты, подавать запрос и извлекать значения из результирующих атрибутов, которые соответствуют требуемым глобальным атрибутам. Таким образом, система согласования схем идентифицирует схемы базы данных web, которые могут использоваться для поиска по базе данных web.

На Фиг.1 показана блок-схема, на которой проиллюстрированы различные схемы базы данных web для продавца книг. База данных web включает в себя схему 101 базы данных, интерфейсную схему 102 и результирующую схему 103. Схема базы данных представляет основную схему базы данных web, которая в этом примере включает в себя атрибуты «заглавие», «автор», «издательство» (Publisher), «стандартный международный номер книги» (ISBN), «формат», и «дата публикации». Web-сайт обеспечивает web-страницу поиска так, чтобы пользователь мог посещать ее для поиска книг. Интерфейсная схема для этой базы данных web включает в себя атрибуты «заглавие», «автор», «формат» и «ISBN». Пользователь может задавать поисковые строки для любой комбинации интерфейсных атрибутов для поиска по базе данных книг. Поле "Ваш поиск" web-страницы дает возможность пользователю осуществлять поиск в пределах всех атрибутов базы данных web. Результат поиска выводят на экран на web-странице результата. Результирующая схема для этой базы данных web включает в себя «заглавие», «автор», «издательство», «формат» и «дата публикации». Результат поиска обычно будет предоставлять множество элементов для каждого элемента базы данных, соответствующего поисковому запросу. Каждый элемент результата обычно содержит значение для каждого из результирующих атрибутов. В этом примере интерфейсная схема содержит атрибут (то есть, ISBN), который не включен в результирующую схему, и результирующая схема содержит атрибут (то есть, «дата публикации»), который не включен в интерфейсную схему.

В дополнение к использованию для базы данных web интерфейсной схемы и результирующей схемы система согласования схем использует также глобальную схему, специфическую для конкретного домена. Глобальная схема для домена представляет набор атрибутов, которые являются общеиспользуемыми базами данных web внутри домена. Например, базы данных web в домене для книг обычно имеют атрибуты, которые включают в себя «заглавие», «автор» и «издательство», а базы данных web в домене для автомобилей обычно имеют атрибуты, которые включают в себя «наименование изготовителя», «модель» и «год». Глобальная схема также может иметь ассоциированные с ней типовые значения глобальных атрибутов. Например, атрибут «издательство» из домена книг может иметь значения глобального атрибута, которые включают в себя наименования издательств "Random House" и "MIT Press".

Чтобы сформировать отображения, система согласования схем первоначально идентифицирует глобальную схему для домена базы данных web и интерфейсную схему и результирующую схему базы данных web. (Способы идентификации этих схем описаны ниже). Система согласования схем формирует запросы на основе значений глобальных атрибутов (например, на основе типового набора значений) для глобальных атрибутов и подает эти запросы через интерфейсную web-страницу на базу данных web (например, посылая запрос по протоколу передачи гипертекста (HTTP), что соответствует подаче запроса через web-страницу поиска). Система согласования схем анализирует результат, представленный web-страницей результата, чтобы определить, какие интерфейсные атрибуты каким результирующим атрибутам соответствуют ("соответствие интерфейсный-результирующий"), какие глобальные атрибуты каким интерфейсным атрибутам соответствуют ("соответствие глобальный-интерфейсный") и какие глобальные атрибуты каким результирующим атрибутам соответствуют ("соответствие глобальный-результирующий"). Эти соответствия называют "внутрисайтовым" согласованием, поскольку интерфейсная и результирующая схемы соответствуют схемам одного web-сайта. Система согласования схем идентифицирует, что интерфейсный атрибут может соответствовать результирующему атрибуту, на основании того, что значение результирующего атрибута совпадает со значением интерфейсного атрибута, используемого при поиске. Например, если интерфейсному атрибуту «заглавие» задано значение "Harry Potter" (Гарри Поттер), то многие элементы результата будут вероятно иметь значение "Harry Potter" в результирующем атрибуте «заглавие». Напротив, если интерфейсному атрибуту «автор» задают для поиска значение "Harry Potter", только небольшое количество элементов результата будут, вероятно, иметь значение "Harry Potter" в интерфейсном атрибуте «заглавие». Как таковой, интерфейсный атрибут «заглавие», вероятно, соответствует результирующему атрибуту «заглавие», но интерфейсный атрибут «автор», вероятно, не соответствует результирующему атрибуту «заглавие».

В одном варианте осуществления система согласования схем может также формировать соответствия между интерфейсными схемами и результирующими схемами различных web-сайтов. Система согласования схем анализирует результаты запросов, поданных как описано выше, и идентифицирует, какие интерфейсные атрибуты схемы одного web-сайта каким интерфейсным атрибутам схемы другого web-сайта соответствуют ("соответствие интерфейсный-интерфейсный") и какие результирующие атрибуты схемы одного web-сайта каким результирующим атрибутам схемы другого web-сайта соответствуют ("соответствие результирующий-результирующий"). Например, система согласования схем может идентифицировать, что интерфейсный атрибут «тип» одного web-сайта может соответствовать интерфейсному атрибуту «формат» другого web-сайта. Эти соответствия называют "межсайтовым" согласованием, поскольку схемы согласовываются между различными web-сайтами. Информация о межсайтовом согласовании может использоваться при поиске нескольких баз данных web внутри домена. Информация о межсайтовом согласовании также может использоваться, чтобы оказывать помощь в проверке того, является ли внутрисайтовое согласование корректным.

На Фиг.2 проиллюстрировано внутрисайтовое и межсайтовое согласование в одном варианте осуществления. В овале 202 представлены схемы, относящиеся к базам данных web в домене для книг. Каждый из web-сайтов 1...N имеет интерфейсную схему ("IS") и результирующую схему ("RS"), и домен имеет глобальную схему ("GS"). Линии между представлениями схем представляют межсайтовое и внутрисайтовое согласование. Например, линия между IS web-сайта 1 и GS представляет внутрисайтовое соответствие глобальный-интерфейсный, линия между IS web-сайта 1 и RS web-сайта 1 представляет внутрисайтовое соответствие интерфейсный-результирующий, и линия между IS web-сайта 1 и IS web-сайта 2 представляет межсайтовое соответствие интерфейсный-интерфейсный между web-сайтом 1 и web-сайтом 2.

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

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

Таблица 1
	TitleGS	AuthorGS	PublisherGS	ISBNGS
AuthorIS	93	[498]	534	0
TitleIS	[451]	345	501	0
PublisherIS	62	184	[468]	2
KeywordIS (ключевое слово)	120	248	143	[275]
ISBNIS	0	0	0	258

Несмотря на то, что величина счета является показателем соответствия между парами атрибутов, относительная величина является более показательной для соответствия, чем абсолютная величина. В частности, большое значение счета вхождений может не представлять соответствующие атрибуты. Например, элемент матрицы для Author_IS и Publisher_GS (534) является наивысшим значением в матрице, но Author_IS и Publisher_GS семантически не соответствуют друг другу. В целом, для заданного конкретного элемента m_ij матрицы его относительная величина между всеми элементами для его интерфейсного атрибута i и глобального атрибута j более важна, чем его абсолютная величина. Например, Keyword_IS, который может включать в себя поле "ваш поиск" и который не является действительным атрибутом для домена книг, имеет подобную характеристику для всех глобальных атрибутов, что означает, что не может быть хорошего согласования для любого из глобальных атрибутов. Элемент Publisher_IS и Publisher_GS (468) не является наивысшим среди элементов для Publisher_GS. Однако он относительно больше других элементов для Publisher_IS.

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

в котором EMI является оценкой взаимной информации между i-м атрибутом схемы S_1i и j-м атрибутом S_2j, М является является и является Матрица EMI для матрицы вхождений согласно Таблицы 1 показана в Таблице 2.

Таблица 2
	TitleGS	AuthorGS	PublisherGS	ISBNGS
AuthorIS	-0,04	[0,11]	0,06	0,00
TitleIS	[0,19]	-0,03	-0,01	0,00
PublisherIS	-0,03	-0,02	[0,14]	-0,01
KeywordIS	-0,01	0,01	-0,07	0,17
ISBNIS	0,00	0,00	0,00	[0,32]

Система согласования схем определяет соответствие между атрибутами в случае, когда один элемент матрицы EMI больше других элементов для этого же интерфейсного атрибута (то есть в этой же строке), а также больше других элементов для этого же глобального атрибута (то есть в этом же столбце). Соответствующие атрибуты имеют большее перекрытие в содержимом информации (смысле информации) между собой, чем их перекрытие с другими атрибутами противоположной схемы, как показано посредством квадратных скобок. Например, элемент матрицы EMI для Author_IS и Author_GS (то есть 0,11) является наибольшим как для интерфейсных атрибутов «автор», так и глобальных атрибутов «автор», и он является корректным соответствием. Соответствие атрибутов представлено посредством нижеследующего уравнения:

= соответствие, если и

при этом MAP показывает, соответствует ли i-й атрибут схемы S₁ j-му атрибуту схемы S₂, и e_ij является элементом матрицы EMI для i-го атрибута схемы S₁ и j-го атрибута схемы S₂.

В одном варианте осуществления система согласования схем идентифицирует соответствия между атрибутами различных баз данных web. Система согласования схем идентифицирует соответствия на основании подобия векторов из соответствующих матриц вхождений для баз данных web. Например, Таблица 3 представляет таблицу вхождений глобальный-интерфейсный для схемы S₁, и Таблица 4 представляет таблицу вхождений глобальный-интерфейсный для схемы S₂. Глобальной схемой GS является {Title, Author, Publisher, ISBN}, интерфейсной схемой IS₁ для web-сайта 1 является {Author1, Title1, Publisher1, Keyword1, ISBN1} и интерфейсной схемой IS₂ для web-сайта 2 является {Title2, Author2, ISBN₂}.

Таблица 3
	TG	AG	PG	IG
A1	93	498	534	0
T1	451	345	501	0
P1	62	184	468	2
K1	120	248	143	275
I1	0	0	0	258

Таблица 4
	TG	AG	PG	IG
T2	166	177	118	0
A2(P)	39	331	406	0
I2	0	0	0	18

Атрибут A1 представлен вектором первой строки Таблицы 3, и атрибут A2 представлен вектором второй строки Таблицы 4. Система согласования схем вычисляет сходство двух атрибутов, используя нижеследующее уравнение:

в котором EVS является оценкой подобия векторов между i-м атрибутом схемы S₁ и j-м атрибутом схемы S₂, a_ik представляет значения матрицы вхождений для схемы S₁, и b_jk представляет значения матрицы вхождений для схемы S₂.

В Таблице 5 представлены оценки подобия векторов, выведенные на основании Таблицы 3 и Таблицы 4.

Таблица 5
	T2	A2(P)	I2
A1	0,84	[0,99]	0
T1	[0,96]	0,84	0
P1	0,71	0,95	0,01
K1	0,72	0,67	0,66
I1	0	0	[1,00]

Система согласования схем определяет соответствие между атрибутами в случае, когда один элемент матрицы EVS больше других элементов для того же интерфейсного атрибута одного web-сайта, а также больше других элементов для того же интерфейсного атрибута другого web-сайта. Квадратными скобками по Таблице 5 помечены наибольшие значения подобия и в ее строке, и в ее столбце, что также показывает корректное соответствие. Несмотря на то, что второй атрибут из IS₂, Author₂, некорректно сопоставлен с Publisher₂ из GS, система согласования схем использует межсайтовое согласование, чтобы внести исправление в соответствие.

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

В одном варианте осуществления система согласования схем аппроксимирует минимизацию среза ребер посредством использования начальных кластеров в качестве начального разбиения и перемещения вершин из одного кластера в другой до тех пор, пока количество сечений не уменьшится. Обычно вершину перемещают в кластер, в котором находятся большинство ее соседей. Соседние вершины между собой имеют ребро. Поскольку вершина должна быть перемещена, если перемещают многих из ее соседей, система согласования схем может использовать многократные проходы так, чтобы срез ребер сходился к локальному оптимуму. Если срез ребер сходится, система согласования схем разрешает межкластерное соответствие между атрибутами A_i web-сайта S₁ и B_j web-сайта S₂, содержащимися в двух кластерах C₁ и C₂, отбрасывая межкластерное соответствие и повторно устанавливая соответствие Ai с атрибутом Bk web-сайта S₂, который находится в кластере C₁, или наоборот.

На фиг.3 проиллюстрирован один проход разбиения системы согласования схемы в одном варианте осуществления. В этом примере глобальная схема содержит два атрибута {Author, Publisher}, и пять баз данных web содержат атрибуты IS IS₁={Aa}, IS₂={Ba,Bp}, IS₃={Ca,Cp}, IS₄={Da,Dp,} и IS₅={Ea,Ep}. Кластеры 301 и 302 иллюстрируют начальные кластеры атрибутов (представленные посредством вершин) на основе того, какому глобальному атрибуту они соответствуют (по внутрисайтовому согласованию), и ребра между парами атрибутов означают, что атрибуты соответствуют (по межсайтовому согласованию). В начальном состоянии атрибут A_a некорректно сопоставлен глобальному атрибуту Publisher и также некорректно сопоставлен B_p, в то же время он был корректно сопоставлен трем другим атрибутам в категории Author. Поэтому система согласования схем для уменьшения количества ребер перемещает A_a между кластерами из 3 в 1.

Перемещение исправляет согласующий атрибут Aa с Publisher на глобальный атрибут Author. После перемещения система согласования схем удаляет ребро между A_a и B_p и добавляет новое ребро между A_a и B_a (атрибут web-сайта 2, который сопоставлен глобальному атрибуту Author). Кластеры 311 и 312 представляют исправленные соответствия.

Глобальные схемы, интерфейсные схемы и результирующие схемы могут быть идентифицированы с использованием различных способов. Некоторые способы идентификации глобальных схем основываются на именах атрибутов и структуре элементов. (См. S. Castano, V. Antonellis and S. Vimercati. Global Viewing of Heterogeneous Data Sources. IEEE Trans. Data and Knowledge Eng., vol. 13, no. 2, 2001; и B. He, C.C. Chang. Statistical Schema Matching across Web Query Interfaces. Proc. ACM SIGMOD Conf, 2003, которые тем самым включены в настоящее описание путем ссылки.) Другие способы основываются на формальных онтологиях. (См. B. He, C.C. Chang. Statistical Schema Matching across Web Query Interfaces. Proc. ACM SIGMOD Conf, 2003; и F. Hakimpour, A. Geppert. Global Schema Generation Using Formal Ontologies. Proc. 21st Conf. on Conceptual Modeling, 2002, которые тем самым включены в настоящее описание путем ссылки). Типовые значения глобальных атрибутов могут быть собраны из различных типовых баз данных web или сформированы вручную. Интерфейсная схема базы данных web может быть идентифицирована на основании относящихся к вводу данных тегов (неотображаемых элементов разметки), web-страницы запроса, как определено спецификацией языка гипертекстовой разметки (HTML). Некоторые способы идентификации результирующей схемы формируют объекты-оболочки, чтобы извлекать содержимое вложенных полуструктурированных данных из динамических, формируемых по шаблону web-страниц. (См. A. Arasu, H. Garcia-Molina. Extracting Structured Data from Web Pages. Proc. ACM SIGMOD Conf., 2003; C.H. Chang, S.C. Lui. IEPAD: Information Extraction based on Pattern Discovery. Proc. 10th World Wide Web Conf, 681-688, 2001; V. Crescenzi, G. Mecca P. Merialdo. ROADRUNNER: Towards Automatic Data Extraction from Large Web Sites. Proc. 27th VLDB. Conf, 109-118, 2001; и J. Wang, F. Lochovsky. Data Extraction and Label Assignment for Web Databases. Proc. 12th World Wide Web Conf, 187-196, 2003, которые тем самым включены в настоящее описание путем ссылки). Один способ формирует объект-оболочку регулярного выражения на основании вложенного обнаружения повторяемого образа в страницах HTML. (См. J. Wang, F. Lochovsky. Data Extraction and Label Assignment for Web Databases. Proc. 12^th World Wide Web Conf., 187-196, 2003, которое тем самым включено в настоящее описание путем ссылки). Специалист в данной области техники оценит тот факт, что каждая из этих схем также может быть идентифицирована вручную или комбинацией ручного и автоматизированного средств.

На фиг.4 показана блок-схема, на которой в одном варианте осуществления проиллюстрированы компоненты системы согласования схем. Система 410 согласования схем соединена с различными сайтами 401 баз данных web через линию связи 402. Система согласования схем включает в себя компонент 411 внутрисайтового согласования, компонент 412 межсайтового согласования, компонент 413 перекрестной проверки, компонент 414 формирования куба, компонент 415 проецирования куба, компонент 416 вычисления EMI и компонент 417 формирования матрицы соответствий. Система согласования схем также включает в себя хранилище 421 куба, хранилище 422 проекций, хранилище 423 EMI и хранилище 424 соответствий. Компонент внутрисайтового согласования вызывает компонент формирования куба, чтобы сформировать куб вхождений. и вызывает компонент проецирования куба, чтобы сформировать матрицы вхождений глобальный-интерфейсный, глобальный-результирующий и интерфейсный-результирующий. Компонент внутрисайтового согласования вызывает также компонент вычисления EMI, чтобы вычислить оценку взаимной информации на основании матриц вхождений, и вызывает компонент формирования матрицы соответствий, чтобы идентифицировать, какие пары атрибутов соответствуют. Компонент межсайтового согласования использует матрицы вхождений, чтобы вычислить оценку подобия векторов, и вызывает компонент формирования матрицы соответствий, чтобы идентифицировать соответствия. Компонент перекрестной проверки изменяет соответствие для атрибутов, которые выявляются согласованными некорректно. Хранилище куба содержит кубы вхождений, хранилище проекций содержит матрицы вхождений, хранилище EMI содержит матрицы EMI и хранилище соответствий содержит матрицы соответствий.

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

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

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

На фиг.5 показана блок-схема последовательности операций, на которой проиллюстрирована работа для компонента внутрисайтового согласования в одном варианте осуществления. Компонент идентифицирует соответствия глобальный-интерфейсный, глобальный-результирующий и интерфейсный-результирующий для базы данных web. На этапе 501 компонент вызывает компонент формирования куба, чтобы сформировать куб вхождений. На этапах 502-506 компонент осуществляет в цикле выбор пары схем (то есть глобальной и интерфейсной, глобальной и результирующей и интерфейсной и результирующей) и формирует матрицу соответствий, представляющую соответствие каждой пары. На этапе 502 компонент выбирает следующую пару схем. На этапе 503 ветвления, если все пары схем были уже выбраны, компонент завершает работу, иначе компонент продолжает работу на этапе 504. На этапе 504 компонент вызывает компонент проецирования куба, чтобы сформировать матрицу вхождений для выбранной пары схем. На этапе 505 компонент вызывает компонент вычисления EMI, чтобы оценить взаимную информацию между парами атрибутов для выбранной пары схем. На этапе 506 компонент вызывает компонент формирования матрицы соответствий, чтобы сформировать матрицу соответствий, указывающую соответствия атрибутов для выбранной пары схем. Компонент затем переходит в цикле на этап 502, чтобы выбрать следующую пару схем.

На фиг.6 показана блок-схема послед