Method and apparatus for structuring the querying and interpretation of semistructured information

• US 5,826,258 A
• Filed: 10/02/1996
• Issued: 10/20/1998
• Est. Priority Date: 10/02/1996
• Status: Expired due to Term

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Junglee Corp. (Amazon.com, Inc.)
• Inventors: Rajaraman, Anand, Harinariyan, Venky, Quass, Dallan, Gupta, Ashish
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Rones, Charles L.
• Application Number:
  US08/724,943
• Time in Patent Office: 748 Days
• Field of Search: 707/3, 707/4, 707/6, 707/102, 707/10, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method is provided for determining how semistructured information is organized in disparate semistructured resources by providing a wrapper to extract information and to provide structured information (e.g., tuples of an SQL database) to a mapper coupled to a standard relational database engine. In a specific embodiment, a querying agent is provided on top of the mapper. Further according to the invention, structured high-level user queries are processed across the disparate semistructured resources using a plurality of wrappers each dedicated to a particular resource.

Claims

1. A method of generating a wrapper for accessing semistructured information in order to provide access to at least one of a plurality of attributes in said semistructured information as tuples for a relational database system, said method comprising the steps of:

examining the semistructured information to identify patterns of interest, said patterns of interest including at least one of said attributes;

generating a description file, including regular expressions, for the patterns of interest, said regular expressions specifying at least one of a plurality of locations of the attributes within the semistructured information; and

generating said wrapper based upon the description file.

2. The method of claim 1, wherein the examining step comprises the step of repeatedly examining the semistructured information for nested patterns of interest.

3. The method of claim 1, further comprising the step of cataloging, without a priori information, the patterns of interest by name and position in a nested structure.

4. The method of claim 1, further comprising the steps of:

examining a plurality of other semistructured information to identify patterns of interest that include attributes;

generating a plurality of description files including regular expressions for the patterns which specify locations of the attributes within each semistructured information; and

generating a plurality of wrappers based upon the plurality of description files in order to provide access to the attributes in the plurality of other semistructured information as tuples for the relational database system.

5. The method of claim 1, wherein the semistructured information is in Hypertext Markup Language representing a World Wide Web page.

6. The method of claim 1, wherein the wrapper is generated by a compiler that compiles the description file to produce the wrapper.

7. The method of claim 1, wherein the wrapper is generated as an interpreter that receives the description file as input.

8. The method of claim 1, further comprising the step of utilizing a mapper to translate attributes within the semistructured information accessed by the wrapper to fields in the relational database system.

9. A method for generating a parser for parsing semistructured information, said parsing to produce an input to a relational database by structuring, querying and interpreting said semistructured information to form at least one of a plurality of organized tuples, said method comprising the steps of:

a) lexically analyzing the semistructured information to identify patterns of interest;

b) cataloging, without a priori information, the patterns of interest, said cataloging further comprising;

associating a name and a position with each pattern of interest;

providing a nested structure;

incorporating each pattern of interest along with said name and said position into said nested structure;

c) examining the patterns of interest in the nested structure to identify attributes that correspond to fields of a relational schema of a relational database;

d) further examining the patterns of interest in the nested structure to identify embedded patterns of interest upon which to apply the cataloging step;

e) yet further examining the patterns of interest in the nested structure to identify links to other semistructured information sources to examine;

thereupon,

applying the lexically analyzing, cataloging, examining, further examining and yet further examining steps to said other semistructured information sources;

f) forming a plurality of regular expressions of the semistructured information in the nested structure;

g) providing said plurality of regular expressions in a definition for use by a dedicated program translator; and

h) providing the definition as input to the program translator for building said parser for the relational database.

10. The method according to claim 9, wherein the dedicated program translator is a compiler, and wherein building the parser comprises the steps of:

receiving the definition of the semistructured information as input; and

generating a program for extracting attributes from the semistructured information that correspond to fields of the relational schema to form tuples.

11. The method according to claim 9, wherein the dedicated program translator is an interpreter, and wherein building the parser comprises the steps of:

receiving the definition of the semistructured information and the semistructured information as input; and

extracting attributes from the semistructured information that correspond to fields of the relational schema to form tuples.

12. The method according to claim 9, wherein the semistructured information is produced by multiple computer programs as output.

13. A method for responding to a single high-level structured user query over a plurality of disparate semistructured information resources, comprising the steps of:

providing a wrapper for each one of the disparate semistructured information resources, each wrapper employing a definition of semistructured information for a specific semistructured information resource, each wrapper created by;

examining the semistructured information to identify patterns of interest, said patterns of interest including at least one of said attributes;

generating a description file, including regular expressions, for the patterns of interest, said regular expressions specifying at least one of a plurality of locations of the attributes within the semistructured information; and

generating said wrapper based upon the description file;

thereupon

issuing the user query through the wrappers to the plurality of disparate semistructured information resources;

receiving tuples from each one of the wrappers in response to the query;

providing the tuples to a relational database; and

executing the query on the relational database to return results to the user.

14. The method according to claim 13, wherein the providing step further comprises:

translating, via a mapper, the tuples to a schema and vocabulary of the common relational database.

15. The method according to claim 13, wherein the user query is an SQL query.

16. The method according to claim 13, wherein the semistructured information resources are built in a hypertext network.

17. A method for responding to a single high-level structured user query over a plurality of disparate semistructured information resources, comprising the steps of:

providing a wrapper for each one of the disparate semistructured information resources, each wrapper employing a definition of semistructured information for a specific semistructured information resource, each wrapper created by;

examining the semistructured information to identify patterns of interest, said patterns of interest including at least one of said attributes;

generating a description file, including regular expressions, for the patterns of interest, said regular expressions specifying at least one of a plurality of locations of the attributes within the semistructured information; and

generating said wrapper based upon the description file;

thereupon;

issuing a preselected set of load queries through the wrappers to the plurality of disparate semistructured information resources to collect tuples;

receiving the tuples from each one of the wrappers in response to the query;

storing the tuples in a common relational database; and

executing the single user query on the common relational database to return results to the user.

18. A method of generating a wrapper for accessing information in a web page, comprising the steps of:

examining the web page to identify patterns of interest that include attributes;

generating a description file including regular expressions for the patterns of interest which specify locations of the attributes within the web page; and

generating a wrapper based upon the description file said wrapper, providing access to the attributes in the web page as tuples for a relational database system.

19. The method of claim 18, wherein the examining step comprises the step of repeatedly examining the semistructured information for nested patterns of interest.

20. The method of claim 18, further comprising the step of cataloging, without a priori information, the patterns of interest by name and position in a nested structure.

21. The method of claim 18, further comprising the steps of:

examining a plurality of other web pages to identify patterns of interest that include attributes;

generating a plurality of description files including regular expressions for the patterns which specify locations of the attributes within each web page; and

generating a plurality of wrappers based upon the plurality of description files said plurality of wrappers to provide access to the attributes in the plurality of other web pages as tuples for the relational database system.

22. The method of claim 18, wherein the wrapper is generated by a compiler that compiles the description file to produce the wrapper.

23. The method of claim 18, wherein the wrapper is generated as an interpreter that receives the description file as input.

24. The method of claim 18, further comprising the step of utilizing a mapper to translate attributes within the semistructured information accessed by the wrapper to fields in the relational database system.