System and method for providing structure and content scoring for XML

• US 8,005,817 B1
• Filed: 11/30/2005
• Issued: 08/23/2011
• Est. Priority Date: 11/30/2005
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Amer-Yahia, Sihem, Koudas, Nikolas, Marian, Amelie, Srivastava, Divesh, Toman, David
• Primary Examiner(s): Thai, Hanh B
• Application Number:
  US11/290,858
• Time in Patent Office: 2,092 Days
• Field of Search: 707 1- 10, 707101-102, 707/104.1, 707/713, 707/715
• US Class Current: 707/713
• CPC Class Codes: G06F 16/835 Query processing

Abstract

A system, method and computer readable medium are disclosed. The method embodiment relates to a method of computing score of candidate answers to a database query. The method comprises receiving a database query, assigning a first score to a match to the query, the first score being associated with a relative importance of an individual keyword in a collection of documents based on all structural and content predicates in the query, assigning a second score to the match, the second score being associated with a relative importance of a keyword in an individual document and using the assigned first score and second score to compute an answer score for the query.

Claims

1. A method of computing score of candidate answers to a database query, the method comprising:

receiving the database query;

converting the database query to a binary predicate query;

assigning a first score to a match to the binary predicate query, the database query organized as a node labeled tree and the first score being associated with a relative importance of an individual keyword in a collection of documents, each document in the collection of documents organized as the node labeled tree, based on all structural and content predicates in the database query, wherein assigning the first score captures all the structure and content predicates in the database query by applying an edge relaxation, a leaf deletion relaxation and a subtree promotion relaxation to the node labeled tree of the database query;

assigning a second score to the match, the second score being associated with a relative importance of a keyword in an individual document in the collection of documents; and

computing an answer score for the database query based on the first score and second score.

2. The method of claim 1, wherein assigning the second score to the match comprises assigning the second score based an inverse document frequency.

3. The method of claim 2, wherein assigning the second score to the match comprises assigning a term frequency score.

4. The method of claim 1, wherein the database query is an XML query.

5. The method of claim 4, further comprising:

precomputing and storing inverse document frequencies for all possible relations of the XML query.

6. The method of claim 5, wherein precomputing is performed using at least one of a query relaxation directed acyclic and a query matrix.

7. The method of claim 1, wherein the query is a twig query and the method further comprises:

generating an approximate answer to the twig query by generating at least one relaxed twig query.

8. The method of claim 7, further comprising organizing the at least one relaxed twig query into a directed acyclic graph.

9. The method of claim 1, wherein the answer score is computed using top-k processing.

10. The method of claim 1, wherein the content predicates further comprise keyword predicates.

11. A non-transitory computer-readable medium storing instructions for controlling a computing device to compute a score of candidate answers to a database query, the instructions comprising:

receiving the database query;

converting the database query to a binary predicate query;

assigning a first score to a match to the binary predicate query, the database query organized as a node labeled tree and the first score being associated with a relative importance of an individual keyword in a collection of documents, each document in the collection of documents organized as the node labeled tree, based on all structural and content predicates in the database query, wherein assigning the first score captures all the structure and content predicates in the database query by applying an edge relaxation, a leaf deletion relaxation and a subtree promotion relaxation to the node labeled tree of the database query;

assigning a second score to the match, the second score being associated with a relative importance of a keyword in an individual document in the collection of documents; and

computing an answer score for the database query based on the assigned first score and second score.

12. The non-transitory computer-readable medium of claim 11, wherein assigning the second score to the match comprises assigning the second score based an inverse document frequency.

13. The non-transitory computer-readable medium of claim 12, wherein assigning the second score to the match comprises assigning a term frequency score.

14. The non-transitory computer-readable medium of claim 11, wherein the query is a twig query and the method further comprises:

generating an approximate answer to the twig query by generating at least one relaxed twig query.

15. The non-transitory computer-readable medium of claim 14, wherein the instructions further comprise organizing the at least one relaxed twig query into a directed acyclic graph.

16. The non-transitory computer-readable medium of claim 14, wherein the database query is an XML query, and wherein the instructions further comprise:

precomputing and storing inverse document frequencies for all possible relations of the XML query.

17. The non-transitory computer-readable medium of claim 16, wherein precomputing is performed using at least one of a query relaxation directed acyclic graph and a query matrix.

18. A system for computing score of candidate answers to a database query, the system comprising:

a processor;

a first module configured to control the processor to receive the database query;

a second module configured to control the processor to convert the database query to a binary predicate query;

a third module configured to control the processor to assign a first score to a match to the binary predicate query, the database query organized as a node labeled tree and the first score being associated with a relative importance of an individual keyword in a collection of documents, each document in the collection of documents organized as the node labeled tree, based on all structural and content predicates in the database query, wherein assigning the first score captures all the structure and content predicates in the database query by applying an edge relaxation, a leaf deletion relaxation and a subtree promotion relaxation to the node labeled tree of the database query;

a fourth module configured to control the processor to assign a second score to the match, the second score being associated with a relative importance of a keyword in an individual document in the collection of documents; and

a fifth module configured to control the processor to use the assigned first score and second score to compute an answer score for the database query.