Approximate querying method for databases with multiple grouping attributes
AssigneeLucent Technologies Inc.
InventorsSwarup Acharya, Phillip B. Gibbons, Viswanath Poosala
Life of this patent
Estimating the term…
Abstract
An approximate querying method comprising grouping tuples within a database according to grouping attributes, determining how many tuples are needed to represent each group, selecting the tuples from a corresponding group to create a database sample, and querying the database sample. The database sample yields statistically unbiased answers when queried. The sample may be created and maintained without a priori knowledge of the data distribution within the database or the queries to be performed.
Claims38
A method for deriving a database sample comprising the steps of
- selecting grouping attributes within a relational database having tuples;
- grouping said tuples based on said grouping attributes to derive sub groups;
- applying a function to determine a number of tuples for each of said sub groups;
- and
- selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
A method for querying a database comprising the steps of:
- selecting grouping attributes within a relational database having tuples;
- grouping said tuples based on said grouping attributes to derive sub groups;
- applying a function to determine a number of tuples for each of said sub groups;
- selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group;
- and
- querying said database sample.
A method for deriving a relational database sample comprising the steps of:
- selecting a uniform sample from a database having tuples;
- selecting grouping attributes within said database;
- grouping said tuples based on said grouping attributes to derive sub groups;
- applying a function to determine a number of tuples for each of said sub groups;
- and
- adding additional tuples to said uniform sample in accordance with said function, wherein said additional tuples for each of said sub groups are obtained from a corresponding sub group within said database.
A system for deriving a database sample comprising:
- a relational database having tuples and grouping attributes;
- grouping means for grouping said tuples based on said grouping attributes to derive sub groups;
- means for determining a number of tuples for each of said sub groups;
- and
- a selector for selecting a database sample comprising tuples according to said number of tuples for each of said sub groups from a corresponding sub group.
A system for querying a database comprising:
- a relational database having tuples and grouping attributes;
- grouping means for grouping said tuples based on said grouping attributes to derive sub groups;
- means for determining a number of tuples for each of said sub groups;
- a selector for selecting a database sample of tuples according to said number of tuples for each of said sub groups from a corresponding sub group;
- and
- a querying system for querying said database sample.
Dependencies are inferred from the claim text.