On Monday, July 8, 2013, Robert James wrote: > On 7/8/13, hubert depesz lubaczewski <dep...@depesz.com <javascript:;>> > wrote: > > On Mon, Jul 08, 2013 at 09:09:26AM -0400, Robert James wrote: > >> I have two relations, where each relation has two fields, one > >> indicating a name and one indicating a position. That is, each > >> relation defines a sequence. > >> > >> I need to determine their longest common subsequence. Yes, I can do > >> this by fetching all the data into Java (or any other language) and > >> computing it using the standard LCS dynamic programming language. But > >> I'd like to stay within Postgres. Is there any way to do this? > > > > I'm not entirely sure I understand. Can you show us some sample data and > > expected output? > > Sure. Borrowing a good example from > http://wordaligned.org/articles/longest-common-subsequence : > > Table A (val varchar primary key, pos integer): > 1, "C" > 2, "H" > 3, "I" > 4, "M" > 5, "P" > 6, "A" > 7, "N" > 8, "Z" > 9, "E" > 10, "E" > > Table B (val varchar primary key, pos integer): > 1, "H" > 2, "U" > 3, "M" > 4, "A" > 5, "N" > > SELECT LongestCommonSubsequence(A,B): > 1, "H" > 2, "M" > 3, "A" > 4, "N" > > (Common chars are in upper case: > cHiMpANzee > HuMAN > ) > > The std dynamic programming algorithm is described at > http://en.wikipedia.org/wiki/Longest_common_subsequence_problem > > > -- > Sent via pgsql-general mailing list > (pgsql-general@postgresql.org<javascript:;> > ) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-general >
To me it looks like: Selecte distinct val from tablea join tableb using (val)
