There and back again

生も死もひとつのブランコの分岐点においてゆらゆらそのゆれをほほえんで見ているしかないのですね。

グラフデータベースの入門例：TeX LiveとNeo4j

by · Published · Updated

Neo4jは、成熟した堅牢なデータベースの特徴をすべて備えたハイパフォーマンスなグラフエンジンです。以前も紹介しましたが（①、②、③）、グラフ技術的に難しかったので、今回はどうやってある情報をグラフに表示するかを簡単な例で紹介したいと思います。

日本Neo4jユーザーグループのためのプレゼンテーションでは、私はTeX Live Databaseをグラフデータベースに表示し、あらゆる種類のパッケージとファイルとそれぞれのパッケージ間の依存関係をノードとエッジ（辺）として表現しました。

TeX Live Databaseのtlpdbをどのようにグラフ化したかについて詳細に説明する前に、TeX Liveではどのようにパッケージを管理し、整理するかについていくつかの概念を思い出してみましょう。TeX Liveの各パッケージには、カテゴリーがあります。現在利用可能なカテゴリはPackage, ConTeXt, Collection, Scheme, TLCoreです。それらは下記4つのグループに分類することができます：

  • 基本的なマクロパッケージ TeX Liveの本体です。アップストリームの作者が実際に作っているものです。 一般にLaTeXやフォントパッケージの場合は、カテゴリPackageかConTeXtのいずれかです。
  • バイナリのパッケージ binディレクトリにインストールされ、実行可能なファイルを意味する”バイナリ”ファイルです。これらは実際にはスクリプトであり、バイナリであり、様々な形です。
  • Collection 基本パッケージとバイナリパッケージが含まれており、他のコレクションに依存する場合があります。コレクションの集合が利用可能なファイルのパーティションであることを保証します。Debianなどのディストリビューターは、異なるパッケージに同じファイルが含まれないようにします。
  • スキーマ インストール時にユーザーに提示されるトップレベルのグループです。それらはコレクションや他のパッケージに依存し、意味のある選択肢を提供しようとします。

TeX Live Database自体は、Debianパッケージデータベースの後にモデル化され、各パッケージのスタンザ（段落）を含みます。 パッケージの典型的な例は、（やや簡略化しますが）次のとおりです：

category Package
revision 15878
catalogue one2many
shortdesc Generalising mathematical index sets
longdesc In the discrete branches of mathematics and the computer
...
longdesc one-line change.
docfiles size=98
 texmf-dist/doc/latex/12many/12many.pdf details="Package documentation"
 texmf-dist/doc/latex/12many/README details="Readme"
srcfiles size=6
 texmf-dist/source/latex/12many/12many.dtx
 texmf-dist/source/latex/12many/12many.ins
runfiles size=1
 texmf-dist/tex/latex/12many/12many.sty
catalogue-ctan /macros/latex/contrib/12many
catalogue-date 2016-06-24 19:18:15 +0200
catalogue-license lppl
catalogue-topics maths
catalogue-version 0.3
...

Collectionの典型的な例は次のとおりです：

name collection-langjapanese
category Collection
revision 48752
shortdesc Japanese
longdesc Support for Japanese; additional packages in
longdesc collection-langcjk.
depend collection-langcjk
depend ascmac
depend babel-japanese
...

Schemeの典型的な例は次のようになります：

name scheme-medium
category Scheme
revision 44177
shortdesc medium scheme (small + more packages and languages)
longdesc This is the medium TeX Live collection: it contains plain TeX,
longdesc LaTeX, many recommended packages, and support for most European
longdesc languages.
depend collection-basic
depend collection-binextra
depend collection-context
depend collection-fontsrecommendedRepresentation as graph was relatively straight-forward: We decided for separate nodes for each package and each file, and relations of dependency (depend in the above examples), inclusion (files being included in a package), and containment (a package is contained in a certain tlpdb revision).
...

合計で、9スキーマ、41コレクション、6,718パッケージ（Package, TLCore, ConTeXt）、および約181,839ファイルあります。

Neo4jでの表現

グラフは比較的単純明快な構造で、各パッケージと各ファイルに別々の種類のノードで表現しています。エッジ（辺、関係）はdepends（依存関係）、includes（ファイルはパッケージに含まれている関係）、包含（パッケージはあるtlpdbに含まれてる関係）です。

TeX Liveが提供するPerlモジュールを使用してTeX Live Databaseを読み込んで解析し、各ノードタイプと各リレーションタイプのCSVファイルを生成する単純なPerlスクリプトtl-dump-neo4jを使用しました。 これらのCSVファイルは、 neo4j-import使用してNeo4jデータベースにインポートされました。 3つのフィールド（名前とリビジョンを:で区切ったUUID、パッケージの名前とリビジョン）各ノードタイプに対して、1つのcsvファイルが生成されました。 Packagesを含むファイルnode-Package.csv例：

