Example implementations relate to database records associated with a trie. For example, a computing device may include at least one processor to receive a query string and determine, based on the query string, a lookup string associated with a plurality of words in an order. The at least one processor may identify, based on the lookup string and a trie associated with the lookup string, a set of records from a database of records, each record in the set being associated with a score that is associated with a degree to which each record matches the query string, wherein the set is identified based on a penalty value calculated for each record based on a hypothesized collection of typing errors sufficient to transform a prefix of a string associated with each record into the lookup string. The at least one processor may provide a result based on the set.