Index to a semi-structured database

• US 7,409,381 B1
• Filed: 07/30/1999
• Issued: 08/05/2008
• Est. Priority Date: 07/30/1998
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Azvine, Behnam, Turner, Raymond, Scott, Paul D., Webb, Nicholas J., Steel, Samuel W. D., Kruschwitz, Udo, Wobcke, Wayne R., De Roeck, Anne N., Tsui, Kwok C.
• Primary Examiner(s): Le; Miranda
• Application Number:
  US09/744,393
• Time in Patent Office: 3,294 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-201, 704/9, 704/1, 709/203
• US Class Current: 707/741
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and apparatus for generating an index entry for a record in a semi-structured database involves analysing each field to identify an entry within each field and to identify a sequence of characters having a format corresponding to a predetermined format. Thereafter, the method and apparatus operate to generate an index entry for the identified entry, and for at least one field, define any characters not identified as an entry as a free text entry.

Claims

1. Apparatus for accessing a semi-structured database in accordance with an input request for information, wherein the semi-structured database comprises a plurality of items, each item comprising one or more fields having a plurality of characters therein, at least one of the fields being a free text field, the apparatus comprising:

a processor;

means for accessing a data store comprising a plurality of index entries, each index entry representing a concordance between an entry in a field of an item in the semi-structured database and that item in the semi-structured database;

input means for receiving a request for information, the request comprising a natural language phrase;

a parser for parsing the received request to determine components of the request;

a slot filler for generating a slot-and-filler request having a plurality of slots, each slot corresponding to a group of index entries in said data store, the slot-filler being arranged to identify, one or more object components representing an object of the received request from the parsed request, and allocate at least one object component to a respective slot of a slot-and-filler request; and

a query constructor for accessing the data store, wherein the query constructor is arranged to compare the or each allocated object component in the slot-and-filler request with a group of index entries in said data store corresponding to the slot of the allocated component, so as to identify an index entry corresponding thereto, and to use the identified index entry to identify a corresponding item in the semi-structured database;

an index generator comprising a processor arranged, in respect of each item in the semi-structured database, to analyze each field in accordance with a predetermined criterion so as to identify an entry within said field, and to generate at least one index entry representing a concordance between an identified entry and the item corresponding to the identified entry, and store the generated index entry in the data store;

wherein for each of a plurality of predetermined formats, the processor is arranged to search said free text field to identify a sequence of characters having a format corresponding to the predetermined format, said identified sequence of characters being deemed to constitute an identified entry;

wherein for the free text field, the processor is arranged to define any data not identified as an entry as a free text entry;

wherein the free text entry comprises at least one free text word defined by a sequence of alphanumeric characters, the processor being arranged to identify at least one selected free text word for a field by comparing the free text entry with at least one selection criterion defining one or more predetermined characteristics of a selected free text word.

2. Apparatus according to claim 1, wherein the items within the semi-structured database are further arranged in groups of items, each group being located in a heading field and being identified by at least one heading entry, wherein the processor is arranged to identify a heading entry by comparing each heading field with each of a plurality of selection criteria defining one or more predetermined characteristics of a respective heading entry, and is arranged to generate index entries representing a concordance between such heading entries and the group of items in the heading field.

3. Apparatus according to claim 1, wherein the slot filler is arranged to identify verb components forming a verb or verb group in the parsed request and to allocate any such identified verb components to a slot in accordance with a predetermined mapping between verb components and slots.

4. Apparatus according to claim 3, wherein the slot filler is arranged to identify any subject components in accordance with the position of the verb or verb group within the request and to allocate any such identified subject components to a slot in accordance with a predetermined mapping between subject components and slots.

5. Apparatus according to claim 3, wherein, in the absence of identifying verb components, the slot filler is arranged to deem any components to be object components.

6. Apparatus according to claim 1, wherein the data store is part of the apparatus.