Evaluating relevance of results in a semi-structured data-base system

• US 20040111388A1
• Filed: 12/06/2002
• Published: 06/10/2004
• Est. Priority Date: 12/06/2002
• Status: Abandoned Application

• Current Assignee: Xyleme SA (Xyleme, Inc.)
• Original Assignee: Xyleme SA (Xyleme, Inc.)
• Inventors: Boiscuvier, Frederic, Koechlin, Bruno, Cluet, Sophie
• Application Number:
  US10/313,823
• Publication Number:
  US 20040111388A1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95

Abstract

A method for evaluating queries applied to semi-structured data, including, providing a query for the semi-structured data, the query includes indication of relevance ranking of sought results. The indication includes specification according to the structural positioning of words in the semi-structured data. The method further provides for evaluating the query vis-a-vis the semi-structured data in accordance with the indicated relevance ranking, and providing results, where each result includes a portion of the semi-structured data that meets the query.

Claims

1. ) A method for evaluating queries applied to semi-structured data, comprising:

i) providing a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data;

ii) evaluating the query vis-a-vis the semi-structured data in accordance with said indicated relevance ranking; and

iii) providing at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

2. ) The method according to claim 1, wherein said evaluating is performed in a pipelined fashion including:

said evaluating is stopped upon meeting a pre-defined evaluation criterion.

3. ) The method according to claim 2, wherein said criterion being a number of the results reaching or exceeding a predefined number.

4. ) The method according to claim 2, wherein in response to a user command said evaluation is resumed, and wherein said evaluation step (b) further includes:

resuming evaluating the query vis a vis the data that were not evaluated before.

5. ) The method according to claim 1, wherein said evaluating step (b) includes:

evaluating said query against said semi-structured data in a non-pipelined manner.

6. ) The method according to claim 1, wherein said evaluating step (b) includes:

evaluating said query vis-a-vis said semi-structured data in either mode (A) or (B) depending upon a predefined criterion, wherein (A) being a non-pipelined and (B) being pipelined.

7. ) The method according to claim 6, wherein said predefined criterion is based on a statistical model that estimates the number of results and wherein in case of large number of estimated results, said pipelined evaluation (B) is selected and in case of estimated small number or zero results said non-pipelined evaluation (A) is selected.

8. ) The method according to claim 2, wherein said indicating relevance ranking being by means of BESTOF operator, where BESTOF being defined as

BESTOF (F, SP, P1, P2, P3, . . . )

Where:

F;

a forest of XML nodes;

SP;

a string predicate;

P1, P2, . . . , Pn;

1 to many XPath expressions;

The result of the BESTOF operation is a re-ordered sub-part of the forest F defined as follows;

BESTOF(F, SP, P1, P2, . . . , Pn)=Fres={N1, N2, N3, . . . , Nm} with;

For all nodes N in F, if there exists j in [1,n] such that Pj applied to N satisfies SP then N is part of Fres.

For all i in [1, m] there exists j in [1,n] such that Pj applied to Ni satisfies SP. Let jmin(i) be the smallest such j for a given I

For all i in [1, mn−

1], (jmin(i)<

jmin(i+1)) or (jmin(i)=jmin(i+1) and Ni is before Ni+1 in F).

9. ) The method according to claim 8, wherein using said operator includes invoking LAUNCHRELAX, RELAX and FTISCAN functions.

10. ) The method according to claim 1, wherein said semi-structured data include XML documents.

11. ) The method according to claim 10, wherein said query language for semi-structure documents being Xquery.

12. ) A method for constructing queries for application to semi-structured data, comprising:

i. providing a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data;

ii. transmitting the query for evaluation vis-a-vis the semi-structured data in accordance with said indicated relevance ranking; and

iii. receiving at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

13. ) The method according to claim 12, wherein said evaluating is performed in a pipelined fashion including:

said evaluating is stopped upon meeting a pre-defined evaluation criterion.

14. ) The method according to claim 13, wherein said criterion being a number of the results reaching or exceeding a predefined number.

15. ) The method according to claim 13, wherein in response to a user command said evaluation is resumed, and wherein said evaluation step (b) further includes:

resuming evaluating the query vis a vis the data that were not evaluated before.

16. ) The method according to claim 12, wherein said evaluating step (b) includes:

evaluating said query against said semi-structured data in a non pipelined manner.

17. ) The method according to claim 12, wherein said evaluating step (b) includes:

evaluating said query vis-a-vis said semi-structured data in either mode (A) or (B) depending upon a predefined criterion, wherein (A) being a non-pipelined and (B) being pipelined.

18. ) The method according to claim 17, wherein said predefined criterion is based on a statistical model that estimates the number of results and wherein in case of large number of estimated results, said pipelined evaluation (B) is selected and in case of estimated small number or zero results said non-pipelined evaluation (A) is selected.

19. ) The method according to claim 13, wherein said indicating relevance ranking being by means of BESTOF operator, where BESTOF being defined as BESTOF (F, SP, P1, P2, P3, . . . )

Where:

F;

a forest of XML nodes;

SP;

a string predicate;

P1, P2, . . . , Pn;

1 to many XPath expressions;

The result of the BESTOF operation is a re-ordered sub-part of the forest F defined as follows;

BESTOF(F, SP, P1, P2, . . . , Pn)=Fres={N1, N2, N3, . . . , Nm} with;

For all nodes N in F, if there exists j in [1,n] such that Pj applied to N satisfies SP then N is part of Fres.

