Interesting question.

In PostgreSQL there are some text tools that may already be adequate for such a database:

The built-in full-text search (includes indexing, parsing, stemming, ranking). [1]

The extension pg_trgm (trigrams). Can be used to index, provides similarity functions. [2]

The extension fuzzystrmatch (with soundex, levenshtein etc.). [3]

[1] http://www.postgresql.org/docs/current/static/textsearch.html

[2] http://www.postgresql.org/docs/current/static/pgtrgm.html

[3] http://www.postgresql.org/docs/current/static/fuzzystrmatch.html