Norbert Preining氏による【グラフデータベースの入門例:TeX Live データベースからNeo4jグラフデータベースへ】を公開

アクセリア株式会社の研究開発部社員であるNorbert Preining氏による、コラム連載を開始しました。 https://www.accelia.net/column/research/

アクセリア株式会社 2018年10月19日

第17回:グラフデータベースの入門例:TeX Live データベースからNeo4jグラフデータベースへ

「TeX Liveではどのようにパッケージを管理し、整理するか」
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が提供するデータをNeo4Jに取り込むために、次の方法をとりました。

tl-dump-neo4jを用いて TeX Live Databaseを解析し、各ノードタイプと各リレーションタイプのCSVファイルを生成し、neo4j-importを用いて CSVファイルをNeo4jデータベースにインポートします。

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ファイルの先頭は次の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;

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

④依存関係のサイクルを検索する:
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;


・・・ここから先は、アクセリア株式会社で公開中のコラム本編でご覧ください。
本編では、挿絵を交えて詳しく説明しています。
(リンク »)


【アクセリア株式会社の研究開発部社員:Norbert Preining氏のコラム】
・第1回:今さら聞けない、機械学習/ディープラーニングとは!? (リンク »)
・第2回:最新の機械学習の代表、ニューラルネットワークとは (リンク »)
・第3回:手書き数字を認識する機械学習 (リンク »)
・第4回:畳み込みニューラルネットワーク (リンク »)
・第5回:機械学習における今後の展開 (リンク »)
・第9回:Analyzing Debian packages with Neo4j (リンク »)
・第10回:Analyzing Debian packages with Neo4j - Part 2 UDD and Graph DB Schema (リンク »)
・第11回:Analyzing Debian packages with Neo4j - Part 3 Getting data from UDD into Neo4j (リンク »)
・第12回:Specification and Verification of Software with CafeOBJ - Part 1 - Introducing CafeOBJ (リンク »)
・第13回:Specification and Verification of Software with CafeOBJ - Part 2 - Basics of CafeOBJ (リンク »)
・第14回:Specification and Verification of Software with CafeOBJ - Part 3 - First steps with CafeOBJ (リンク »)
・第15回:Specification and Verification of Software with CafeOBJ - Part 4 - Modules (リンク »)
・第16回:DebConf 2018 in 新竹 レポート (リンク »)

【アクセリア株式会社の研究開発部社員のコラム】
・第6回:アクセリアが手がけるP2P (Peer-to-Peer) (リンク »)
・第7回:効率的な検索を可能にする、グラフデータベース (リンク »)
・第8回:アクセリアにおけるディープラーニング適用例 (リンク »)

関連情報へのリンク »

本プレスリリースは発表元企業よりご投稿いただいた情報を掲載しております。
お問い合わせにつきましては発表元企業までお願いいたします。

アクセリア株式会社の関連情報

アクセリア株式会社

アクセリア株式会社の記事一覧へ

【企業の皆様へ】企業情報を掲載・登録するには?

御社の企業情報・プレスリリース・イベント情報・製品情報などを登録するには、企業情報センターサービスへのお申し込みをいただく必要がございます。詳しくは以下のページをご覧ください。

SpecialPR

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]