For all i in [1, m] there exists j in [1,n] such that Pj applied to Ni satisfies SP. Let jmin(i) be the smallest such j for a given I

For all i in [1, m−

1], (jmin(i)<

jmin(i+1)) or jmin(i)=jmin(i+1) and Ni is before Ni+1 in F).

20. ) The method according to claim 19, wherein using said operator includes invoking LAUNCHRELAX, RELAX and FTISCAN functions.

21. ) The method according to claim 12, wherein said semi-structured data include XML documents.

22. ) The method according to claim 21, wherein said query language for semi-structure documents being Xquery.

23. ) A method for constructing queries for application to semi-structured data, comprising:

i. providing a query for the semi-structured data such that said query is formatted to indicated relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data;

ii. transmitting the query for evaluation vis-a-vis the semi-structured data in accordance with said indicated relevance ranking;

iii. receiving at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

24. ) The method according to claim 23, wherein said query is in Xquery language, and wherein said data being XML documents and wherein said result being at least one document or portion thereof, that meets said query.

25. ) The method according to claim 23, wherein said query is formatted to indicated relevance ranking by means that include calling to at least one external function.

26. ) The method according to claim 24, wherein said query is formatted to indicated relevance ranking by means that include calling to at least one external function.

27. ) A method for evaluating queries applied to semi-structured data, comprising:

i. providing a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data.

ii. evaluating the query vis-a-vis the semi-structured data in accordance with said indicated relevance ranking; and

iii. providing at least one result, if any, where each result includes a portion of said semi-structured data that meets said query,

whereby, results that meet said query in compliance with said relevance ranking, are provided, irrespective of the size of the semi-structured data, provided that the user has not stopped the evaluation process.

28. ) A computer program product comprising:

computer code for constructing a query for application to semi-structured data, the computer code further facilitates incorporation in the query means for indicating relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data,

whereby said query is capable of being evaluated vis a vis the semi-structured data in accordance with said indicated relevance ranking for receiving at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

29. ) The product according to claim 28, wherein said evaluating is performed in a pipelined fashion including:

said evaluating is stopped upon meeting a pre-defined evaluation criterion.

30. ) The product according to claim 29, wherein said criterion being a number of the results reaching or exceeding a predefined number.

31. ) The product according to claim 29, wherein in response to a user command said evaluation is resumed, and wherein said evaluation step (b) further includes:

resuming evaluating the query vis a vis the data that were not evaluated before.

32. ) The product according to claim 28, wherein said evaluating step (b) includes:

evaluating said query against said semi-structured data in a non-pipelined manner.

33. ) The product according to claim 28, wherein said evaluating step (b) includes:

evaluating said query vis-a-vis said semi-structured data in either mode (A) or (B) depending upon a predefined criterion, wherein (A) being a non-pipelined and (B) being pipelined.

34. ) The product according to claim 33, wherein said predefined criterion is based on a statistical model that estimates the number of results and wherein in case of large number of estimated results, said pipelined evaluation (B) is selected and in case of estimated small number or zero results said non-pipelined evaluation (A) is selected.

35. ) The product according to claim 29, wherein said indicating relevance ranking being by means of BESTOF operator, where BESTOF being defined as BESTOF (F, SP, P1, P2, P3, . . . )

Where:

F;

a forest of XML nodes;

SP;

a string predicate;

P1, P2, . . . , Pn;

1 to many XPath expressions;

The result of the BESTOF operation is a re-ordered sub-part of the forest F defined as follows;

BESTOF(F, SP, P1, P2, . . . , Pn)=Fres={N1, N2, N3, . . . , Nm} with;

For all nodes N in F, if there exists j in [1,n] such that Pj applied to N satisfies SP then N is part of Fres.

For all i in [1, m] there exists j in [1,n] such that Pj applied to Ni satisfies SP. Let jmin(i) be the smallest such j for a given I

For all i in [1, m−

1], (jmin(i)<

jmin(i+1)) or (jmin(i)=jmin(i+1) and Ni is before Ni+1 in F).

36. ) The product according to claim 35, wherein using said operator includes invoking LAUNCHRELAX, RELAX and FTISCAN functions.

37. ) The product according to claim 28, wherein said semi-structured data include XML documents.

38. ) The product according to claim 37, wherein said query language for semi-structure documents being Xquery.

39. ) A system for evaluating queries applied to semi-structured data, comprising:

receiver for receiving a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data;

evaluator for evaluating the query vis-a-vis the semi-structured data in accordance with said indicated relevance ranking;

said evaluation is capable of providing at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

40. ) A system for constructing queries for application to semi-structured data, comprising:

generator for generating a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data;

transmitter for transmitting the query for evaluation vis-a-vis the semi-structured data in accordance with said indicated relevance ranking; and

receiver for receiving at least one result, if any, where each result includes a portion of said semi-structured data that meets said query.

41. ) A system for evaluating queries applied to semi-structured data, comprising:

receiver for receiving a query for the semi-structured data, the query includes indication of relevance ranking of sought results;

wherein said indication includes specification according to the structural positioning of words in the semi-structured data.

evaluator for evaluating the query vis-a-vis the semi-structured data in accordance with said indicated relevance ranking;

said evaluator is capable of providing at least one result, if any, where each result includes a portion of said semi-structured data that meets said query,

whereby, results that meet said query in compliance with said relevance ranking, are provided, irrespective of the size of the semi-structured data, provided that the user has not stopped the evaluation process.