ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
Настоящее изобретение в целом относится к структуре индекса, или индексной структуре, метаданных, предусмотренной для поиска информации о содержимом и для способа обеспечения индексов метаданных, и к способу и устройству, предназначенным для поиска метаданных с использованием структуры индекса метаданных. Более конкретно настоящее изобретение относится к структуре индекса метаданных, предусмотренной для поиска информации о содержимом и для способа обеспечения индексов метаданных, и к способу и устройству для поиска метаданных с использованием индексов метаданных, причем метаданных, содержащих многокодовые ключи, или мультиключи, с помощью которых можно более эффективно осуществлять поиск информации о содержимом в том случае, если метаданные XML (Расширяемый язык разметки, РЯР) о цифровом содержимом, определенные Форумом TV-Anytime (Телевидение по времени)(ниже в документе обозначаемые как "метаданные TVA"), разделяют на фрагменты в качестве независимых блоков и передают на основании фрагмента. Настоящая заявка на патент основана на заявках на патент Кореи с порядковыми номерами 2002-43097 и 2002-62923, которые включены в настоящий документ путем ссылки.
УРОВЕНЬ ТЕХНИКИ
Форум TV-Anytime является частной организацией по стандартизации, учрежденной в сентябре 1999 с целью развития стандартов в области предоставления услуг, относящихся к аудиовизуальным, в дружественной пользователю среде, такой как персональное цифровое записывающее устройство (ПЦЗУ, PDR), содержащее персональное запоминающее устройство большого объема. Конкретно назначение услуг состоит в том, чтобы на основе персонального запоминающего устройстве предоставить возможность всем пользователям просматривать и прослушивать различные типы программ (таких, как обычные вещательные услуги, интерактивные диалоговые услуги в оперативном режиме и т.п.) в требуемое время и требуемым образом.
Форум TV-Anytime задействовал Рабочие группы по моделям предприятий, обращению к интерфейсам/содержимому систем/передачи, описаниям, метаданным, управления правами и защите и подобному, для того, чтобы установить стандартизацию. Что касается метаданных, рассматриваемых в настоящем изобретении, до июня 2002 был опубликован "1st Draft of Metadata Specification SP003vl.3" (1-ый Проект по описанию метаданных версии SP003vl.3).
Конфигурация ПЦЗУ будет кратко описана со ссылкой на Фиг. 1. ПЦЗУ 100 принимает видео/аудиосигналы и метаданные через многообразие сетей связи, таких как сигналы, отраженные от верхних слоев атмосферы, сигналы от искусственных спутников, сети интернет и подобное, от поставщика 200, предоставляющего видео/аудиосигналы, собирает в случае необходимости образцы просмотра и прослушивания, и личные вкусы пользователей, и передает их поставщику 200 для поставки видео/аудиосигналов. ПЦЗУ 100 содержит запоминающее устройство большого объема для хранения на нем принятых видео/аудиосигналов и метаданных. ПЦЗУ 100 дополнительно содержит программное обеспечение для хранения и воспроизведения видео/аудиосигналов, и приложение электронного программного руководства (EPG, ЭПР) для поиска и отображения метаданных для видео/аудиосигналов. Пользователь определяет метаданные для видео/аудиоданных, то есть заголовки программ, времена воспроизведения программы и подобное, посредством показанного на Фиг. 2 экрана приложения ЭПР, который предназначен для руководства и имеет вид сетки, выбирает требуемую программу и принимает ее через сеть связи в реальном времени или воспроизводит видео/аудиоданные, ранее сохраненные на запоминающем устройстве большого объема.
Метаданные относятся к данным, описывающим содержимое, такое как заголовки и резюме программ, и определены в качестве "данных о данных". В технических описаниях метаданных TVA форума TV-Anytime их структура определена с помощью языка схем XML (см. XML 1.0 из W3C (консорциум по WWW)), стандарта W3C (консорциум по продвижению стандартов XML), и определены также семантика и атрибуты соответствующих элементов метаданных. Метаданные TVA, релевантные содержимому вещания, определяют с помощью XML-документа, имеющего корневой узел "TVAMain (300)", как показано на Фиг. 3. Метаданные TVA, релевантные программам, определяют, например, с помощью таких узлов, как «ProgramInformation Table» (Таблица информации о программах), «GroupInformation Table» (Таблица о группах информации), «ProgramLocation Table» (Таблица местоположения программ), «ServiceInformation» (Таблица информации об услугах) и подобное, ниже узла "ProgramDescription" (Описание программы).
На Форуме TV-Anytime метаданные TVA передают на основе фрагмента в качестве независимого блока для передачи большого объема метаданных TVA в формате потока. Понятие фрагментов будет кратко описано со ссылкой на Фиг. 4. Фрагменты формируют, структурируя, или разделяя, метаданные TVA, определенные с помощью XML-документов, показанных на Фиг. 3, на заранее установленные древовидные структуры. Например, если разделяют полные метаданные TVA на древовидную структуру (фрагмент TVAMain), включающую узел "TVAMain" верхнего уровня, и заранее установленные дочерние узлы ниже этого верхнего узла, древовидную структуру (фрагмент ProgramInformation), включающую узел ProgramInformation Table верхнего уровня и дочерние узлы ниже этого верхнего узла, древовидную структуру (фрагмент BroadcastEvent), включающую узел верхнего уровня BroadcastEvent Information и дочерние узлы ниже этого верхнего узла, то каждая из разделенных древовидных структур становится фрагментом. Фрагменты могут быть переданы независимо от других фрагментов, и к фрагментам можно осуществлять доступ индивидуально.
Для индивидуального доступа к фрагментам необходимо знать узел, на который ссылается передаваемый фрагмент метаданных TVA, то есть узел в полной структуре дерева метаданных, соответствующий узлу верхнего уровня для фрагмента метаданных TVA, и описать относительные пути к фрагментам метаданных TVA ключами, содержащимися в передаваемом фрагменте метаданных TVA. С этой целью используется XPath (язык путей в XML-документах, ЯПРЯР), который является определенным W3C синтаксисом описания пути к одному или нескольким узлам в XML-документе. Термин "ключ" относится к конкретному полю метаданных, используемому для индексирования, и означает также дочерние узлы для узла, на который ссылается фрагмент. Поля (для условий поиска), вводимые пользователем, например, 'Service ID' (ИД услуги) и 'Published Time' (Опубликованное время), соответствуют ключам.
Для того чтобы обеспечить эффективный поиск фрагментов и доступ к фрагментам, дополнительно требуется индексная структура для ключей, включенных во фрагменты метаданных, и информацию об индексной структуре, то есть индексную информацию, также передают независимо от фрагментов метаданных.
В среде, обеспечиваемой Форумом TV-Anytime, если пользователь желает получить информацию о программе, удовлетворяющую заранее установленному условию Published Time, используют передаваемую для этой цели независимо от фрагментов индексную информацию, чтобы идентифицировать местоположение (идентификатор) фрагмента метаданных, удовлетворяющего требуемому условию Published Time, и затем на основании местоположения (идентификатора) осуществляют доступ к релевантному фрагменту метаданных для того, чтобы извлечь метаданные, удовлетворяющие условию Published Time.
Техническое описание TV-Anytime TV145, J.P. Evain, "1st Draft of Metadata Specification SP003vl.3", 17-ое совещание, Монреаль, Канада, июнь 2002; далее в документе обозначаемое как "Single key index art reference" (Справочник по уровню техники индексирования по одиночному ключу), предлагает для индексирования фрагмента метаданных структуру индекса одиночного ключа (далее структура одиноключевого индекса).
Обратите внимание, что термин "одиночный ключ" используется в настоящем документе, чтобы отличить его от понятия термина "мультиключ" в варианте осуществления настоящего изобретения, который будет описано далее. Структура индекса мультиключа (далее структура многоключевого индекса) в соответствии с вариантом осуществления настоящего изобретения дает возможность пользователю осуществлять доступ к метаданным по многим ключам, используя несколько ключей одновременно, а структура одиноключевого индекса согласно предшествующему уровню техники позволяет использовать только один ключ для доступа к метаданным.
Понятие контейнера, или объекта, содержащего другие объекты, определенного Форумом TV-Anytime, будет описано прежде описания структуры индекса.
Форум TV-Anytime определяет контейнер как высокоуровневое хранилище, в которое осуществляют передачу всех данных, охватывающих вышеуказанную индексную информацию и фрагменты метаданных, которую называют типом высокоуровневой передачи. Описывая контейнер кратко, каждый контейнер содержит набор разделов, каждый из которых хранит индексную информацию или фрагменты метаданных. Контейнер может быть классифицирован на контейнер индекса и контейнер данных в соответствии с информацией, которая при этом в нем заключена: контейнер индекса заключает в себе разделы индексной информации, такие как раздел перечня индексов ключей (key_index_list), раздел индекса ключа (key_index), раздел индекса подключа (sub_key_index), раздел хранилища строк (string_repository) и раздел хранилища фрагментов данных (fragment_data_repository), причем контейнер данных заключает в себе разделы фрагментов метаданных, такие как раздел таблицы элементов (elements_table), раздел хранилища строк и раздел хранилища фрагментов данных. Вышеуказанная классификация сделана на основании содержимого информации, заключенной в контейнерах. Как контейнер индекса, так и контейнер данных идентичны по построению.
Что касается контейнера, определенного Форумом TV-Anytime Forum, как проиллюстрировано на Фиг. 5, контейнер содержит поле данных для идентификатора контейнера (container_id) (не показано) и несколько разделов. В каждом разделе содержимое, хранимое в теле раздела (section_body), идентифицировано в соответствии с кодированным значением из идентификатора раздела (ИД раздела) (section_id). Например, раздел 10, кодированным значением для которого в ИД раздела является "0X0004", идентифицирован в качестве раздела 20 перечня индексов ключей, раздел 20, кодированным значением для которого в ИД раздела является "0X0005", идентифицирован в качестве раздела индекса ключа, раздел 30, кодированным значением для которого в ИД раздела является "0X0006", идентифицирован как раздел индекса подключа, раздел 40, кодированным значением для которого в ИД раздела является "0X0001", идентифицирован как раздел таблицы элементов, и раздел 50, кодированным значением для которого в ИД раздела является "0X0003", идентифицирован в качестве раздела хранилища фрагментов данных.
Фрагменты метаданных TVA хранят в контейнере данных в разделе 50 хранилища фрагментов данных и затем передают. Информацию об идентификаторе для фрагментов метаданных TVA (handle_value) в контейнере данных включают в раздел 40 таблицы элементов контейнера данных.
В заключение фрагмент метаданных TVA уникально идентифицируют посредством информации об идентификаторе контейнера и информации об идентификаторе фрагмента метаданных того контейнера, который включает фрагмент метаданных TVA.
Описанный выше в ссылке уровень техники, использующий индекс одиночного ключа, предлагает структуру одноключевого индекса для индексирования фрагментов метаданных TVA, хранимых в вышеуказанном контейнере данных, то есть структуру, составленную из раздела 10 перечня индексов ключей, раздела 20 индекса ключа, и раздела 30 индекса подключа. Поскольку синтаксис структуры описан подробно в указанной выше ссылке на индексирование по одиночному ключу, то ее подробное описание будет опущено. Ниже в документе структура будет описана со ссылкой на Фиг. 6, на которой иллюстрирована структура по сегментам индексной информации.
Раздел 10 перечня индексов ключей, определенный в структуре одноключевого индекса, предусматривает перечень всех передаваемых одиночных ключей. Перечень включает в себя информацию об одиночном ключе, определяющую каждый одиночный ключ, и информацию об идентификации, или идентифицирующую информацию, раздела 20 индекса ключа, который будет описан далее в документе.
Информация об одиночном ключе содержит (1) информацию местоположения фрагмента метаданных, релевантного одиночному ключу, и (2) информацию местоположения одиночного ключа во фрагменте метаданных. Информацию местоположения фрагмента метаданных выражают в XPath (fragment_xpath_ptr) в TVA. Информацию местоположения одиночного ключа выражают в XPath (key_xpath_ptr), соответствующим относительному пути в релевантном фрагменте для узла, используемого в качестве одиночного ключа в TVA.
XPath фрагмента метаданных является путем к корневому узлу XML-документа, представляющего метаданные TVA, то есть абсолютный путь, и XPath узлов, используемых в качестве одиночных ключей, то есть XPath одиночных ключей, представляет относительный путь одиночного ключа для релевантного фрагмента метаданных. XPath для фрагмента метаданных и XPath для одиночного ключа сохраняют в сегменте 11 "fragment_xpath_ptr" и сегменте 12 "key_xpath_ptr", соответственно.
Кроме того, раздел 10 перечня индексов ключей включает в себя идентифицирующую информацию о разделе 20 индекса ключа для каждого одиночного ключа, которая будет описана далее в документе (то есть информацию об идентификаторе контейнера того контейнера, который сохраняет раздел 20 индекса ключа, и информацию об идентификаторе индекса ключа). Информацию об идентификаторе контейнера и информацию об идентификаторе индекса ключа сохраняют в сегменте "index_container" раздела 10 перечня индексов ключей и в сегменте идентификатор индекса ключа (ИД индекса ключа) (key_index_identifier), соответственно, и затем передают.
Раздел 20 индекса ключа, определенный в структуре одноключевого индекса, предусматривает перечень информации, представляющей диапазоны значений ключа, включенных в соответствующие разделы 30 индекса подключа, то есть наивысшее значение ключа из значений ключа в соответствующем диапазоне (в дальнейшем обозначаемое как «представительное значение ключа»), и идентифицирующую информацию о разделе 30 индекса подключа, релевантную каждому представительному значению ключа (то есть информацию об идентификаторе контейнера того контейнера, который сохраняет раздел 30 индекса подключа, и информацию об идентификаторе индекса подключа).
Соответственно, раздел 20 индекса ключа включает в себя сегмент ИД индекса ключа для сохранения в нем информации об идентификаторе индекса ключа, определенной в разделе 10 перечня индексов ключей, сегменты 13 наивысшего значения ключа "high_key_value" для сохранения в них представительных значений ключа для соответствующих диапазонов значений ключа, включенных в раздел 30 индекса подключа, и сегменты "sub_index_container" и сегменты "sub_index_identifier" для идентифицирующей информации о разделе 30 индекса подключа (то есть для информации об идентификаторе контейнера того контейнера, в котором сохраняют раздел 30 индекса подключа, и соответствующую информацию об идентификаторе индекса подключа). Раздел 30 индекса подключа, определенный для структуры одноключевого индекса, предусматривает перечень значений ключа. Перечень дополнительно включает в себя идентифицирующую информацию о фрагментах метаданных, соответствующих значениям ключа (то есть информацию об идентификаторе контейнера тех контейнеров, которые сохраняют фрагменты метаданных и информацию об идентификаторе фрагментов метаданных).
Соответственно, раздел 30 индекса подключа включает в себя сегмент "sub_index_identifier" для сохранения в нем информации об идентификаторе индекса подключа, определенной в разделе 20 индекса ключа, сегменты 14 значения ключа (key_value) для хранения в них соответствующих диапазонов значений ключа, сегменты "target_container" для хранения в них соответствующей информации об идентификаторе контейнера контейнеров, в которых хранятся фрагменты метаданных, и сегменты "target_handle", в которых хранится соответствующая информация об идентификаторе фрагмента данных. Структура одиноключевого индекса может быть более легко понята посредством ссылки на Фиг. 7, на которой иллюстрируется информация об индексе.
На Фиг. 7a и 7b показан раздел перечня индексов ключей, включающий в себя одиночные ключи, релевантные Service Id, Published Time и Published Duration. Верхним узлом фрагмента метаданных, включающим одиночные ключи, релевантные Service Id, Published Time и Published Duration, является «BroadcastEvent» 310, как показано на Фиг. 3, выделенный затененным блоком. Соответственно, путь XPath «/TVAMain/ProgramDescription/ProgramLocation Table/BroadcastEvent» для фрагмента "BroadcastEvent" хранят в сегменте "fragment_xpath_ptr" 11a, и пути XPath к одиночным ключам «Service Id», «Published Time» и «Published Duration» для фрагмента «BroadcastEvent» для фрагмента «BroadcastEvent», то есть "@ServiceId" (311a на Фиг. 3), "EventDescription/PublishedTime" 3l1b на Фиг. 3) и "EventDescription/PublishedDuration" (311с на Фиг. 3) хранят в сегменте 12a "key_xpath_ptr".
На Фиг. 7a иллюстративно показан раздел 20a индекса ключа и раздел 30а индекса подключа для «Service Id» (путь XPath для одиночного ключа: @ServiceId) раздела 10a перечня индексов ключей. На Фиг. 7b показан раздел 20b индекса ключа и раздел 30b индекса подключа для «Published Time» (путь XPath для одиночного ключа: EventDescription/PublishedTime).
Данная структура одноключевого индекса является невыгодной потому, что неэффективна для выполнения поиска с составным условием, то есть поиска по одному или нескольким условиям поиска, поскольку согласно техническому описанию TV-Anytime она может поддерживать поиск только по одному, или одиночному, ключу, то есть индексный поиск с использованием ключа, соответствующего конкретному полю фрагмента метаданных. Например, для того чтобы отобразить перечень программ вещания на имеющем вид сетки экране руководства, как показано на Фиг. 2, необходимы операции поиска по двум полям, то есть по «Service Id» и «Published Time».
Для того чтобы объяснить поиск по объединенному условию с использованием обычной структуры одноключевого индекса, ниже в документе в качестве примера будет объяснен вариант, в котором для перечня программ «Service Id» находится в диапазоне от 507 до 514, и «Published Time» - от 09:30 до 10:00. В техническом описании метаданных TV-Anytime условия поиска для извлечения метаданных, относящихся к перечню программ, выражают, как изложено ниже.
- Целевой фрагмент для поиска (BroadcastEvent): /TVAmain/ProgramDescription/ProgramLocationTable/BroadcastEvent
- Перечень условий поиска:
507<=ServiceId<=514
09:30<=EventDescription/PublishedTime<= 10:00.
Для обычной структуры одноключевого индекса доступны два способа получения фрагментов, удовлетворяющих указанным условиям поиска. Способы будут описаны подробно со ссылкой на Фиг. 8a и 8b.
(1) Первый способ поиска с использованием индекса с одиночным ключом
По первому способу, как показано на Фиг. 8a, осуществляют поиск наборов фрагментов в качестве промежуточных результатов, удовлетворяющих соответствующим условиям, независимо с использованием соответствующих одиночных ключей для ServiceId и EventDescription/PublishedTime. После этого получают фрагменты, являющиеся общими в обоих наборах независимо найденных фрагментов, из которых получают итоговый результирующий набор фрагментов, удовлетворяющих условиям.
Ниже в документе данный способ будет описан подробно со ссылкой на Фиг. 7a и 8a.
Сначала указывают (S11) информацию об одиночном ключе и значение одиночного ключа, необходимые для поиска «Service Id» и «Published Time». Информация об одиночном ключе содержит XPath для целевого искомого фрагмента метаданных в качестве информации о местоположении целевого искомого фрагмента метаданных, и XPath для одиночного ключа в качестве информации о местоположении одиночного ключа во фрагменте метаданных.
- XPath для фрагмента метаданных: /TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent,
- XPath для Service Id: @ServiceId,
- Значение ключа для Service Id: 507<=ServiceId<=514.
Затем одиночный ключ, соответствующий XPath 11a для фрагмента и XPath 12a для Service Id, извлекают из раздела 10а перечня индексов ключей, и извлекают идентифицирующую информацию о разделе 20а индекса ключа. На этой основе представительные значения ключа "509" 13a и "519" 13a, то есть представительные значения ключа, которые обозначают диапазоны (500-509, 510-519) значений ключа, в которые включены значения ключа (507-514), подлежащие поиску, извлекают из раздела 20а индекса ключа, имеющего данную извлеченную идентифицирующую информацию. Затем извлекают идентифицирующую информацию о разделе 30а индекса подключа для сегментов 14a, имеющих соответствующие диапазоны значений ключа (500-509, 510-519), связанные с представительными значениями ключа "509" и "519". Идентифицирующую информацию для фрагментов метаданных (информацию об идентификаторе контейнера и информацию об идентификаторе фрагмента данных, хранимые в сегменте "target_container" и сегменте "target_handle", соответственно), соответствующую значениям ключа 507-514, извлекают из раздела 30а индекса подключа, и извлекают релевантные фрагменты метаданных, используя извлеченную идентифицирующую информацию (S12, S14).
Для поиска Published Time в качестве примера, информацию об одиночном ключе, то есть информацию об XPath для целевого искомого фрагмента метаданных и информацию об XPath для одиночного ключа, и значение одиночного ключа выражают, как изложено ниже.
- XPath для фрагмента:
/TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent,
- XPath для Published Time: EventDescription/PublishedTime,
- Значение ключа для Published Time: 09:30<=EventDescription/PublishedTime<=10:00.
Фрагменты метаданных, соответствующие значениям ключа 09:30-10:00, извлекают посредством по существу те же этапов, что и при поиске (S13, S15) Service Id. Выполняют пересечение извлеченных фрагментов метаданных для Service Id и Published Time, и метаданные общих фрагментов метаданных в качестве итогового результата (S16) поставляют на имеющий вид сетки экран руководства, показанный на Фиг. 2.
(2) Второй способ поиска с использованием индекса с одиночным ключом.
По второму способу осуществляют поиск фрагментов с использованием только одного (например, Service Id) из двух одиночных ключей, связанных с условиями поиска, как проиллюстрировано на Фиг. 8b (S21-S23), и только те фрагменты, для которых Published Time, как другое условие поиска, находится между 09:30 и 10:00, выбирают из найденных фрагментов (S24).
Поскольку промежуточные результирующие фрагменты, полученные посредством поиска с использованием соответствующих одиночных ключей, являются обычно значительными по объему, то такие способы поиска, использующие структуру одноключевого индекса, не являются эффективными. По первому способу, поскольку все программы в диапазоне релевантных Service Id получают как результат поиска независимо от диапазона Published Time, и программы в релевантном временном диапазоне для всех значений Service Id получают как результат поиска, то размер результата поиска может стать очень значительным. Кроме того, поскольку вычисление также является усложненным при обработке объединения двух промежуточных результатов поиска, являющихся значительными по размеру, то непроизводительные издержки в приемном устройстве значительно возрастают. По второму способу один промежуточный результат должен быть дополнительно фильтрован другим условием поиска. Следовательно, поиск по составному условию при использовании структуры одноключевого индекса может вызывать значительные непроизводительные издержки в приемном устройстве. Дополнительно, если условие поиска для одиночного ключа является входным, то в метаданных определяют информацию местоположения для поля условия поиска, и определенную информацию местоположения сравнивают с информацией о ключе из перечня индексов ключа для осуществления поиска соответствующего ключа. В таком случае непроизводительные издержки вызваны тем, что необходимо сравнение обоих путей XPath.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
Соответственно, задача настоящего изобретения состоит в том, чтобы создать структуру многоключевого индекса метаданных, применимую для поиска по составному условию информации о содержимом.
Другая задача настоящего изобретения состоит в том, чтобы создать способ обеспечения индексов метаданных, применимых для составного условия, задаваемого по информации о содержимом, способ поиска метаданных с использованием индексов метаданных, и устройство для поиска, использующее таковые. Еще одна задача настоящего изобретения состоит в том, чтобы создать структуру многоключевого индекса, в которой по меньшей мере часть информации о ключе, то есть информацию местоположения, определяющую ключ, выражают согласно заранее установленному коду. Дополнительные задачи и/или преимущества настоящего изобретения будут сформулированы частично в описании, которое следует ниже, и, частично, будут очевидны из описания, или могут быть изучены посредством осуществления изобретения на практике.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложена структура индекса для метаданных, разделенных на фрагменты, содержащая перечень мультиключей, которые соответствуют комбинации полей метаданных, и информацию местоположения для определения мультиключа из перечня. Структура индекса может дополнительно содержать значения мультиключа и идентифицирующую информацию метаданных, соответствующую значениям мультиключа. Идентифицирующая информация метаданных может содержать идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключа.
Структура индекса может дополнительно содержать подраздел, включающий в себя диапазоны значений мультиключа и идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключа, и раздел, включающий в себя представительные значения ключа, представляющие соответствующие диапазоны значений мультиключа.
Перечень может включать в себя идентифицирующую информацию о разделе, и раздел может дополнительно включать в себя идентифицирующую информацию о подразделе. По меньшей мере часть информации о местоположении может быть выражена заранее установленным кодом. Информация о местоположении может содержать информацию местоположения фрагмента, включающего в себя мультиключ, и информацию местоположения мультиключа во фрагменте. В качестве еще одного аспекта, информация местоположения может быть выражена в XPath.
Каждое из представительных значений ключа может быть значением из соответствующего диапазона значений мультиключа. Представительное значение ключа может быть по меньшей мере одним из значений максимальным значением, минимальным значением или промежуточным значением из значений, находящихся в заранее установленном диапазоне. Метаданные могут быть метаданными согласно определениям Форума TVA.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложена еще одна структура индекса для метаданных, разделенных на фрагменты, содержащая значения мультиключей и идентифицирующую информацию метаданных, соответствующую значениям мультиключей, причем мультиключи соответствуют комбинации полей метаданных. Структура индекса может дополнительно содержать перечень мультиключей. Структура индекса может дополнительно содержать информацию местоположения для определения мультиключей, причем по меньшей мере часть информации местоположения выражена заранее установленным кодом. Идентифицирующая информация метаданных может содержать идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключей.
Что касается сравнения значений мультиключа по размеру, то мультиключ может содержать поля (k1, k2, k3... kn) метаданных, которые расположены в соответствии с приоритетом (k1>k2>k3>... kn), и комбинированные поля могут быть сравниваемыми последовательно, начиная с первого поля, имеющего самый высокий приоритет, причем значения сравнивают арифметически, если значения мультиключа являются числовыми, или оценивают в лексикографическом порядке, если значения мультиключа являются буквенными. Первое и второе значения мультиключа могут соответствовать (a1, a2, a3...an) и (b1, b2, b3... bn), соответственно, и первое и второе значения (a1, a2, a3...an) и (bl, b2, b3...bn) мультиключа могут быть определены как имеющие одинаковый размер, если отсутствует поле, имеющее отличающийся размер.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложена еще одна структура индекса для метаданных, разделенных на фрагменты, содержащая раздел перечня индексов ключей, который содержит перечень мультиключей, причем каждый мультиключ соответствует комбинации полей метаданных, раздел индекса ключа и раздел индекса подключа, причем для мультиключа из перечня индексов ключей раздел индекса подключа содержит диапазоны значений мультиключа и идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключа, и раздел индекса ключа содержит представительные значения ключа, представляющие соответствующие диапазоны значений мультиключа.
Раздел перечня индексов ключей может дополнительно содержать информацию местоположения для определения мультиключей, причем по меньшей мере часть информации о местоположении выражена заранее установленным кодом.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен машиночитаемый носитель информации, содержащий структуру данных для хранения индекса метаданных, разделенных на фрагменты, причем индекс предусмотрен для поиска метаданных.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен способ обеспечения структуры индекса для метаданных, разделенных на фрагменты, содержащий обеспечение перечня мультиключей, соответствующих комбинацию полей метаданных, и информации местоположения для определения мультиключа из перечня.
Способ может дополнительно содержать обеспечение значений мультиключа и идентифицирующей информации метаданных, соответствующей значениям мультиключа.
Информация о местоположении может быть выражена в XPath. По меньшей мере часть информации местоположения выражена заранее установленным кодом. Метаданные могут быть метаданными согласно определениям Форума TVA.
Способ может дополнительно содержать обеспечение подраздела, включающего в себя диапазоны значений мультиключа и идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключа, и обеспечение раздела, включающего представительные значения ключа, представляющие соответствующие диапазоны значений мультиключа.
Каждое из представительных значений ключа является значением из соответствующего диапазона значений мультиключа. Представительное значение ключа может быть одним из значений максимальным значением, минимальным значением или промежуточным значением из значений в заранее установленном диапазоне.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен еще один способ обеспечения структуры индекса для метаданных, разделенных на фрагменты, содержащий обеспечение значений мультиключей и обеспечение идентифицирующей информации для метаданных, соответствующей значениям мультиключей, причем мультиключи соответствуют комбинации полей метаданных.
Способ может дополнительно содержать перечень мультиключей.
Способ может дополнительно содержать обеспечение информации местоположения для определения мультиключей, причем по меньшей мере часть информации местоположения выражают заранее установленным кодом.
Идентифицирующая информация метаданных может содержать идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключей.
Что касается сравнения значений мультиключа по размеру, то мультиключ может содержать поля (k1, k2, k3... kn) метаданных, которые расположены в соответствии с приоритетом (k1>k2>k3>... kn), и комбинированные поля могут быть сравниваемыми последовательно, начиная с первого поля, имеющего самый высокий приоритет, причем значения сравнивают арифметически, если значения мультиключа являются числовыми, или оценивают в лексикографическом порядке, если значения мультиключа являются буквенными.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен очередной способ обеспечения структуры индекса для метаданных, разделенных на фрагменты, который содержит обеспечение раздела перечня индексов ключей, включая перечень мультиключей, причем каждый мультиключ соответствует комбинации полей метаданных, обеспечение раздела индекса ключа, и обеспечение раздела индекса подключа, причем для мультиключа из перечня индексов ключей раздел индекса подключа содержит диапазоны значений мультиключа и идентифицирующую информацию некоторых фрагментов метаданных, соответствующих значениям мультиключа, и раздел индекса ключа содержит представительные значения ключа, представляющие соответствующие диапазоны значений мультиключа.
Раздел перечня индексов ключей может дополнительно содержать информацию местоположения для определения мультиключей, причем по меньшей мере часть информации местоположения выражена заранее установленным кодом.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен способ осуществления поиска метаданных, разделенных на фрагменты, с использованием индекса, имеющего перечень мультиключей и информацию местоположения для определения мультиключей, содержащий поиск в индексе метаданных мультиключа, соответствующего условиям поиска из комбинации полей метаданных, и извлечение фрагмента метаданных с использованием найденного мультиключа.
Поиск мультиключа может содержать определение информации местоположения, соответствующей полям условий поиска метаданных, и поиск мультиключа, соответствующего информации местоположения, относящейся к полям условий поиска.
Поиск мультиключа может содержать поиск значения мультиключа, удовлетворяющего условиям поиска.
Поиск значения может содержать поиск значения из значений мультиключа в индексе, и извлечение фрагмента может включать в себя извлечение фрагмента метаданных с использованием идентифицирующей информации фрагмента, соответствующего значению мультиключа.
В качестве ответа на множество значений мультиключа, удовлетворяющего условиям поиска, извлечение фрагмента может содержать извлечение некоторых фрагментов метаданных, соответствующих значениям мультиключа, удовлетворяющего условиям поиска.
Поиск значения может содержать поиск представительного значения ключа, удовлетворяющего условиям поиска, из представительных значений ключа индекса, соответствующих диапазонам значений мультиключа, и поиска значения в диапазоне значений, соответствующего представительному значению ключа.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен другой способ поиска метаданных, разделенных на фрагменты, с использованием индекса, имеющего перечень мультиключей и информацию местоположения для определения мультиключей, содержащий поиск в индексе метаданных значения мультиключа, удовлетворяющего условиям поиска из комбинации полей метаданных, и извлечение фрагмента метаданных, соответствующего найденному значению.
В качестве ответа на множественность значений мультиключа, удовлетворяющего условиям поиска, извлечение фрагмента может содержать извлечение некоторых фрагментов метаданных, соответствующих значениям мультиключа, удовлетворяющего условиям поиска.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложен еще один способ поиска метаданных, разделенных на фрагменты, содержащий доступ к перечню, содержащему набор комбинаций информации местоположения фрагмента и информации местоположения, определяющей по меньшей мере два ключа во фрагменте, и поиск в перечне комбинации, соответствующей условиям поиска по меньшей мере для двух ключей метаданных.
Способ может дополнительно содержать извлечение одного или нескольких фрагментов метаданных, соответствующих идентифицирующей информации о метаданных, идентифицированных посредством выбранной комбинации.
По способу, одна из информации местоположения фрагмента и информации местоположения, определяющей по меньшей мере два ключа, может быть выражена заранее установленным кодом.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения предложено устройство для поиска метаданных, разделенных на фрагменты, с использованием индекса, имеющего перечень мультиключей и информацию местоположения для определения мультиключей, содержащее блок ввода данных, который принимает условия поиска, и блок управления, который осуществляет поиск в индексе метаданных мультиключа, соответствующего условиям поиска из комбинации полей метаданных, и извлечение фрагмента метаданных с использованием найденного ключа.
Блок управления может осуществлять поиск значения мультиключа, удовлетворяющего условиям поиска, среди значений мультиключа из индекса, и извлекать фрагмент, соответствующий значению мультиключа, используя идентифицирующую информацию фрагмента.
В качестве ответа на набор значений мультиключа, удовлетворяющих условиям поиска, блок управления может выделять некоторые из фрагментов метаданных, соответствующие значениям мультиключа, удовлетворяющего условиям поиска.
Блок управления может осуществлять поиск представительного значения, удовлетворяющего условиям поиска, из числа представительных значений индекса, соответствующих диапазонам значений мультиключа, и осуществлять поиск значения из диапазона значений, соответствующего представительному значению ключа.
Информация местоположения может быть выражена в XPath.
По меньшей мере часть информации местоположения может быть выражена заранее установленным кодом.
Метаданные могут быть метаданными согласно определениям Форума TVA.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложено другое устройство для поиска метаданных, разделенных на фрагменты, с использованием индекса, имеющего перечень мультиключей и информацию местоположения для определения мультиключей, содержащее блок ввода данных, который принимает условия поиска, и блок управления, который осуществляет поиск в индексе метаданных мультиключа, соответствующего условиям поиска из комбинация полей метаданных, и извлечение фрагмента метаданных с использованием найденного значения.
Блок управления может осуществлять поиск значения мультиключа, удовлетворяющего условиям поиска, среди значений мультиключа из индекса, и выделять фрагмент, соответствующий значению мультиключа, с использованием идентифицирующей информации фрагмента.
Блок управления может осуществлять поиск представительного значения, удовлетворяющего условиям поиска, среди представительных значений индекса, соответствующих диапазонам значений мультиключа, и осуществлять поиск значения в диапазоне значений, соответствующего представительному ключу.
В качестве ответа на набор значений мультиключа, удовлетворяющего условиям поиска, блок управления может выделять фрагменты метаданных, соответствующие значениям мультиключа, удовлетворяющего условиям поиска.
По меньшей мере часть информации местоположения может быть выражена заранее установленным кодом.
Устройство может дополнительно содержать блок ввода данных, который принимает метаданные и индекс метаданных, запоминающее устройство, хранящее метаданные и индекс метаданных, и блок вывода, который осуществляет вывод результата поиска с помощью блока управления.
Для того чтобы решить вышеуказанные и/или другие задачи настоящего изобретения, предложено следующее устройство для поиска метаданных, разделенных на фрагменты, с использованием индекса, имеющего перечень мультиключей и информацию местоположения для определения мультиключей, содержащее блок ввода данных, который принимает условия поиска по меньшей мере по двум ключам метаданных, и блок управления, который осуществляет выбор комбинации, соответствующей условиям поиска из перечня, содержащего набор комбинаций информации местоположения фрагмента и информации местоположения, определяющей по меньшей мере два ключа во фрагменте.
Блок управления может дополнительно извлекать один или несколько фрагментов метаданных, соответствующих идентифицирующей информации для метаданных, идентифицированных посредством выбранной комбинации.
Одна из информации местоположения фрагмента и информации местоположения, определяющая по меньшей мере два ключа, может быть выражена заранее установленным кодом.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Вышеуказанные и/или другие особенности и признаки настоящего изобретения будут более очевидными из последующего описания предпочтительных вариантов осуществления, приведенных вместе с сопроводительными чертежами, на которых:
Фиг. 1 - схематическое представление схемы обычного ПЦЗУ;
Фиг. 2 - экран руководства в виде сетки в обычном приложении ЭПР;
Фиг. 3 - блок-схема структуры обычных метаданных, определенных Форумом TV-Anytime;
Фиг. 4 - схематическое представление обычного фрагмента, определенного Форумом TV-Anytime;
Фиг. 5 - схематическое представление обычного контейнера, определенного Форумом TV-Anytime;
Фиг. 6 - блок-схема структуры индекса метаданных, использующей традиционное понятие одиночного ключа;
Фиг. 7a и 7b - блок-схема структуры индекса метаданных и алгоритма поиска с использованием традиционной схемы с одиночным ключом;
Фиг. 8a и 8b - схемы способов поиска метаданных с использованием традиционной схемы с одиночным ключом;
Фиг. 9 - блок-схема структуры индекса метаданных на основании схемы с мультиключом в соответствии с вариантом осуществления настоящего изобретения;
Фиг. 10 - блок-схема структуры индекса метаданных и алгоритма поиска, использующие схему с мультиключом в соответствии с вариантом осуществления настоящего изобретения;
Фиг. 11 - блок-схема способа обеспечения индексов метаданных в соответствии с вариантом осуществления настоящего изобретения;
Фиг. 12 - схема способа поиска метаданных в соответствии с вариантом осуществления настоящего изобретения; и
Фиг. 13 - схематическое представление устройства, предназначенного для поиска метаданных, в соответствии с вариантом осуществления настоящего изобретения.
ЛУЧШИЙ ВАРИАНТ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ
Ниже в документе со ссылками на сопроводительные чертежи будут подробно описаны воплощения структуры индекса метаданных, предусмотренной для поиска информации о содержимом, способа обеспечения индексов метаданных, и способа и устройства для поиска метаданных с использованием индексов метаданных.
Воплощения в данном описании будут представлены на основе метаданных TVA для цели характеристики; однако, это не должно быть интерпретировано или понято как ограничение рамок охраны настоящего изобретения.
На Фиг. 9 показан синтаксис определения структуры многоключевого индекса в соответствии с вариантом осуществления настоящего изобретения. Сначала со ссылкой на Фиг. 9 в качестве структуры индекса метаданных, предназначенной для поиска информации о содержимом, будет описана структура, включающая в себя раздел 110 перечня индексов ключей, раздел 120 индекса ключа и раздел 130 индекса подключа, предназначенная для индексирования фрагментов метаданных TVA, передаваемых и хранимых в контейнере данных, и затем будет описана структура многоключевого индекса, определенная посредством синтаксиса.
По сравнению с синтаксисом, определенным в ссылке на уровень техники индексирования с одиночным ключом, синтаксис, определяющий структуру индекса метаданных, то есть структуру многоключевого индекса в соответствии с вариантом осуществления настоящего изобретения, содержит структуру, заново представленную для схемы многоключевого индексирования, включающую в себя дескриптор ключа (key_descriptor), дескриптор наивысшего значения ключа (high_key_value_descriptor) и дескриптор значения ключа (key_value_descriptor), и измененные структуры раздела перечня индексов ключей, раздела индекса ключа и раздела индекса подключа.
1. Раздел перечня индексов ключей
Раздел перечня индексов ключей обеспечивает перечень всех передаваемых мультиключей. В каждую структуру перечня индексов ключей включен (key_descriptor), чтобы дать возможность индексирования по многим ключам, как показано в Таблице 1.
key_index_count: задает количество всех передаваемых мультиключей, то есть количество индексов для полного XML-документа.
fragment_xpath_ptr(): описывает XPath для целевого фрагмента метаданных, который должен быть индексирован, то есть информацию местоположения целевого фрагмента метаданных, который должен быть индексирован. Информация местоположения фрагмента может быть выражена согласно заранее установленному коду. То есть, если фрагмент имеет, например, часто используемый тип, то предусматривают кодированное значение, выражающее XPath для фрагмента с помощью заранее установленного кода. Так как XPath фрагмента может быть выражен просто как кодированное значение, то непроизводительные издержки при поиске метаданных могут быть сокращены. Например, кодированными значениями могут быть "0X01", "0X02", "0X03", и так далее, и из 8 битов, из 16 битов, и так далее, в соответствии с применениями. Информация местоположения для фрагмента, кодированного как "0X07", может обозначать, например, XPath для фрагмента BroadcastEvent (широковещательное событие). Если значением кода является "0X00FF", оно может обозначать, определяемый пользователем фрагмент, и таким образом, XPath для релевантного определяемого пользователем фрагмента может быть добавлен в качестве дополнительной информации.
key_descriptor(): описывает положение XPath мультиключа в XPath целевой группе фрагментов метаданных, которые должны быть индексированы, то есть информацию местоположения мультиключа во фрагменте метаданных и информацию об индикаторе кодирования в каждом элементе/признаке, составляющем мультиключ. Подобно вышеуказанному, информация местоположения для мультиключа, который имеет часто используемый тип, может быть выражена заранее установленным кодом. Значение кода для часто используемого типа мультиключа может иметь структуру, подобную кодированию фрагмента. Кодирование XPath для фрагмента и кодирование XPath для мультиключа может быть использовано совместно или независимо.
index_container (контейнер индекса): идентифицирует контейнер, в котором находится (присутствует) заданный раздел индекса ключа.
key_index_identifier: идентифицирует раздел индекса ключа в контейнере, заданным посредством index_container. Раздел 20 индекса ключа может быть идентифицирован уникальным образом комбинацией index_container и key_index_identifier.
2. Дескриптор ключа (key_descriptor)
Мультиключ является объединенным, или составным, ключом. По отношению к набору ключей, составляющих мультиключ, key_descriptor описывает характеристики ключа, такие как XPath для ключа. В Таблице 2 ниже показан key_descriptor.
key_attribute_count: определяет количество ключей, которые составляют мультиключ.
key_xpath_ptr: указывает путь, относящийся к fragment_xpath_ptr, для узла (ключа), используемого в качестве мультиключа.
3. Заново представлен high_key_value_descriptor() раздела индекса ключа.
В данном воплощении high_key_value_descriptor() указывает значение представительного ключа, представляющего диапазон значений мультиключа в искомом разделе индекса из разделов индексов подключей, количество которых указано разделом индекса ключа. Дескриптор high_key_value_descriptor() задает, например, наивысшее значение из значений мультиключа в соответствующем разделе индекса подключа. Однако может любое значение ссылки использоваться, поскольку оно представляет значения мультиключа в заранее установленном диапазоне значений в пределах соответствующих разделов индекса подключа, включая минимальное значение или промежуточное значение, и т.д., в качестве другого воплощения настоящего изобретения.
key_attribute_count
key_index_identifler: идентифицирует раздел индекса ключа в контейнере, заданного посредством index_container. Раздел индекса ключа может быть идентифицирован уникальным образом комбинацией index_container и key_index_identifier. Это определено в разделе перечня индексов ключей.
sub_index_container: идентифицирует контейнер, в котором присутствует указанный индекс подключа.
sub_index_identifier: идентифицирует раздел индекса подключа в контейнере, заданном посредством sub_index_container. Раздел индекса подключа может быть идентифицирован уникальным образом посредством комбинации sub_index_container и sub_index_identifier.
Ниже в Таблице 4 представлен high_key_value_descriptor().
key_attribute_count: задает количество ключей, составляющих мультиключ. Оно определено в разделе перечня индексов ключей.
key_attribute_value: представляет представительное ключевое значение для каждого ключа. Формат кодирования значения соответствует значению key_value схемы индексирования с одиночным ключом.
Если high_key_value_descriptor() содержит значение мультиключа, сравнение значений мультиключа по размеру выполняют, как изложено ниже. Если значения мультиключа являются числовыми, их сравнивают арифметически; если значения мультиключа является буквенными, их оценивают в лексикографическом порядке. Что касается мультиключа (k1, k2..., kn), который состоит из ключей k1, k2..., kn, предполагают, что k1 имеет самый старший приоритет, и kn имеет самый младший приоритет. Согласно данному предположению, рассматривая два значения мультиключа (a1, a2..., an) и (bl, b2..., bn),
* значение мультиключа (a1, a2..., an) больше значения мультиключа (b1, b2..., bn), если и только если существует целое число i (0<=i<=n-l), такое что для каждого j (0<=j<=i-l), aj=bj и ai>bi.
* значение мультиключа (a1, a2..., an) меньше значения мультиключа (b1, b2..., bn), если и только если существует целое число i (0<=i<=n-l), такое что для каждого j (0<=j<=i-l), aj = bj и ai< bi.
* значение мультиключа (a1, a2..., an) равно значению мультиключа (b1, b2..., bn), если и только если для каждого i (1<=i<=n), ai= bj.
4. Раздел индекса подключа
Заново представлен дескриптор key_value_descriptor() для схемы многоключевого индексирования. Дескриптор key_value_descriptor() представляет значение мультиключа целевого фрагмента, указываемого таким образом.
key_attribute_count
sub_index_identifier: идентифицирует в контейнере, идентифицированном посредством sub_index_container, раздел индекса подключа. Раздел индекса подключа может быть идентифицирован уникальным образом комбинацией sub_index_container и sub_index_identifier. Это определено в разделе индекса ключа.
reference_count: задает количество мультиключей, включенных в sub_key_index().
target_container: идентифицирует контейнер, в котором присутствует указанный фрагмент метаданных.
target_handle: идентифицирует раздел фрагмента метаданных в контейнере, идентифицированном посредством target_container. Раздел фрагмента метаданных может быть идентифицирован уникальным образом комбинацией target_container и target_handle.
Ниже в Таблице 6 показан key_value_descriptor().
key_attribute_count: задает количество ключей, составляющих мультиключ. Оно определено в разделе перечня индексов ключей.
key_attribute_value: представляет значение для каждого ключа. Формат соответствует значению key_value в ссылке на уровень техники индексирования с одиночным ключом.
Сравнение значений key_value_descriptor() осуществляют так же, как сравнение значений high_key_value_descriptor() в структуре раздела индекса ключа.
Ниже в документе, со ссылкой на Фиг. 9, будет обсуждена определенная посредством описанного выше синтаксиса структура метаданных, которая проиллюстрирована с использованием сегментов индексной информации.
Раздел 110 перечня индексов ключей, определенный в структуре метаданных, предусматривает перечень всех передаваемых мультиключей. Перечень содержит информацию о мультиключе, определяющую каждый мультиключ, и идентифицирующую информацию для раздела 120 индекса ключа, которая будет описана далее в документе. Информация о мультиключе содержит (1), информацию местоположения фрагмента метаданных, релевантного мультиключу (выражаемую в TVA в XPath (fragment_xpath_ptr) для фрагмента метаданных, релевантного мультиключу), и (2) информацию местоположения мультиключа во фрагменте метаданных (выражаемую в TVA в XPath (key_descriptor) для узлов, используемых в качестве мультиключей, то есть релевантный путь в XPath-местоположении фрагмента метаданных, релевантного узлам, используемым в качестве мультиключей). Подобно структуре индекса с одиночным ключом, XPath для фрагмента метаданных ссылается на путь для корневого узла XML-документа, содержащего метаданные TVA, то есть абсолютный путь, и XPath для узла, используемого в качестве мультиключа, то есть XPath для мультиключа, ссылается на относительный путь мультиключа для фрагмента метаданных. XPath для фрагмента метаданных и XPath для мультиключа хранят в сегменте 111 "fragment_xpath_ptr", и сегменте 112 "key_descriptor", соответственно.
Раздел 110 перечня индексов ключей также содержит идентифицирующую информацию о разделе 120 индекса ключа для каждого мультиключа, которая будет описана далее в документе (то есть информацию об идентификаторе контейнера того контейнера, в котором сохранен раздел 120 индекса ключа, и информацию об идентификаторе индекса ключа). Информацию об идентификаторе контейнера и информацию об идентификаторе индекса ключа сохраняют, соответственно, в сегменте "index_container" и сегменте "key_index_identifier" в разделе 110 перечня индексов ключей и затем передают.
Раздел 120 индекса ключа, определенный в структуре потока данных многоключевого индекса, предусматривает перечень информации о диапазонах значений мультиключа, включенных в соответствующий раздел индекса подключа, то есть представительное ключевое значение, представляющее заранее установленный диапазон значений мультиключа, включенных в каждый раздел 130 индекса подключа (в данном воплощении, наивысшее значение мультиключа), и идентифицирующую информацию для раздела 130 индекса подключа, связанную с каждым представительным ключевым значением (то есть информацию об идентификаторе контейнера того контейнера, который сохраняет раздел 130 индекса подключа, и информацию об идентификаторе индекса подключа). Способ сравнения значений мультиключа в данном воплощении идентичен таковому сравнению значений мультиключа, описанному в связи с Таблицей 4.
Раздел 120 индекса ключа включает в себя сегмент «key_index_identifier», сохраняющий информацию об идентификаторе индекса ключа, определенную в разделе 110 перечня индексов ключей, сегменты 113 «high_key_value_descriptor», сохраняющий представительные значения ключа для соответствующих диапазонов значений мультиключа, включенные в раздел 130 индекса подключа, и информацию, идентифицирующую раздел 130 индекса подключа, который содержит значения мультиключа. Информация, идентифицирующая раздел 130 индекса подключа, включает в себя сегменты "sub_index_container", в которых сохраняется информация об идентификаторе контейнера тех контейнеров, в которых сохранен раздел 130 индекса подключа, и сегменты "sub_index_identifier", в которых сохраняется информация об идентификаторе индекса подключа.
Раздел 130 индекса подключа, определенный в структуре индекса, обеспечивает перечень значений мультиключа. Перечень дополнительно включает в себя идентифицирующую информацию о фрагментах метаданных, соответствующую значениям мультиключа (то есть информацию об идентификаторе контейнера того контейнера, в котором сохранен фрагмент метаданные, и идентифицирующую информацию о фрагменте метаданных).
Соответственно, раздел 130 индекса подключа включает в себя сегмент "sub_index_identifier", в котором сохраняется информация об идентификаторе индекса ключа, определенная в разделе 120 индекса ключа, сегмент 114 "key_value_descriptor" для сохранения в нем соответствующих диапазонов значений мультиключа, и идентифицирующая информация о фрагментах метаданных, соответствующих значениям мультиключа. Идентифицирующая информация включает в себя сегменты целевой контейнер (target_container), в которых сохраняется соответствующая, идентифицирующая контейнер, информация для тех контейнеров, в которых сохранены фрагменты метаданных, и сегменты "target_handle", в которых сохраняется соответствующая информация об идентификаторе фрагмента данных (handle_value).
Структура метаданных будет более легко понята посредством Фиг. 10, на который проиллюстрирована информация об индексе.
На Фиг. 10 показан раздел перечня индексов мультиключей, содержащий мультиключи для Service Id и Published Time. Узлом верхнего уровня для фрагмента метаданных, включающего мультиключи, связанные с Service Id и Published Time, является «BroadcastEvent» 310, как обозначено затененной областью на Фиг. 3. Следовательно, XPath «/TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent» для фрагмента «BroadcastEvent» хранят в сегменте 111 «fragment_xpath_ptr», и пути XPath мультиключей для Service Id и Published Time для фрагмента «BroadcastEvent», которыми являются "@ServiceId" 311a, и "EventDescription/PublishedTime" 311b, хранят в сегменте 112 "key_descriptor".
Такая структура потока метаданных позволяет эффективно осуществлять поиск и доступ к фрагментам метаданных, если поиск осуществляют на основании более одного условия, то есть, при осуществлении поиска по составным условиям.
Несмотря на то, что в качестве примера в настоящем варианте осуществления упомянуты мультиключи для Service Id и Published Time, в комбинации также может быть использовано многообразие мультиключей. Например, могут использоваться мультиключи для времен начала и окончания программы в связи с расписанием вещания, мультиключи для фамилии и имен личности (актер, директор, или подобное), включенных в программу и так далее.
При использовании мультиключей для времен начала и окончания программы в связи с расписанием вещания, верхним узлом фрагмента метаданных, включающим мультиключи для времен начала и окончания программы, может быть «Schedule» (Расписание) (не показано). Следовательно, XPath «TVAMain/ProgramDescription/ProgramLocationTable/Schedule» для фрагмента «Schedule» может быть сохранен в сегменте 111 "fragment_xpath_ptr", и пути XPath, "@start" и "@end" мультиключей для времен начала и окончания программы для фрагмента 'Schedule' могут быть сохранены в сегменте 112 "key_descriptor".
Если используют мультиключи для фамилии и имен личности (актер, директор или подобный), включенных в программу, то верхним узлом фрагмента метаданных, включающим мультиключи для фамилии и имен личности (актер, директор, или подобный), может быть "PersonName" (не показано), и поэтому XPath «TVAMain/ProgramDescription/CreditsInformation Table/PersonName» для фрагмента "PersonName" может быть сохранен в сегменте 111 "fragment_xpath_ptr", и XPaths "FamilyName" и "GivenName" мультиключей для фамилии и имен личности в программе для фрагмента "PersonName" может быть сохранен в сегменте 112 "key_descriptor".
На Фиг. 11 изображен способ обеспечения индекса метаданных, содержащих структуру, соответствующую варианту осуществления настоящего изобретения. Индекс метаданных может быть сформирован поставщиком 200, поставляющим аудио/визуальные сигналы.
Информация о содержимом, то есть метаданные, обрабатывают блоками, соответствующими фрагменту, как описано выше (SI00). Мультиключ обеспечивают комбинацией ключей, связанных с информацией о фрагментах, например, 'Service ID' и 'Published Time' (S200). Затем обеспечивают раздел 130 индекса (sub_key_index) подключа, в котором сегменты, например, 114a, 114b и 114с и т.д., содержащие диапазоны значений мультиключа, обеспечивают, как описано выше (S300). Раздел 130 индекса подключа дополнительно включает в себя идентифицирующую информацию о фрагменте метаданных, соответствующую значениям мультиключа (то есть информацию об идентификаторе контейнера и информацию об идентификаторе фрагмента данных, соответственно хранимых в сегментах "target_container" и сегментах "target_handle", показанных на Фиг. 9).
Обеспечивают (S400) раздел 120 индекса ключа, содержащий представительные значения ключа, представляющие диапазоны значений мультиключа. Например, со ссылкой на Фиг. 9, в него включены представительные значения ключа "509/10:00" и "519/10:00" (113a и 113b), представляющие заранее установленные диапазоны 500˜509/09:10-10:00 и 510˜519/09:10-10:00 (114a и 114b) значений мультиключа для 'Service ID'/'Published Time', как комбинированных. В данном варианте осуществления Service ID имеет более высокий приоритет относительно Published Time. Раздел 120 индекса ключа дополнительно включает идентифицирующую информацию о разделе 130 индекса подключа, в котором сохраняются значения мультиключа (то есть информацию об идентификаторе контейнера относительно тех контейнеров, в которых хранят раздел индекса подключа согласно Фиг. 9, и информацию об идентификаторе индекса подключа). Понятно, что могут быть обеспечены другие мультиключи и соответствующие разделы индексов ключей и/или разделы индексов подключей так, как описано выше.
Обеспечивают (S500) раздел 110 перечня индексов ключей, в котором информацию о мультиключе, то есть информацию местоположения фрагмента метаданных, к которому принадлежит каждое поле, составляющее обеспечиваемый мультиключ, и информацию местоположения для каждого поля во фрагменте метаданных, располагают на основе мультиключа. Например, если ключи 'Service ID' и 'Published Time' объединены, то информацию о мультиключе для объединенного 'Service ID' и 'Published Time', например, XPath для целевого фрагмента метаданных для индексирования (/TVAMain/ProgramDescription/Program LocationTable/BroadcastEvent) и XPath мультиключа для фрагмента метаданных (XPath "@ServiceID" для Service ID и XPath "EventDescription/PublishedTime" для Published Time) включают в раздел 110 перечня индексов ключей.
Вышеуказанные этапы могут быть обработаны в обратном порядке в других вариантах осуществления настоящего изобретения. Дополнительно, в зависимости от некоторых вариантов осуществления настоящего изобретения может быть удален этап обеспечения раздела 120 индекса ключа, включающего в себя представительные ключевые значения (S400), или этап обеспечения раздела (S500) перечня индексов ключей.
Далее в документе со ссылкой Фиг. 12 будет описан вышеуказанный способ поиска, предназначенный для получения метаданных, удовлетворяющих более чем одному условию поиска, осуществляемый с помощью структуры многоключевого индекса в соответствии с вариантом осуществления настоящего изобретения.
Условия поиска для осуществления поиска вводит, например, пользователь (S1100). В индексе метаданных (S1200) осуществляют поиск значения мультиключа, удовлетворяющего введенным условиям поиска. Искомый фрагмент метаданных извлекают с использованием идентифицирующей информации для фрагмента метаданных, соответствующего значению мультиключа, с использованием найденного значения мультиключа (S1300). Посредством этих этапов извлекают метаданные, удовлетворяющие условиям поиска. В условия поиска, введенные пользователем, могут быть включены поля и значение или диапазоны полей, которые подлежат поиску.
Этап поиска значения мультиключа (S1200) содержит этапы определения информации местоположения для фрагмента метаданных, к которому принадлежат поля введенных условий поиска, и информации местоположения для полей во фрагменте метаданных (S1210), поиска в разделе 110, предназначенном для перечня индексов ключей, мультиключа, состоящего из полей, содержащих информацию местоположения, идентичную определенной выше информации местоположения, осуществляемого с использованием определенной информации местоположения, и поиска в разделе 120, предназначенном для индекса ключа, найденного мультиключа (SI220), поиска в разделе 120, предназначенном для индекса ключа, представительного ключевого значения, составленного из значений полей, введенных в качестве условий поиска, и поиска раздела 130 индекса подключа, включающего значения мультиключа, находящиеся в диапазоне, обозначенном представительным ключевым значением, найденным выше (S1230), и поиска значения мультиключа, удовлетворяющего условиям поиска, в найденном выше разделе 130 индекса подключа (S1240).
На вышеуказанных этапах S1220, S1230 и S1300, этапы поиска раздела 120 индекса ключа, раздела индекса подключа и извлечения фрагмента метаданных соответственно выполняют с использованием идентифицирующей информации раздела 120 индекса ключа, идентифицирующей информации раздела индекса подключа и идентифицирующей информации фрагмента метаданных. Понятно, что, например, если диапазон поля метаданных входит как часть в условия поиска, то может быть несколько найденных значений мультиключа, и извлечено более одного фрагмента, как описано ниже в документе.
Способ поиска, как показано на Фиг. 12, может быть использован при поиске Service ID и Published Time, описанных со ссылкой на Фиг. 10, следующим образом:
Если пользователь вводит условия поиска '507-514' для Service ID и '9:30˜10:00' для Published Time (S1100), то информацию местоположения для искомого фрагмента метаданных определяют по полям комбинации, состоящей из Service ID в диапазоне "507-514" и из Published Time в диапазоне "9:30-10:00", и определяют информацию местоположения полей во фрагменте метаданных (S1210).
Введенные в качестве условий поиска Service ID и Published Time соответственно имеют (значения) "@ServiceId" и "EventDescription/PublishedTime" в качестве информации местоположения во фрагменте метаданных. На этой основе определяют информацию местоположения для искомого фрагмента метаданных в качестве атрибута искомого фрагмента, то есть XPath (S1210).
Чтобы подвести итог, по вышеуказанным этапам можно получить нижеследующее:
XPath для фрагмента:
/TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent
- XPath для Service Id: @ServiceId,
- XPath для Published Time: EventDescription/PublishedTime
- Значение Service Id: 507<=ServiceId<=514,
- Значение Published Time: 9:30<=EventDescription/PublishedTime<= 10:00.
Затем в разделе 110 перечня индексов ключей осуществляют поиск мультиключа, соответствующего XPath 111 для фрагмента метаданных и XPath 112 для Service Id/Published Time, и извлекают (S1220) идентифицирующую информацию раздела 120 индекса ключа, включающего найденный мультиключ. В настоящем варианте осуществления Service Id является более старшей по приоритету, чем Published Time. Осуществляют поиск в разделе 120 индекса ключа представительных значений ключа "509/10:00" 113a и "519/10:00" 113b, то есть представительных значений ключа, указывающих диапазоны (500-509/09:10-10:00 114a, 510-519/09:10-10:00 114b) значений мультиключа, к которым принадлежат значения мультиключа (507-514/09:30-10:00), соответствующие условиям поиска, и извлекают из раздела 120 индекса ключа (S1230) идентифицирующую информацию о разделе 130 индекса подключа, содержащего представительные значения. Осуществляют поиск значений мультиключей, имеющих значения ключей "507/09:30", "507/09:40"... "509/10:00" и "510/09:30", "510/09:40"... "514/10:00", соответствующие значениям мультиключа (507˜514/09:30-10:00), соответствующего условиям поиска, в разделе 130 индекса подключа, то есть в сегментах 114a и 114b (S1240).
Извлекают из раздела 130 индекса подключа идентифицирующую информацию о фрагменте метаданных, соответствующую значениям найденных мультиключей (информацию об идентификаторе контейнера и информацию об идентификаторе фрагмента данных, сохраненные в сегменте "target_container" и сегменте "target_handle", соответственно), и затем извлекают релевантные фрагменты метаданных с использованием извлеченной идентифицирующей информации (S1300).
На Фиг. 13 показано устройство, предназначенное для поиска метаданных в соответствии с вариантом осуществления настоящего изобретения. Устройством, осуществляющим поиск, в настоящем изобретении является устройство, выполняющее способ поиска метаданных в соответствии с вариантом осуществления настоящего изобретения, описанного выше со ссылкой на Фиг. 12.
Устройство 1000 содержит блок 1100 ввода данных, который дает возможность пользователю вводить условия поиска, приемный блок 1200, который принимает содержимое, метаданные о содержимом или индекс метаданных, запоминающее устройство 1300, в котором сохраняется принятое содержимое, метаданные о содержимом или индекс метаданных, блок 1400 управления, который осуществляет поиск значения/значений мультиключа, соответствующего входным условиям поиска от модуля 1100 ввода данных, и извлечение искомых метаданных с использованием найденного значения/значений мультиключа, и блока 1500 вывода, который выводит результат поиска, осуществленного блоком управления 1400.
Блок управления 1400 сравнивает условия поиска, введенные от блока 1100 ввода данных, со значениями мультиключа, включенными в индекс метаданных, хранимый на запоминающем устройстве.
Из этапов поиска значений мультиключа в соответствии с одним вариантом осуществления настоящего изобретения, этап поиска мультиключа, соответствующего входным условиям поиска (S1200), или этап извлечения искомого фрагмента(ов) с использованием идентифицирующей информации фрагмента, соответствующей найденному мультиключу, будет истолкован со ссылкой на описание, сделанное выше в связи с Фиг. 12.
В соответствии с настоящим изобретением обеспечены структура индекса метаданных, позволяющая более эффективные поиск и доступ к информации о содержимом, способ обеспечения индекса метаданных, имеющего такую структуру, и способ и устройство, предназначенные для поиска метаданных с использованием индекса метаданных.
ПРОМЫШЛЕННАЯ ПРИМЕНИМОСТЬ
Как описано выше, настоящее изобретение дает возможность одновременных поисков метаданных Форума TV-Anytime Forum по составным условиям. При проведении поисков метаданных Форума TV-Anytime по составным условиям непроизводительные издержки устройства поиска снижаются, таким образом позволяя уменьшить время поиска и повысить показатели эффективности устройства поиска. Однако понятно, что тогда как иллюстративные неограничивающие варианты осуществления настоящего изобретения преодолевают описанные выше недостатки и другие недостатки, которые не описаны выше, от настоящего изобретение не требуется преодолевать недостатки, описанные выше, и иллюстративные, не ограничивающие варианты осуществления настоящего изобретения, могут не преодолеть какой-либо из недостатков, описанных выше. Также понятно, что система, которая использует настоящее изобретение, включает в себя также постоянный или сменный носитель, такой как магнитные и оптические диски, ОЗУ, ПЗУ, несущая волна, и т.д., на котором способ обработки и структуры данных настоящего изобретения могут быть сохранены и распределены. Операции также могут быть распределены посредством, например, загрузки по сети, такой как Internet.
Несмотря на то, что настоящее изобретение было описано в связи с предпочтительным вариантом осуществления, показанным на чертежах, это является лишь иллюстративным. Специалистам в данной области техники будет понятно, что различные модификации и эквиваленты могут быть сделаны без выхода за рамки объема и сущности изобретения. Следовательно, объем настоящего изобретения следует определять только в соответствии прилагаемой формулой изобретения.
Изобретение относится к индексной структуре метаданных. Техническим результатом является повышение скорости поиска индекса. Для этого структура индекса метаданных включает в себя перечень мультиключей и информацию местоположения для определения мультиключей, при этом определяют информацию, соответствующую полям условий поиска, и осуществляют поиск мультиключа, соответствующего информации местоположения, после чего извлекают фрагмент метаданных с использованием найденного мультиключа. 2 н. и 4 з.п. ф-лы, 13 ил., 6 табл.
определяют информацию местоположения, соответствующую полям условий поиска в отношении метаданных,
осуществляют поиск мультиключа, соответствующего информации местоположения в отношении полей условий поиска, из индекса метаданных, и
извлекают фрагмент метаданных с использованием найденного мультиключа.
при поиске значения осуществляют поиск значения среди значений мультиключа из индекса и
при извлечении фрагмента извлекают фрагмент метаданных, соответствующий значению мультиключа, с использованием идентифицирующей информации фрагмента.
осуществляют поиск представительного значения ключа, удовлетворяющего условиям поиска, из тех представительных значений ключа индекса, которые соответствуют диапазонам значений мультиключа, и
осуществляют поиск значения в диапазоне значений, соответствующего представительному значению ключа.
| Перекатываемый затвор для водоемов | 1922 |
|
SU2001A1 |
| US 6263313 A1, 17.07.2001 | |||
| УСТРОЙСТВО ДЛЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ В ПАМЯТИ | 1996 |
|
RU2101762C1 |
| СПОСОБ УСТАНОВЛЕНИЯ В ХРАНИЛИЩЕ МЕСТОПОЛОЖЕНИЯ ОБЪЕКТА ПО ПОИСКОВОМУ ТЕМАТИЧЕСКОМУ ПРИЗНАКУ | 1994 |
|
RU2107942C1 |
