Methods and apparatus for specifying and processing descriptive queries for data sources

• US 7,487,142 B2
• Filed: 06/10/2004
• Issued: 02/03/2009
• Est. Priority Date: 06/10/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Castro, Paul C., Misra, Archan, Cohen, Norman Howard
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Le; Jessica N
• Application Number:
  US10/865,058
• Publication Number:
  US 20050278285A1
• Time in Patent Office: 1,699 Days
• Field of Search: 707/1, 707 3- 6, 707/10, 707/101, 707/104.1, 705/10, 705/14, 705/1, 715/500, 715/513, 709/218
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Improved descriptive query techniques are provided. More particularly, techniques are provided for specifying and processing descriptive queries for data providers grouped into provider kinds with hierarchical containment relationships. The query may include arbitrary boolean combinations of arbitrary tests on the values of attributes of the data providers.

Claims

1. A method of processing descriptive queries for data sources, comprising the steps of:

given a set of named data providers, each distinguished by a type of data the data provider provides and a set of attributes each with a unique name and a particular type of value, and a grouping of the data providers into named provider kinds, such that data providers grouped into the same provider kind provide the same type of data and have the same set of attributes;

obtaining a descriptive query, the descriptive query comprising the name of a provider kind and a specification of a mapping from an assignment of one or more values for one or more attributes of the data provider to one of a true value and a false value; and

resolving the descriptive query, the resolving step comprising obtaining the names of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query maps the one or more values of the one or more attributes of the data provider to the true value;

wherein the mapping specification comprises a boolean-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes;

wherein the boolean-valued expression is an XQuery expression evaluated in the context of an XML document that specifies the values of the attributes of the data provider;

wherein each data provider has a set of uniquely named activation parameters, each of a specified type;

wherein data providers grouped into the same provider kind have activation parameters with the same set of names, with identically named activation parameters of different data providers of the same provider kind having the same type, and wherein the descriptive query includes an assignment of values to activation parameters, with the value assigned to an activation parameter being of the type of that activation parameter, and wherein the resolving step further comprises obtaining the names of data providers in the set of named data providers, activated with the assignment of activation parameter values in the descriptive query, that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value;

wherein the descriptive query further comprises the specification of a selection mechanism for selecting a subset of a set of data providers; and

wherein the resolving step further comprises obtaining the names of data providers in the subset selected by the selection mechanism specified in the descriptive query from the set of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value.

2. The method of claim 1, wherein the selection mechanism selects one arbitrary member of the set of data providers or all members of the set of data providers.

3. The method of claim 1, wherein the specification of a selection mechanism comprises the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value and the specification of a mechanism for selecting a subset of a set of data providers given the numeric value to which the mapping maps the attribute values of each data provider in the set.

4. The method of claim 3, wherein the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value comprises a number-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes.

5. The method of claim 4, wherein the number-valued expression is an XQuery expression evaluated in the context of an XML document that specifies the values of the attributes of the data provider.

6. The method of claim 3, wherein the specification of a mechanism for selecting a subset of a set of data providers given the numeric value comprises selecting all data providers with numeric values above a given threshold.

7. The method of claim 3, wherein the specification of a mechanism for selecting a subset of a set of data providers given the numeric value comprises selecting the N data providers with the highest numeric values for a specified value of N.

8. The method of claim 3, wherein the specification of a mechanism for selecting a subset of a set of data providers given the numeric value comprises selecting the first N data providers found regardless of their numeric values for a specified value of N.

9. The method of claim 3, wherein the specification of a mechanism for selecting a subset of a set of data providers given the numeric value comprises selecting all data providers found within a time interval T regardless of their numeric values.

10. The method of claim 1, wherein a first provider kind is designated as a subkind of a second provider kind if the type of the data provided by the first provider kind is a subtype of the type of the data provided by the second provider kind, and wherein the resolving step alternatively obtains the names of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query, or to any subkind of the provider kind, and for which the mapping specified in the descriptive query maps the values of the attributes of the data provider to the true value.

11. The method of claim 1, wherein a first provider kind is designated as a subkind of a second provider kind if:

the type of the data provided by the first provider kind is a subtype of the type of the data provided by the second provider kind;

the set of activation-parameter names of the first provider kind is a subset of the set of activation parameter names of the second provider kind; and

the type of each activation parameter of the first provider kind is a supertype of the type of the identically named activation parameter of the second kind;

wherein the resolving step alternatively obtains the names of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query, or to any subkind of the provider kind, and for which the mapping specified in the descriptive query maps the values of the attributes of the data provider to the true value.

12. The method of claim 1, wherein at least one data provider comprises the application of a stream transformer to a stream of data provided by one or more other data providers.

13. The method of claim 12, further comprising:

providing a set of templates for the specification of provider kinds, in which one or more entities are replaced by one or more template-parameter symbols, wherein substitution of template-parameter values for the template-parameter symbols in a template results in an instance of the template, uniquely specifying a provider kind;

