Optimization: find paths in SQL with recursive common table expressions about wn HOT 5 OPEN

from wn.

from wn.

Thanks! I'm concerned how it would scale when we consider more than just hypernym relations, but it's worth considering.

from wn.

Some updates to this:

Here is a query that recursively finds relations within the same lexicon:

WITH RECURSIVE
  rt(rowid) AS
    (SELECT rowid FROM relation_types WHERE type IN (?,...)), -- hypernym, instance_hypernym, etc.
  tgt(rowid, path, depth) AS
    (SELECT ?, ">"||?||",", 0 -- synset rowid, twice
     UNION ALL
       SELECT rels.target_rowid,
              tgt.path||rels.rowid||">"||rels.target_rowid||",",
              tgt.depth+1
         FROM synset_relations AS rels
         JOIN tgt ON rels.source_rowid = tgt.rowid
        WHERE rels.lexicon_rowid IN (?,...) -- target lexicons
          AND rels.type_rowid IN rt
          AND tgt.depth < ? -- depth limit
          AND NOT instr(tgt.path, ">"||rels.target_rowid||",")
        ORDER BY 3 DESC
        LIMIT 1000000
    )
SELECT rowid, path, depth FROM tgt;

Despite the string operations for avoiding cycles (see https://stackoverflow.com/q/66866542/1441112), it is fairly fast. And not only does it return all transitive relations, but also the path to get there and the depth, and the search can be limited by depth. However, it can easily become slow by broadening the query to, e.g., all relations, or even just hypernym and hyponym. For this reason, the (row) LIMIT is important and also an appropriate depth limit.

More importantly, it does not do expanded (inter-lexicon) search. I tried to replicate the two-step process currently used (first intra-lexicon relations, then expanded ones) by adding this second recursive part:

     UNION ALL
       SELECT ss.rowid, tgt2.path||exp.rowid||">"||ss.rowid||",", tgt2.depth+1
         FROM tgt AS tgt2
         JOIN synsets AS ss1 ON tgt2.rowid = ss1.rowid
         JOIN synsets AS ss2 ON ss2.ili_rowid = ss1.ili_rowid
         JOIN synset_relations AS exp ON exp.source_rowid = ss2.rowid
         JOIN synsets AS ss3 ON ss3.rowid = exp.target_rowid
         JOIN synsets AS ss ON ss.ili_rowid = ss3.ili_rowid
        WHERE exp.lexicon_rowid IN (?,...)  -- expand lexicons
          AND exp.type_rowid IN rt
          AND tgt2.depth < ? -- depth limit, again
          AND NOT instr(tgt2.path, ">"||ss.rowid||",")
          AND ss.lexicon_rowid IN (?,...)  -- target lexicons, again
        ORDER BY 3 DESC
        LIMIT 1000000

But recursive queries with more than one recursive part were not added to SQLite until version 3.34, and Python's version is at 3.31, so I'm not sure if the above even works. When I try something like the above as the only recursive query, it works but is very slow. I suspect that joining synsets 4 times at every recursive step is slowing things down. These 4 are necessary because we start with a synset rowid and relations are between synset rowids, but the expansion happens in ILI, so:

1. Join to get ILI of source synset
2. Join to get other synsets with that ILI
3. Join to get ILIs of matching relations' target synsets
4. Join to get synsets in target lexicon with those ILIs

This could perhaps be simpler if ILIs were required by all synsets. As it is, imagine if the PWN did not have ILIs: the relations still work between its synsets. Since they are optional we have to check, at every relation traversal, if there are relations within the current lexicon as well as the expanded ones available via ILI traversals.

from wn.

Changing the label to "maintenance" as this doesn't change functionality, only (potentially) performance.

from wn.