uuid:ID,name,revision
cslatex:47536,cslatex,47536
mcf2graph:48046,mcf2graph,48046
substances:40989,substances,40989
layouts:42428,layouts,42428
guide-to-latex:45712,guide-to-latex,45712

データベースに含まれるファイルについては、ファイル名を識別子として使用します。したがって、それぞれのCSVには1つのフィールド、ファイル名（空白が間違っていないことを確認するために引用符で囲みます）のみが含まれています。

使用されているtlpdbの、現在のバージョンを運ぶ識別子revisionのみのノードタイプTLPDBがあります。

3つの関係（depends, contains, includes）は、割り当てられたUUIDを使用して関係を定義しました。パッケージの場合は、ファイル名のname:revisionです。 edge-depends.csvの開始点を以下に示します。

:START_ID,:END_ID
cslatex:47536,csplain:48563
cslatex:47536,latex:47860
cslatex:47536,cm:45811
cslatex:47536,tex-ini-files:40533
cslatex:47536,latex-fonts:28888
cslatex:47536,hyphen-base:48303

includes関係の場合にのみ、ファイルの種類（ファイルがtlpdbにあるグループに従ってrun/bin/doc/src）を与える追加のタグを追加しました。 edge-includes.csvの開始点を以下に示します。

:START_ID,type,:END_ID
libertinus-type1:48618,run,"texmf-dist/fonts/tfm/public/libertinus-type1/LibertinusSans-tosf-sc-ly1.tfm"
sourcesanspro:42852,run,"texmf-dist/fonts/tfm/adobe/sourcesanspro/SourceSansPro-ExtraLight-tlf-sc-ly1.tfm"
cbfonts:31624,run,"texmf-dist/fonts/tfm/public/cbfonts/grxc0700.tfm"
clearsans:34405,doc,"texmf-dist/doc/fonts/clearsans/clear-samples.pdf"
fonts-tlwg:47499,run,"texmf-dist/fonts/tfm/public/fonts-tlwg/rkinnari_o.tfm"

最後の関係はcontainsで、tlpdbリビジョンと含まれているパッケージ間の接続を設定します。 edge-contains.csvの開始点を以下に示します。

:START_ID,:END_ID
48864,ltxmisc:21927
48864,tex4ebook:47672
48864,tamefloats:27345
48864,matc3mem:35773
48864,todo:17746

これにより、 neo4j-importへの簡単な呼び出しができ、すぐに使えるNeo4jデータベースが作成されました。

$ ls
edge-contains.csv    node-ConTeXt.csv  node-TLCore.csv
edge-depends.csv     node-Files.csv    node-TLPDB.csv
edge-includes.csv    node-Package.csv
node-Collection.csv  node-Scheme.csv
$ neo4j-import --into ../graphdb \
   --nodes:TLPDB node-TLPDB.csv \
   --nodes:Collection node-Collection.csv \
   --nodes:ConTeXt node-ConTeXt.csv \
   --nodes:Files node-Files.csv \
   --nodes:Package node-Package.csv \
   --nodes:Scheme node-Scheme.csv \
   --nodes:TLCore node-TLCore.csv \
   --relationships:contains edge-contains.csv \
   --relationships:includes edge-includes.csv \
   --relationships:depends edge-depends.csv
...
IMPORT DONE in 2s 93ms. 
Imported:
  168129 nodes
  172280 relationships
  175107 properties
Peak memory usage: 1.03 GB

サンプル・クエリ

SQLに似てるCypherというグラフクエリ言語を使います。Cypherでは、グラフに入っているデータを検索できますが、Cypherの入門はここやここを参考してください。

①すべてのスキーマを返します。

match (s:Scheme) return s;

②スキーマのすべての依存関係を、別のものに戻してからコレクションに戻します。

match p = (s:Scheme) -[:depends]-> (q)
  where NOT 'Collection' IN LABELS(q)
  return p;

ここでは、LABELSを使用してノードのすべてのラベルを検索します。

③同じパッケージが2つの異なるコレクションに含まれているかどうかを確認します：

match (c1:Collection) -[:depends]-> (p)
  <-[:depends]- (c2:Collection) return c1, c2, p;

幸いなことに、コレクションだけが複数の依存のターゲットになります。

④依存関係のサイクルを検索する：

match p = (n)-[:depends*]-> (n) return p;

ここでは、 *演算子を使用して任意の長いパスを検索します。 驚いたことに、ConTeXtがそれ自身に依存するという結果となりました。

⑤複数のパッケージに含まれるファイルを検索する：

match (p1) -[:includes]-> (f)
  <- [:includes]- (p2) return p1, p2, f;

幸いにも、ここでは同様の結果にはなりませんでした。 これは毎回、単純なgrep/awkプログラムでチェックされます。

⑥1つのパッケージのすべてのドキュメントファイルを表示する：

