Provided is a criteria generation device and the like that al low high-speed that achieves high-speed search even if a database contains unsearchable information. The criteria generation device reads, from a memory, target search criteria including first search criteria and second search criteria representing criteria for retrieving information from a database; calculates, regarding the read target search criteria, truth values indicating whether or not search criteria being a subset of the first search criteria are satisfied; sets the calculated truth values for the subset of the search criteria; and generates third search criteria depending on whether the second search criteria are true or false in accordance with whether or not the target search criteria for which the truth values are set are satisfied.