providing a set of synthesis rules, each asserting that an instance of a specified template is synthesized by applying a specified stream transformer to the stream of data provided by the instances of one or more specified templates, provided that the instances are obtained by replacing all occurrences a given template-parameter symbol in the rule with the same template-parameter value;

wherein the resolving step alternatively obtains the names of data providers, either belonging to the set of named data providers or synthesized in accordance with the set of synthesis rules, that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query maps the values of the attributes of the data provider to the true value.

14. Apparatus for processing descriptive queries for data sources, comprising:

a memory; and

at least one processor coupled to the memory and operative to, given a set of named data providers, each distinguished by a type of data the data provider provides and a set of attributes each with a unique name and a particular type of value, and a grouping of the data providers into named provider kinds, such that data providers grouped into the same provider kind provide the same type of data and have the same set of attributes;

(i) obtain a descriptive query, the descriptive query comprising the name of a provider kind and a specification of a mapping from an assignment of one or more values for one or more attributes of the data provider to one of a true value and a false value; and

(ii) resolve the descriptive query, the resolving step comprising obtaining the names of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query maps the one or more values of the one or more attributes of the data provider to the true value;

wherein the mapping specification comprises a boolean-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes;

wherein the boolean-valued expression is an XQuery expression evaluated in the context of an XML document that specifies the values of the attributes of the data provider;

wherein each data provider has a set of uniquely named activation parameters, each of a specified type;

wherein data providers grouped into the same provider kind have activation parameters with the same set of names, with identically named activation parameters of different data providers of the same provider kind having the same type, and wherein the descriptive query includes an assignment of values to activation parameters, with the value assigned to an activation parameter being of the type of that activation parameter, and wherein the resolving step further comprises obtaining the names of data providers in the set of named data providers, activated with the assignment of activation parameter values in the descriptive query, that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value;

wherein the descriptive query further comprises the specification of a selection mechanism for selecting a subset of a set of data providers; and

wherein the resolving step further comprises obtaining the names of data providers in the subset selected by the selection mechanism specified in the descriptive query from the set of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value.

16. The apparatus of claim 14, wherein the selection mechanism selects one arbitrary member of the set of data providers or all members of the set of data providers.

17. The apparatus of claim 14, wherein the specification of a selection mechanism comprises the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value and the specification of a mechanism for selecting a subset of a set of data providers given the numeric value to which the mapping maps the attribute values of each data provider in the set.

18. The apparatus of claim 17, wherein the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value comprises a number-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes.

15. An article of manufacture for processing descriptive queries for data sources, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

given a set of named data providers, each distinguished by a type of data the data provider provides and a set of attributes each with a unique name and a particular type of value, and a grouping of the data providers into named provider kinds, such that data providers grouped into the same provider kind provide the same type of data and have the same set of attributes;

obtaining a descriptive query, the descriptive query comprising the name of a provider kind and a specification of a mapping from an assignment of one or more values for one or more attributes of the data provider to one of a true value and a false value; and

resolving the descriptive query, the resolving step comprising obtaining the names of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query maps the one or more values of the one or more attributes of the data provider to the true value;

wherein the mapping specification comprises a boolean-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes;

wherein the boolean-valued expression is an XQuery expression evaluated in the context of an XML document that specifies the values of the attributes of the data provider;

wherein each data provider has a set of uniquely named activation parameters, each of a specified type;

wherein data providers grouped into the same provider kind have activation parameters with the same set of names, with identically named activation parameters of different data providers of the same provider kind having the same type, and wherein the descriptive query includes an assignment of values to activation parameters, with the value assigned to an activation parameter being of the type of that activation parameter, and wherein the resolving step further comprises obtaining the names of data providers in the set of named data providers, activated with the assignment of activation parameter values in the descriptive query, that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value;

wherein the descriptive query further comprises the specification of a selection mechanism for selecting a subset of a set of data providers; and

wherein the resolving step further comprises obtaining the names of data providers in the subset selected by the selection mechanism specified in the descriptive query from the set of data providers in the set of named data providers that belong to the provider kind specified in the descriptive query and for which the mapping specified in the descriptive query mares the values of the attributes of the data provider to the true value.

19. The article of manufacture of claim 15, wherein the selection mechanism selects one arbitrary member of the set of data providers or all members of the set of data providers.

20. The article of manufacture of claim 15, wherein the specification of a selection mechanism comprises the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value and the specification of a mechanism for selecting a subset of a set of data providers given the numeric value to which the mapping maps the attribute values of each data provider in the set.

21. The article of manufacture of claim 20, wherein the specification of a mapping from an assignment of values for attributes of a data provider to a numeric value comprises a number-valued expression in which the names of the attributes of a data provider appear, representing the assigned values of the attributes.

22. The article of manufacture of claim 21, wherein the number-valued expression is an XQuery expression evaluated in the context of an XML document that specifies the values of the attributes of the data provider.