Patent US5826258A successfully refreshed from Google Patents.
US5826258A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for structuring the querying and interpretation of semistructured information
Assignee: Amazon Technologies Inc
•
Filing: 1996-10-02
•
Granted: 1998-10-20
•
Expires: 2016-10-02
Abstract
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.
Inventors
- 👤 Ashish Gupta
- 👤 Venky Harinariyan
- 👤 Dallan Quass
- 👤 Anand Rajaraman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 18:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/80; G06F16/84; G06F16/86; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
101 words
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.
Claim 2
Independent Claim
101 words
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.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein the examining step comprises the step of repeatedly examining the semistructured information for nested patterns of interest.
Claim 4
Dependent Claim
27 words
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.
Claim 5
Dependent Claim
82 words
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.
Claim 6
Dependent Claim
20 words
The method of claim 1, wherein the semistructured information is in Hypertext Markup Language representing a World Wide Web page.
Claim 7
Dependent Claim
22 words
The method of claim 1, wherein the wrapper is generated by a compiler that compiles the description file to produce the wrapper.
Claim 8
Dependent Claim
20 words
The method of claim 1, wherein the wrapper is generated as an interpreter that receives the description file as input.
Claim 9
Dependent Claim
31 words
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.
Claim 10
Independent Claim
243 words
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.
Claim 11
Independent Claim
243 words
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.
Claim 12
Dependent Claim
54 words
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.
Claim 13
Dependent Claim
54 words
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.
Claim 14
Dependent Claim
18 words
The method according to claim 9, wherein the semistructured information is produced by multiple computer programs as output.
Claim 15
Independent Claim
163 words
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.
Claim 16
Independent Claim
163 words
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.
Claim 17
Dependent Claim
28 words
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.
Claim 18
Dependent Claim
14 words
The method according to claim 13, wherein the user query is an SQL query.
Claim 19
Dependent Claim
17 words
The method according to claim 13, wherein the semistructured information resources are built in a hypertext network.
Claim 20
Independent Claim
174 words
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.
Claim 21
Independent Claim
174 words
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.
Claim 22
Independent Claim
78 words
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.
Claim 23
Independent Claim
78 words
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.
Claim 24
Dependent Claim
23 words
The method of claim 18, wherein the examining step comprises the step of repeatedly examining the semistructured information for nested patterns of interest.
Claim 25
Dependent Claim
27 words
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.
Claim 26
Dependent Claim
84 words
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.
Claim 27
Dependent Claim
22 words
The method of claim 18, wherein the wrapper is generated by a compiler that compiles the description file to produce the wrapper.
Claim 28
Dependent Claim
20 words
The method of claim 18, wherein the wrapper is generated as an interpreter that receives the description file as input.
Claim 29
Dependent Claim
31 words
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.
References Cited (Backward Citations)
US4631673A
Cited
US4918588A
Cited
US4918593A
Cited
US5386556A
Cited
US5307484A
Cited
US5748954A
Cited
US5761663A
Cited
US5737592A
Cited
US5706507A
Cited
US5649186A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-19 | 2002-04-20 | 2002-10-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-19 | 2006-04-20 | 2006-10-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-19 | 2010-04-20 | 2010-10-20 | $7700.00 | Window Closed / Lapsed |