DATA PROCESSING METHOD, DATA QUERY METHOD IN A DATABASE, AND CORRESPONDING DEVICE

• US 20140012858A1
• Filed: 06/27/2013
• Published: 01/09/2014
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Kun, Yuan, Yu, Yue, Zhang, Zou, Jia, Wang, Tianyi
• Granted Patent: US 9,471,612 B2
• Time in Patent Office: Days
• US Class Current: 707/743
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

A data processing method, data query method in a database, and corresponding device. A data processing, wherein a query request for data records includes information indicating a source and destination IP address, the source IP address including N sections, the destination IP address including M sections, both M and N being positive integers, the method including: determining an index encoding manner for the database, wherein the index is an one-dimensional index including N+M sections, the encoding manner specifying a variation sequence of various sections for the index, at least one of the source IP address and the destination address indicated by the information contained in the possible query request including at least one section having a wildcard character, wherein according to the index, for any possible query requests, successive data records can be obtained as a query result; according to the encoding manner, establishing the index for the data records.

Claims

1. A computer implemented data processing method for a database, wherein the computer includes a processor communicatively coupled to a memory, wherein a query request for data records in the database comprises information indicating a source IP address and a destination IP address, the source IP address comprising N sections, the destination IP address comprising M sections, both M and N being positive integers, the method comprising:

determining an index encoding manner for the database, wherein the index is an one-dimensional index comprising N+M sections, the encoding manner specifying a variation sequence of various sections for the index, wherein according to the index, for any possible query requests, successive data records can be obtained as a query result, at least one of the source IP address and the destination address indicated by the information contained in the possible query request comprise at least one section having a wildcard character, the wildcard character representing an arbitrary value in an allowed range; and

according to the encoding manner, establishing the index for the data records.

2. The computer implemented data processing method according to claim 1, wherein the encoding manner is able to cover all of the possible query requests, wherein, if the source IP address and the destination IP address indicated by the information contained in a query request have totally W sections having wildcard characters and the W sections containing wildcard characters correspond to W sections varying first in the index encoded in an encoding manner, then the query request is covered by the encoding manner.

3. The computer implemented data processing method according to claim 2, wherein determining the index encoding manner for the database comprises:

classifying all possible query requests, wherein for query requests in the same class, if there are totally Y sections containing wildcard characters in a source IP address and a destination IP address indicated by information contained in a query request, source IP address and destination IP address indicated by information contained in other query requests within the class have wildcard characters contained in the corresponding Y sections;

determining the number of classes of the possible query requests contained in a maximum mutually exclusive set, wherein for any two classes of query requests in the mutually exclusive set, the two classes of query requests cannot be covered by one encoding manner; and

determining X kinds of encoding manners, wherein X is the number of classes of all possible query requests contained in the maximum mutually exclusive set.

4. The computer implemented data processing method according to claim 3, wherein determining X kinds of encoding manners comprises:

selecting X kinds of encoding manners from a set of encoding manners comprising all possible encoding manners; and

if the selected X kinds of encoding manners can cover all possible query requests, determining the X kinds of encoding manners as the finally determined encoding manners.

5. The computer implemented data processing method according to claim 3, wherein after classifying all of the possible query requests, the method further comprises:

obtaining a (P+1)×

(Q+1) matrix, if all of the possible query requests are classified into S classes, each of S elements within the matrix represents a class of query requests, wherein one of P and Q represents the maximum number of sections containing wildcard characters in the source IP address for any possible query request and the other represents the maximum number of sections containing wildcard characters in the destination IP address for any possible query request; and

determining the number of classes of the possible query requests contained in a maximum mutually exclusive set comprises;

determining the number of classes of the possible query requests contained in a maximum mutually exclusive set according to the matrix;

wherein, source IP addresses and destination IP addresses indicated by information contained in query requests represented by elements in the matrix satisfy one of the following rules;

the number of sections containing wildcard characters in the source IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually decreases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually decreases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually decreases from up to lower;

or

the number of sections containing wildcard characters in the destination IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually decreases from up to lower.

6. The computer implemented data processing method according to claim 5, wherein determining X kinds of encoding manners comprises:

determining the X kinds of encoding manners according to the matrix.

7. The computer implemented data processing method according to claim 5, wherein determining the number of classes of the possible query requests contained in a maximum mutually exclusive set according to the matrix comprises:

determining the number of classes of the possible query requests contained in a maximum mutually exclusive set according to position relationships among the elements in the matrix.

8. The computer implemented data processing method according to claim 6, wherein determining X kinds of encoding manners according to the matrix comprises:

determining the X kinds of encoding manners according to paths constructed by elements in the matrix.

9. The method according to claim 1, wherein the method further comprises:

receiving an instruction for specifying a range of the possible query requests.

10. A computer implemented data query method, wherein the computer includes a processor communicatively coupled to a memory, the method comprising:

receiving a query request, the query request containing information indicating a source IP address and a destination IP address, at least one of the source IP address and the destination IP address comprising at least one section having a wildcard character, the wildcard character representing an arbitrary value in an allowed range;

