Search apparatus and method using order pattern including repeating pattern

• US 6,912,526 B2
• Filed: 03/07/2003
• Issued: 06/28/2005
• Est. Priority Date: 04/16/2002
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Akaboshi, Naoki
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US10/383,064
• Publication Number:
  US 20030195874A1
• Time in Patent Office: 844 Days
• Field of Search: 707 1-100, 707101-1041, 707/3, 707/4, 707/6, 364/419.02, 364/419.08, 364/419.16, 381/43, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• 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/99936 Pattern matching access

Abstract

An order relation extracted from a search pattern query is converted into a deterministic finite automaton (DFA). A process of determining whether or not a state transition can be performed by the DFA using each record, and of registering a transition destination and history information in a state transition set, is repeated, thereby obtaining a combination of records corresponding to the search pattern query.

Claims

1. A search method of searching for a combination of records from a set of records consisting of a plurality of attributes, comprising

extracting order relation among a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, the order relation defined based on an order of an attribute value, from a search pattern query that includes a repetition of an event and that is designated using the plurality of events and the order relation, and converting the extracted order relation into a deterministic finite automaton;

repeating a process of reading into a memory one or more records positioned in a same order position from the set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition;

obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached an end state of the deterministic finite automaton when the end state is registered in the state transition set as a transition destination; and

outputting the obtained combination of records as a search result.

2. A search apparatus searching for a combination of records from a set of records consisting of a plurality of attributes, comprising:

an input device inputting a search pattern query that includes a repetition of an event and that is designated using a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, and using an order relation among the plurality of events, which is defined based on an order of an attribute value;

a conversion device extracting the order relation from the search pattern query, and converting the extracted order relation into a deterministic finite automaton;

a search device repeating a process of, reading one or more records positioned in a same order position from a set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition, and when an end state of the deterministic finite automaton is registered in the state transition set as a transition destination, obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached the end state; and

an output device outputting the obtained combination of records as a search result.

3. A search apparatus searching for a combination of records from a set of records consisting of a plurality of attributes, comprising:

input means for inputting a search pattern query that includes a repetition of an event and that is designated using a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, and using an order relation among the plurality of events, which is defined based on an order of an attribute value;

conversion means for extracting the order relation from the search pattern query, and converting the extracted order relation into a deterministic finite automaton;

search means for repeating a process of, reading one or more records positioned in a same order position from a set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition, and when an end state of the deterministic finite automaton is registered in the state transition set as a transition destination, obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached the end state; and

output means for outputting the obtained combination of records as a search result.

4. A propagation signal propagating a program to a computer for searching for a combination of records from a set of records consisting of a plurality of attributes, the program enabling the computer to perform;

extracting order relation among a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, the order relation defined based on an order of an attribute value, from a search pattern query that includes a repetition of an event and that is designated using the plurality of events and the order relation, and converting the extracted order relation into a deterministic finite automaton;

repeating a process of reading into a memory one or more records positioned in a same order position from the set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition;

obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached an end state of the deterministic finite automaton when the end state is registered in the state transition set as a transition destination; and

outputting the obtained combination of records as a search result.

5. A computer-readable recording medium recording a program for enabling a computer that searches for a combination of records from a set of records consisting of a plurality of attributes, to perform:

extracting order relation among a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, the order relation defined based on an order of an attribute value, from a search pattern query that includes a repetition of an event and that is designated using the plurality of events and the order relation, and converting the extracted order relation into a deterministic finite automaton;

repeating a process of reading into a memory one or more records positioned in a same order position from the set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition;

obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached an end state of the deterministic finite automaton when the end state is registered in the state transition set as a transition destination; and

outputting the obtained combination of records as a search result.

6. The recording medium according to claim 5, wherein the program further enables the computer to perform:

extracting a restriction among events other than the order relation from the search pattern query; and

checking whether or not the record enabling the possible state transition satisfies the restriction.

7. The recording medium according to claim 5, wherein the search pattern query is a search pattern query including a repetition of an event which does not continuously occur.

8. The recording medium according to claim 5, wherein said outputting outputs detected combination of records every time a combination of records corresponding to the search pattern query is detected.

9. The recording medium according to claim 5, wherein said obtaining performs pattern matching using one of processes of longest match which returns a combination of records with a longest interval of events among combinations of records matching the search pattern query, of shortest match which returns a combination of records with a shortest interval of events among combinations of records matching the search pattern query, of first match which returns a first combination of records matching the search pattern query, and of all match which returns all combinations of records matching the search pattern query.

10. The recording medium according to claim 5, wherein said outputting compiles information about the combination of records corresponding to the search pattern query in a designated format and outputs the compiled information.

11. The recording medium according to claim 5, wherein the program further enables the computer to perform an aggregating function for the combination of records corresponding to the search pattern query and outputting a result of the aggregating function.

12. The recording medium according to claim 5, wherein said repeating sorts the set of records by values of a designated attribute, and searches a sorted set of records.

13. The recording medium according to claim 12, wherein said repeating groups the set of records by values of a designated attribute, and sorts records of each group.