Search apparatus and method using order pattern including repeating pattern

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.

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.

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.

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.