Search apparatus and method using order pattern including repeating pattern
First Claim
1. A search method of searching for a combination of records from a set of records consisting of a plurality of attributes, comprisingextracting 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13)
-
Specification