linearizing the source IP address and the destination IP address; and

according to the linearized IP address, searching in a database having an one-dimensional index to obtain successive data records as a query result, wherein the data records in the database have been indexed according to the method comprising;

determining an index encoding manner for the database, wherein the index is an one-dimensional index comprising N+M sections, the encoding manner specifying a variation sequence of various sections for the index, wherein according to the index, for any possible query requests, successive data records can be obtained as a query result, at least one of the source IP address and the destination address indicated by the information contained in the possible query request comprise at least one section having a wildcard character, the wildcard character representing an arbitrary value in an allowed range; and

according to the encoding manner, establishing the index for the data records.

11. The computer implemented data query method according to claim 10, wherein linearizing the source IP address and the destination IP address comprises:

linearizing the source IP address and the destination IP address according to each of index encoding manners for the database.

12. The computer implemented data query method according to claim 10, wherein linearizing the source IP address and the destination IP address comprises:

determining an index encoding manner covering the query request; and

linearizing the source IP address and the destination IP address according to the encoding manner.

13. A computer readable storage medium tangibly embodying a computer readable non-transitory program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of the method for data query according to claim 10.

14. A device for data processing in a database, wherein a query request for data records in the database contains information indicating a source IP address and a destination IP address, the source IP address comprising N sections, the destination IP address comprising M sections, both M and N being positive integers, the device comprising:

an encoding module, configured to determine an index encoding manner of the database, wherein the index is an one-dimensional index comprising N+M sections, the encoding manner specifying a variation sequence of various sections of the index, wherein according to the index, for any possible query requests, successive data records can be obtained as a query result, at least one of the source IP address and the destination address indicated by the information contained in the possible query request comprise at least one section having a wildcard character, the wildcard character representing an arbitrary value in an allowed range; and

an index module, configured to establish the index for the data records according to the encoding manner.

15. The data processing device according to claim 14, wherein the encoding manner is capable of covering all of the possible query requests, wherein if the source IP address and the destination IP address indicated by the information contained in a query request have totally W sections containing wildcard characters and the W sections containing wildcard characters correspond to W sections varying first in the index encoded in an encoding manner, then the query request is covered by the encoding manner.

16. The data processing device according to claim 15, wherein the encoding module comprises:

a classification sub-module, configured to classify all of the possible query requests, wherein for query requests in the same class, if there are totally Y sections containing wildcard characters in a source IP address and a destination IP address indicated by information contained in a query request, a source IP address and a destination IP address indicated by information contained in other query requests within the class have wildcard characters contained in the corresponding Y sections;

a disjoint sub-module, configured to determine the number of classes of the possible query requests contained in a maximum mutually exclusive set, wherein for any two classes of query requests in the mutually exclusive set, the two classes of query requests cannot be covered by any encoding manner; and

a determination module, configured to determine X kinds of encoding manners, wherein X is the number of classes of all possible query requests contained in the maximum mutually exclusive set.

17. The data processing device according to claim 16, wherein the encoding module further comprises:

a matrix sub-module, configured to get a (P+1)×

(Q+1) matrix, if all of the possible query requests are classified into S classes, each of S elements within the matrix represents a class of query requests, wherein one of P and Q represents the maximum number of sections containing wildcard characters in the source IP address for any possible query request and the other represents the maximum number of sections containing wildcard characters in the destination IP address for any possible query request;

the disjoint sub-module is further configured to determine determining the number of classes of the possible query requests contained in a maximum mutually exclusive set according to the matrix; and

the determination module is configured to determine X kinds of encoding manners according to the matrix, wherein, source IP addresses and destination IP addresses indicated by information contained in query requests represented by elements in the matrix satisfy one of the following rules;

the number of sections containing wildcard characters in the source IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually decreases from up to lower;

the number of sections containing wildcard characters in the source IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the destination IP addresses gradually decreases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually increases from up to lower;

the number of sections containing wildcard characters in the destination IP addresses gradually decreases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually decreases from up to lower;

or

the number of sections containing wildcard characters in the destination IP addresses gradually increases from left to right and the number of sections containing wildcard characters in the source IP addresses gradually decreases from up to lower.

18. The data processing device according to claim 17, wherein the disjoint sub-module is particularly configured to determine the number of classes of the possible query requests contained in a maximum mutually exclusive set according to position relationships between elements in the matrix and the determination sub-module is particularly configured to determine the X kinds of encoding manners according to paths constructed by elements in the matrix.

19. The data processing device according to claim 14, wherein the device further comprises:

a receiving module, configured to receive an instruction for specifying a range of the possible query requests.

20. A data query device, comprising:

a receiving module, configured to receive a query request, comprising information indicating a source IP address and a destination IP address, at least one of the source IP address and the destination IP address comprising at least one section having a wildcard character, the wildcard character representing an arbitrary value in an allowed range;

a linearization module, configured to linearize the source IP address and the destination IP address; and

a search module, configured to search in a database having a one-dimensional index according to the linearized IP address to obtain successive data records as a query result, wherein the data records in the database have been indexed.