match (p) -[:includes {type:'doc'}]-> (f)
  where p.name = "tlcockpit"
  return p,f;

Neo4jによるグラフアルゴリズム

Neo4jチームは、グラフ・アルゴリズムのライブラリーをプラグインとして提供しています。このプラグインには色々なグラフ関係の関数が含まれています。プラグインはNeo4j Githubページからダウンロード（現在にはgraph-algorithms-algo-3.4.7.0.jar）して、Neo4jインストールのpluginsフォルダに入れることでインストールことができます。Debianでは/var/lib/neo4j/plugins/です。 実際に実行させるには、Neo4j設定ファイル（Debian /etc/neo4j/neo4j.conf）に次の行を追加して実行する必要があります。

dbms.security.procedures.unrestricted=algo.*

Neo4jを再起動すると、このjarで提供されているすべてのアルゴリズムを使用する準備が整います。

まず、 Googleのページランクを確認しましょう。

CALL algo.pageRank.stream(null, 'depends', {iterations:20, dampingFactor:0.85})
  YIELD nodeId, score
  MATCH (node) WHERE id(node) = nodeId
  RETURN node.name AS page,score
  ORDER BY score DESC

次の出力が得られます（テーブルモード）:

╒══════════════════════════════╤═══════════════════╕
│"page"                        │"score"            │
╞══════════════════════════════╪═══════════════════╡
│"context"                     │4.868265000000001  │
├──────────────────────────────┼───────────────────┤
│"hyphen-base"                 │4.667172000000001  │
├──────────────────────────────┼───────────────────┤
│"hyph-utf8"                   │4.0754105          │
├──────────────────────────────┼───────────────────┤
│"kpathsea"                    │1.8529665          │
├──────────────────────────────┼───────────────────┤
│"plain"                       │0.982524           │
├──────────────────────────────┼───────────────────┤

同様のものでは、Betweenness Centralityがあります：

CALL algo.betweenness.stream(null, 'depends', {direction:'out'})
  YIELD nodeId, centrality
  MATCH (pkg) WHERE id(pkg) = nodeId
  RETURN pkg.name AS pkg,centrality
  ORDER BY centrality DESC;

次の出力が得られます:

╒══════════════════════════╤═══════════════════╕
│"pkg"                     │"centrality"       │
╞══════════════════════════╪═══════════════════╡
│"collection-basic"        │1675.4717032967033 │
├──────────────────────────┼───────────────────┤
│"collection-latexextra"   │1212.0             │
├──────────────────────────┼───────────────────┤
│"context"                 │947.3333333333334  │
├──────────────────────────┼───────────────────┤
│"collection-latex"        │744.8166666666666  │
├──────────────────────────┼───────────────────┤
│"collection-pictures"     │586.0              │
├──────────────────────────┼───────────────────┤

最後に三角計算を見てみましょう：

CALL algo.triangleCount.stream(null, 'depends', {concurrency:4})
  YIELD nodeId, triangles, coefficient
  MATCH (p) WHERE id(p) = nodeId
  RETURN p.name AS name, triangles, coefficient
  ORDER BY triangles DESC

次の出力が得られます:

╒═════════════════════════╤═══════════╤═══════════════════════╕
│"name"                   │"triangles"│"coefficient"          │
╞═════════════════════════╪═══════════╪═══════════════════════╡
│"collection-basic"       │109        │0.042644757433489826   │
├─────────────────────────┼───────────┼───────────────────────┤
│"scheme-full"            │46         │0.05897435897435897    │
├─────────────────────────┼───────────┼───────────────────────┤
│"collection-latex"       │43         │0.04154589371980676    │
├─────────────────────────┼───────────┼───────────────────────┤
│"scheme-tetex"           │42         │0.022950819672131147   │
├─────────────────────────┼───────────┼───────────────────────┤
│"collection-context"     │39         │0.04318936877076412    │
├─────────────────────────┼───────────┼───────────────────────┤

今後の仕事

パッケージの完全な情報（リビジョン番号、カタログ情報など）をさらに解析し、ノードに保存し、定期的にデータベースを更新してパッケージの展開を確認することは興味深いでしょう。

閉鎖

上記すべてと、実際のプレゼンテーションのスライドが1日以内で書かれていることを考慮すると、Neo4jに基づいてグラフデータベースを開発し、それを使って行っていることは、ほんの些細な手順であることがわかります。 難しい部分は、ノードタイプとリレーションタイプの「正しい」セットとその属性を見つけることです。 TeX Liveデータベースの場合、それはかなり簡単で、Neo4jで簡単で直接的な表現が可能でした。

http://texlive.info:7474/browser/（user/pass: neo4j）では、作成されたグラフで遊ぶことができます。（読み取り専用です。）

グラフのこのような簡単な例が、グラフの力を使ってより興味深いプロジェクトが開始されるのに役立つことを願っています。

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *