Method and device for extracting information from a database

• US 6,236,986 B1
• Filed: 05/21/1997
• Issued: 05/22/2001
• Est. Priority Date: 09/21/1994
• Status: Expired due to Term

• Current Assignee: QlikTech International AB (Qlik Technologies)
• Original Assignee: QlikTech International AB (Qlik Technologies)
• Inventors: Fransson, Håkan, Berg, Björn, Gestrelius, Staffan
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US08/809,403
• Time in Patent Office: 1,462 Days
• Field of Search: 707/3, 707/205, 707/10, 707/203, 707/1-2, 707/4, 707/103, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention relates to a method and a device for extracting information from a database, which comprises a plurality of data records, each data record comprising at least two data elements, each data element being defined by a data element type and a data element value. First, the data records are read into the primary memory of a computer, so that all processing of the data may be done off-line. Then, the data element values are binary-coded and stored in one or more tables. When the selection of at least one data element value is detected, all binary-coded data element values are examined to obtain all data records implied by selection. Due to the binary-coding, these data records are found very quickly. Finally the data element values implied by the selection is kept track of in a status set.

Claims

1. A method for extracting information from a database, which comprises a plurality of data records, each data record comprising at least two data elements, each of the data elements being defined by a data element type and a data element value, the data element values for at least some of the data elements being different and the data element values for at least some of the data elements being the same, the method being characterized by the steps of

assigning a binary code to each data element value of each data element type, different binary codes being assigned to different data element values, the same binary codes being assigned to the same data element values, the assignment of binary codes to different data element values being made arbitrarily with respect to the data elements;

storing the data records in a binary-coded form that uses the assigned binary codes to express the data element values of the data records;

detecting a selection of at least one of the data element values;

examining the binary-coded data records to obtain all data element values that are implied by the selection; and

keeping track, in a status set, of all data element values implied by the selection.

2. A method as set forth in claim 1, characterised by the further step of presenting at least those data element values implied by the selection to the user in human-readable form.

3. A method as set forth in claim 1, characterised in that for each further detection of the selection of at least one of the data element values implied by the previous selection, the step of examining the binary-coded data records and the step of keeping track of all data element values implied by the selection are repeated.

4. A method as set forth in claim 1, characterised in that all data element values which are not excluded by the detected selection are initially included in the status set and in that said examining step comprises the steps of finding all data records having data element values which all belong to the status set and excluding from the status set those data element values which do not appear in any of the data records found in the finding step.

5. A method as set forth in claim 4, characterised in that the status set comprises one status vector for each data element type, each status vector having one element for each data element value of the corresponding data element type and that said step of examining comprises the step of setting each element of the status vectors corresponding to a data element value implied by said selection of at least one of the data element values at a first value and each element of the status vectors corresponding to a data element value not implied by said selection at a second value.

6. A method as set forth in claim 2, characterised by the further step of providing one frequency vector for each data element type, each frequency vector having one element for each data element value of the corresponding data element type, said examining step comprising the step of incrementing by one the frequency vector elements corresponding to the data element values of those data records in which all data element values belong to the status set.

7. A method as set forth in claim 6, characterised by the further step of eliminating, from the status set, each data element value corresponding to a frequency vector element having a frequency count which is zero when all the data records have been examined.

8. A method as set forth in claim 2, wherein the data records of the database are organized in two or more tables, characterised in that the data records of the tables are examined repetitively until the elements of the status set no longer change.

9. A method as set forth in claim 6, characterised in that the method comprises the step of detecting that the data element values of a first data element type are related by a logical AND, and that said step of detecting the selection of at least one of the data element values comprises the detection of the selection of n data element values of said first data element type, and that the step of obtaining the data element values implied by the selection comprises the step of obtaining those data element values of a second data element type which have a frequency vector element value of n.

10. A method as set forth in claim 9, characterised by the further step of using said obtained data element values of the second data element type as a selection to obtain the data element values of the first data element type excluded by said selection of n data element values of the first data element type.

11. A method as set forth in claim 2, characterised in that said plurality of data records read into the primary memory comprise one default data record, in which the data element value of at least one data element type is unspecified, the remaining data records being ordinary data records of which all data element values are specified, and that said step of examining comprises the step of determining that the default data record is not a data record implied by said selection of at least one of the data element values, if, and only if, the number of data records implied by said selection and having a data element value of the same type as the unspecified data element value that is unique, equals the number of selected data element values of the same data element type as the unspecified value.

12. A method as set forth in claim 2, characterised in that said plurality of data records read into the primary memory of the computer are presented on the display of the computer in the form of a plurality of lists, each list containing the data element values of a different data element type and each data element value appearing only once in each list, data element values implied by the selection being indicated in a first way and data element values not implied by the selection being indicated in a second way.

13. A device for extracting information from a database, which comprises a plurality of data records, each data record comprising at least two data elements each of the data elements being defined by a data element type and a data element value, the data element values for at least some of the data elements being different and the data element values for at least some of the data elements being the same, the device being characterized by

means for assigning a binary code to each data element value of each data element type, different binary codes being assigned to different data element values, the same binary codes being assigned to the same data element values, the assignment of binary codes to different data element values being made arbitrarily with respect to the data elements;

storing the data records in a binary-coded form that uses the assigned binary-codes to express the data element values of the data records;

means for detecting the selection of at least one of the data element values;

means for examining the binary-coded data records to obtain all data element values that are implied by the selection; and

means for keeping track, in a status set, of all data element values implied by the selection.