{"id":891,"date":"2014-01-10T15:36:36","date_gmt":"2014-01-10T20:36:36","guid":{"rendered":"http:\/\/www.phishie.com\/wordpress\/?p=891"},"modified":"2014-01-10T15:36:38","modified_gmt":"2014-01-10T20:36:38","slug":"5-degrees-of-pokemon-bacon","status":"publish","type":"post","link":"https:\/\/www.phishie.com\/wordpress\/2014\/01\/5-degrees-of-pokemon-bacon\/","title":{"rendered":"5 Degrees of Pok\u00c3\u00a9mon Bacon"},"content":{"rendered":"

One of the side projects I work on outside of my job<\/a> is a Japanese anime site called AniDB<\/a>. It was put together by some German guys quite some time ago with Perl, PostgreSQL<\/a>, and some old donated hardware\/bandwidth from an ISP. They were kind\/foolish enough to let me help out with the site about two years ago. Anidb has almost anything you could possibly need to know about Japanese anime series (much like imdb<\/a> for movies). Including things like what characters know each other between the different series.<\/p>\n

\"satoshi\"<\/a>AniDB’s data is populated by its users. \u00c2\u00a0Unfortunately, not all of them are as careful as others about providing complete entries for the character data they add. \u00c2\u00a0Many of the minor characters get entered but never linked to the rest of the story. \u00c2\u00a0We needed to find these missing\/orphaned characters so they can be investigated and cleaned up by the AniDB staff.\u00c2\u00a0\u00c2\u00a0The question we were trying to answer was, “out of any character in any Pok\u00c3\u00a9mon series, who doesn’t have some sort of relationship to Ash\/Satoshi <\/a>(the main character)?” It’s almost impossible to not SOMEHOW be related to the main character. \u00c2\u00a0 Because of how the reporting system is setup, we also wanted this to be a single query so we could just throw it in a report. \u00c2\u00a0AniDB’s tables are setup a little weird. This is in part due to necessary design and in part due to historical reasons that stem from organic growth. \u00c2\u00a0This design is part of the complexity of the problem.<\/p>\n

For the first part of our report, we wanted to get a list of EVERY character in any type of Pokemon anime. To do that, the tables we have are:<\/p>\n

animetb -- The Anime Table\r\n-------\r\nid -- Primary Key for the anime\r\n...\r\n\r\nseqtb -- The Sequel Table\r\n-----\r\naid -- Foreign Key to animetb. The subject anime.\r\nnext -- Foreign Key to animetb. The object anime (sequel)\r\ntype -- What kind of relation. Sequel, side-story, OVA, etc.<\/pre>\n
So to start with, we had\u00c2\u00a0the original Pokemon anime<\/a> that started it all in 1997. \u00c2\u00a0This is anime id 230<\/code> in our system. \u00c2\u00a0We need to traverse the tree structure of anime relations to get a list of every anime related to the original Pokemon. \u00c2\u00a0This in itself can be quite complicated. \u00c2\u00a0Here’s a graph of how all these anime are related<\/a>. \u00c2\u00a0To do this I needed a great feature of PostgreSQL called Recursive Common Table Expressions<\/a>\u00c2\u00a0(CTEs). \u00c2\u00a0To explain how these work, lets go through the (slightly modified) example in the PostgresSQL docs.<\/p>\n
WITH RECURSIVE temp(n) AS (\r\n  VALUES (1)\r\n  UNION ALL\r\n  SELECT n+1 FROM temp WHERE n < 10\r\n)\r\nSELECT sum(n) FROM temp;<\/pre>\n
The way this works is, we create a named recursive CTE called “temp”. \u00c2\u00a0Recursive CTEs contain several parts. \u00c2\u00a0The non-recursive term: VALUES(1)<\/span>,\u00c2\u00a0which unsurprisingly just returns the result set of “1”. \u00c2\u00a0 This is following by a UNION<\/span> or UNION ALL<\/span> connection. \u00c2\u00a0Then the fun part. The recursive part:<\/p>\n
SELECT n+1 FROM temp WHERE n < 10<\/pre>\n
When Postgres runs this query, it will see the recursive CTE and evaluate the first part, which returns the single value 1. \u00c2\u00a0It then takes this result set as the content of the “temp” table and will then run the second recursive part with this result set. \u00c2\u00a0 Since we’re just selecting N+1, the result, in this case, will be “2”. \u00c2\u00a0Since this iteration created new values to add to “temp”, it will incrementally keep going and get “3” then “4” and so forth until the query returns nothing, at which point it will end. \u00c2\u00a0The final result of the recursive CTE is a “temp” table with 10 rows in it. \u00c2\u00a0Values \u00c2\u00a0“1” through “10.” \u00c2\u00a0 We can then query “temp”, in our final query, to sum() it and get our grand total of “55.”<\/p>\n
We’re going to use the same strategy with anime. \u00c2\u00a0We’re returning our hardcoded first Pokemon anime (id 230<\/code>) as the starting value, and then \u00c2\u00a0start pulling the relations with this query:<\/p>\n
WITH RECURSIVE pokemon_animes(animeid) AS (\r\n  VALUES( 230 )\r\n  UNION\r\n  SELECT s.next FROM seqtb s, pokemon_animes p WHERE p.animeid = s.aid\r\n)\r\nSELECT animeid FROM pokemon_animes ORDER BY animeid;<\/pre>\n
Our first iteration will return 230<\/code>, which we will run the recursive query with returning our second set :<\/p>\n
921 | Pocket Monsters: Mizu no Miyako no Mamorigami Latias to Latios<\/a>\r\n990 | Gekijouban Pocket Monsters: Mewtwo no Gyakushuu<\/a>\r\n991 | Pocket Monsters: Celebi Toki o Koeta Deai<\/a>\r\n992 | Pocket Monsters: Kesshoutou no Teiou<\/a>\r\n1020 | Pocket Monsters: Maboroshi no Pokemon Lugia Bakutan<\/a>\r\n1041 | Pocket Monsters Advanced Generation<\/a>\r\n3491 | Pocket Monsters: Pikachu no Fuyuyasumi (1999)<\/a>\r\n3492 | Pocket Monsters: Pikachu no Fuyuyasumi (2000)<\/a>\r\n3493 | Pocket Monsters: Pikachu no Fuyuyasumi (2001)<\/a>\r\n7117 | Pocket Monsters Crystal: Raikou Ikazuchi no Densetsu<\/a><\/pre>\n
Our recursive query will then get run again with the above set of ids returning another, third set, and so on until we have no more results. \u00c2\u00a0This gives us a list of all the Pokemon anime that we can use to get all of the character ids. \u00c2\u00a0To pull these character ids will require use of another table from AniDB.<\/p>\n
chartb -- The Character Table\r\nid : Primary Key for the character\r\nparentid : The 'guise' for the character.\r\n\u00e2\u20ac\u00a6<\/pre>\n
By using our list of anime ids and AniDB’s “charanimereltb” link table, we can get a listing \u00c2\u00a0of all characters in any Pokemon anime with:<\/p>\n
WITH RECURSIVE pokemon_animes(animeid) AS (\r\n  VALUES( 230 )\r\n  UNION\r\n  SELECT s.next FROM seqtb s, pokemon_animes p WHERE p.animeid = s.aid\r\n)\r\nSELECT c.charid FROM charanimereltb c, pokemon_animes a WHERE c.aid = a.animeid;<\/pre>\n
That gets us halfway there! \u00c2\u00a0Now we just need all the characters related to Satoshi to compare the set to. \u00c2\u00a0The parentid\/guise from the table above was the first type of relationship tracked in AniDB. \u00c2\u00a0The guise is used to associate alternate forms of a character. \u00c2\u00a0Because this relationship is chronological in story lines, it can usually be represented this way without any problems. \u00c2\u00a0As time passed, a real relations table had been added. \u00c2\u00a0However, since guises were already in the chartb, these were never moved because of the number of changes that would be required to do so. \u00c2\u00a0Technical debt is incurred, but usually we can work around that. \u00c2\u00a0However, eventually this system was further abused by some of the data entry people. \u00c2\u00a0 \u00c2\u00a0The ‘wild’ version of a Pokemon was created and guises were created for more specific versions of the individual trainer’s instances of these fur balls. \u00c2\u00a0This brings us to where we are now.<\/span><\/p>\n
charcharreltb -- The Character to Character Relation Table\r\ncharid : The subject of the relation. FK to chartb\r\nnext : The object of the relation. Also a FK to chartb.\r\ntype : How they are related, friend\/enemy\/etc\r\n...<\/pre>\n
\"fushi\"<\/a>This setup causes some fun problems. In this case, to really find out everyone who is related to a character, you not only want all of the relationships about that instance of the character, but any other versions\/guises of the character as well (or any other versions\/guises of the relations you are related to.)<\/p>\n
For example (and this will get geeky),\u00c2\u00a0Satoshi<\/a> and Fushigidane<\/a> are related to each other as Fushigidane (Japanese for Bulbasaur), which is Satoshi’s personal trained Pok\u00c3\u00a9mon. Fushigidane is a type\/guise of Bulbasaur<\/a>. Bulbasaurs can evolve into any Ivysaur<\/a>. Thus all 3 forms in the system are “related” to Satoshi.<\/p>\n
6693 <-related-> 22350 -guise-> 18 -relation-> 20<\/b><\/p>\n
Or for even crazier example. \u00c2\u00a0A Clefairy\/Pippi<\/a> is a type of Pokemon. These are a guise of a particular Clefairy<\/a> (id 23859) that was trained\/owned by Akai Isamu<\/a>(id 23857). Akai also has another personal trained Pokemon<\/a> (id 23858) that is a Pikachu type<\/a>\/guise (id 69). That, of course, is also a guise to the Pikachu<\/a> (id 8091) that everyone knows and loves belonging to Satoshi<\/a> (6693). Therefore, all of these characters are related to Satoshi.<\/p>\n
169 <-guise_of- 23859 <-related-> 23857 <-related-> 23858 -guise_of-> 69 <-guise_of- 8091 <-related-> 6693<\/b><\/p>\n
This is a pretty nasty chain. And remember, we need to do it with a single query! \u00c2\u00a0One limitation of recursive queries is that you can only refer to the recursive table once and it may not be (unfortunately) in a subquery. \u00c2\u00a0 This provided a challenge, since we needed to return a single value, but I needed to pull from several different potential relations or guises! \u00c2\u00a0 I was finally able to work around this with two other great utilities that PostgreSQL offers -\u00c2\u00a0Arrays<\/a>\u00c2\u00a0and the unnest() function<\/a>,\u00c2\u00a0which will expand an array into a set of rows. \u00c2\u00a0It ended up looking something like this:<\/p>\n
\"pippi\"<\/a><\/p>\n
WITH RECURSIVE related_to_satoshi(charid) AS (\r\n  VALUES (6693)\r\n  UNION\r\n  SELECT unnest(ARRAY[c.next, n.charid, d.parentid, e.parentid, g.id])\r\n  FROM related_to_satoshi s\r\n    -- related to character\r\n    LEFT JOIN charcharreltb c ON (c.charid = s.charid)\r\n      -- get the character to get any guise of them\r\n      LEFT JOIN chartb d ON (c.charid = d.id)\r\n        -- get any reverse relations to the character\r\n        LEFT JOIN charcharreltb n ON (n.next = s.charid)\r\n      -- get that character to get any guise from them\r\n      LEFT JOIN chartb e ON (n.next = e.id)\r\n    -- get my guise so we can look it up next iteration too\r\n    LEFT JOIN chartb g ON (s.charid = g.parentid)\r\n)<\/pre>\n
Basically, we pull in everyone who was related, or a guise of the character, and then keep iterating over them. \u00c2\u00a0We throw them all into the array, and then unnest it for the final result set. \u00c2\u00a0 Because we UNION everything we remove any duplicate values and keep us from going into any possible loops (important!).<\/p>\n
Adding in a non-recursive CTE for clarity we can come to our final solution of:<\/p>\n
WITH RECURSIVE related_to_satoshi(charid) AS (\r\n  VALUES (6693)\r\n  UNION\r\n  SELECT unnest(ARRAY[c.next, n.charid, d.parentid, e.parentid, g.id])\r\n  FROM related_to_satoshi s\r\n    LEFT JOIN charcharreltb c ON (c.charid = s.charid)\r\n      LEFT JOIN chartb d ON (c.charid = d.id)\r\n    LEFT JOIN charcharreltb n ON (n.next = s.charid)\r\n      LEFT JOIN chartb e ON (n.next = e.id)\r\n    LEFT JOIN chartb g ON (s.charid = g.parentid)\r\n),\r\npokemon_animes(animeid) AS (\r\n  VALUES( 230 )\r\n  UNION\r\n  SELECT s.next FROM seqtb s, pokemon_animes p WHERE p.animeid = s.aid\r\n),\r\nall_characters AS (\r\n  SELECT DISTINCT c.charid FROM charanimereltb c, pokemon_animes a WHERE c.aid = a.animeid\r\n)\r\nSELECT DISTINCT a.charid as not_related\r\nFROM all_characters a\r\nLEFT JOIN related_to_satoshi r USING(charid)\r\nWHERE r.charid IS NULL\r\nORDER BY a.charid;<\/pre>\n
The editors were thrilled and this has started to become a new report for helping clean up the system! \u00c2\u00a0 Finally we could catch them all! \u00c2\u00a0 PostgreSQL was chosen as the database for AniDB because of its reliability and ability to do these tough reports. \u00c2\u00a0It’s not a decision we’ve ever regretted.<\/p>\n
\u00c2\u00a0“Meowth! That’s right!”<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
One of the side projects I work on outside of my job is a Japanese anime site called AniDB. It was put together by some German guys quite some time ago with Perl, PostgreSQL, and some old donated hardware\/bandwidth from an ISP. They were kind\/foolish enough to let me help out with the site about […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18,21,20],"tags":[],"class_list":["post-891","post","type-post","status-publish","format-standard","hentry","category-anime","category-postgresql","category-work"],"_links":{"self":[{"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/posts\/891","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/comments?post=891"}],"version-history":[{"count":35,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/posts\/891\/revisions"}],"predecessor-version":[{"id":930,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/posts\/891\/revisions\/930"}],"wp:attachment":[{"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/media?parent=891"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/categories?post=891"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.phishie.com\/wordpress\/wp-json\/wp\/v2\/tags?post=891"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}