日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

木分解の圧縮および解集合プログラ

点のラベル対のうち最頻出するものを非終端記号へ置換すること

ミングに基づく問合せ処理法の提案

文法に基づく多くの圧縮法の中で圧縮率や圧縮に要する時間の点を繰り返し, 直線的文脈自由木文法に変換する. TreeRePair は木で優れている. 更に直線的文脈自由木文法び対して解凍することと評価なく問合せや更新を行う手法について研究がなされている [16].
以下, 本論文では諸定義を行った後, 後続の圧縮効果が得やすい

小島 和之 1

分解木の表現形式 (3 節), 木文法を用いた圧縮法 (4 節) を提案す関 浩之 2る. 次に, 圧縮データへの (解凍を伴わない) 直接問合せ法を例を用いて説明する (5 節). 最後に分解木に対して (木圧縮を意識せず

グラフの木分解は, 大規模グラフデータの問合せに対して有効に) 動的計画法による問合せ処理の記述を支援する解集合プログ

なアプローチであるが, 木分解自体には大きな計算量を要する.

ラムの枠組みを提案する (6 節). 解集合プログラムは規則の集合

そこで本研究は木分解を再利用するために木文法に基づく圧縮手として記述された論理プログラムである. プログラムの解は任意法を提案する. 併せて問合せ処理について解凍することなく実行の規則を満たす原子命題の集合 (解集合) であり, 解集合の探索にする手法を提案する. 問合せ時に使用するアルゴリズムについて

はソルバを利用する. 解くべき問題の定義を規則の集合として与直接記述する方法と解集合プログラムを利用する方法を提供す

えると, そのままプログラムとして実行できるという利点がある.

る. 実験の結果, 十分な圧縮率が得られること, 問合せを直接記述

5 節と 6 節では実装システムを用いて提案手法を評価した結果をする方法においては解凍せずに問合せ処理を行う方法が従来法よ述べる. 2 つの問合せ手法をいくつかのベンチマークに対して実り計算効率がよいこと, 解集合プログラムを利用する方法では記行した結果, (1) 十分な圧縮効果が得られたこと, (2) 手作業で記述

述容易性・了解性が向上することがわかった.

した問合せについては直接問合せが多くの場合で効率よく実行できたこと, (3) 解集合プログラミングを用いることにより宣言的な

1

まえがき

問合せ記述ができ, 問合せプログラムの了解性が向上したが, 今回の実装では直接問合せの実行効率には改善の余地があることがわ

グラフ構造は科学データなど実世界の大規模データを表現する

かった.

ために用いられる. グラフに対する問題で効率のよいアルゴリズ

関連研究 グラフ圧縮には, [19] 等の文字列圧縮を応用した伝統的ムが知られていないものが多数ある. こうした問題の計算量を削な方法があるが, 近年, 簡潔データ構造を用いた圧縮 [6,7,13] や文減するために, 木分解と呼ばれる手法を用いて, 与えられたグラ法を用いた圧縮 [22] などのように, 圧縮データを解凍することな

フから木構造 (分解木とよぶ) を構成し, 分解木に対して動的計画

く近傍走査が行えるグラフ圧縮法が主流となっている. k2 -tree [7]法を用いて元のグラフに対する問題を解くというアプローチが知では, グラフを隣接行列で表し, その行列を適切な区間で区切っられている. ここで分解木の頂点は元のグラフの部分グラフに対たものを簡潔な表現に符号化することで圧縮を行なっており, 疎応しており, それらの部分グラフの頂点の最大数から 1 を引いたなグラフに対して効果的に圧縮できる. k2 -tree はその汎用性が高数をその分解木の幅とよぶ. 幅がある定数以下の分解木のクラス

く, 他の圧縮法の内部で使用されている [9, 17, 22]. 特に [17] でに対しては, ある種の NP 完全な問題をこのようなアプローチには, [8] を拡張したものと k2 -tree を組み合わせた手法が提案されよって元のグラフのサイズの多項式時間で解くことができる.

ており, Web グラフの圧縮では 0.9 ∼ 1.5bpe という高い圧縮率を一方, 木分解の計算にはグラフ全体の構造情報を必要とし計算示している. 他の手法として, 圧縮グラフに対する問合せをあら

コストが高い. また分解木に含まれる部分グラフには重複が多い

かじめ限定し, その問合せに不必要な情報を削ることで効果的にためデータサイズが元のグラフに比べ大きく, データの圧縮を行

圧縮を行う手法も存在する [12, 23, 24]. [14] では, 隣接リストをえることが望ましい. しかし, 分解木に対して単純な圧縮アルゴ用いて圧縮された Web グラフに対するページランクの効率的なリズムを適用した場合では構造情報が損なわれてしまう. そのた計算方法が示されているが, Web グラフのスパース性と局所性をめ分解木に対する問合せや更新時には一旦解凍してから処理を行利用しているため, 一般のグラフに対してはあまり効果的でない.

わなければならず非効率的である.

グラフ文法を用いた gRePair [22] では, 圧縮グラフ上で 2 頂点間

本研究では, 与えられたグラフの分解木に対して圧縮法を効の到達可能性を圧縮データサイズの線形時間オーダで判定できる

果的に適用可能な表現形式および, 圧縮された分解木に対してことを証明しているが, 実験的評価は行われていない. グラフ圧

解凍せずに直接的に問合せを行う方法として, 問合せアルゴリ

縮と直接問合せ法を概観するには [3, 21] を参照されたい.

ズムを直接記述する方法 [25] と解集合プログラムの形式で記述

木分解を利用して木幅が有界なグラフに対する問題を効率良する方法 [26] を提案する. この 2 つの記述法を用いて問合せをく解く手法を解集合プログラミングに導入した先駆的研究とし記述し評価実験を行った. 筆者らが圧縮法として利用しているて [18] がある. 問合せアルゴリズムを解集合プログラムによってTreeRePair [20] は, 入力として与えられた木において隣接する頂1 学生会員

記述することで多くのグラフ問題を扱っている. この研究に基づき, 木分解を前提とした解集合プログラミングを支援する統合環

名古屋大学 情報学研究科

境 D-FLAT が開発された [2, 4]. 6 節の研究方針および実装シスk.kojima@sqlab.jp
2 正会員

名古屋大学 情報学研究科

テムも, D-FLAT の設計方針を参考にしている. ただし, 本研究でseki@sqlab.jp

1

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

𝐿(𝐺𝑟) = {𝑡 | 𝑆 ⇒+𝐺𝑟 𝑡 かつ 𝑡 ∈ 𝑇 (Σ, ∅)} と定義する.

は分解木をさらに木文法に圧縮することを前提としており, ユー
ザが圧縮後のデータの細部に依存せずに解集合プログラミングを

直線的文脈自由木文法 (SLCFTG) は以下の条件を満たす CFTG

𝐺𝑟 = (𝑁, Σ, 𝑅, 𝑆) のことをいう.

行える点に特長がある.

2

定義

2.1

グラフ

(1) 各非終端記号 𝐴 ∈ 𝑁 について, ちょうど 1 つの生成規則
𝐴(𝑥1 , . . . , 𝑥 𝑛 ) → 𝑡 ∈ 𝑅 が存在し, かつ 𝑡 が線形である.
(2) 各非終端記号 𝐴 ∈ 𝑁 について, 𝐴(𝑥1 , . . . , 𝑥 𝑛 ) ⇒+𝐺𝑟 𝑠 である

無向グラフは 2 項組 𝐺 = (𝑉, 𝐸) である. ここで 𝑉 は頂点の有ならば, 𝑠 に 𝐴 が出現しない.

限集合, 𝐸 は辺すなわち頂点の非順序対 (𝑢, 𝑣) (𝑢, 𝑣 ∈ 𝑉) の有限𝐴(𝑥 1 , . . . , 𝑥 𝑛 ) → 𝑡 ∈ 𝑅 について, 𝑡 を 𝑡 𝐴 と書き, また 𝑡 𝐴 を 𝐴 の集合である. 以下では無向グラフを単にグラフとよぶ.
グラフ 𝐺 = (𝑉, 𝐸) における独立集合 𝐼 ⊆ 𝑉 とは任意の異な右辺とよぶ. 任意の SLCFTG 𝐺𝑟 について, 開始非終端記号 𝑆 かる頂点間に辺が存在しない頂点の部分集合である. つまり任意のらの導出 𝑆 ⇒+𝐺𝑟 𝑠 は (1) より決定的に行われ, (2) よりどの規則

𝑢, 𝑣 ∈ 𝐼 (𝑢 ≠ 𝑣) について (𝑢, 𝑣) ∉ 𝐸.

も再帰的に適用されないので, 𝐿 (𝐺𝑟) の要素数は 1 である.

グラフ 𝐺 = (𝑉, 𝐸) における 3 彩色とは写像 𝜎 : 𝑉 → 𝐶 (𝐶 =TreeRePair [20] は 入 力 と し て 与 え ら れ た 木 を 次 の 方 法 で{𝑟𝑒𝑑, 𝑏𝑙𝑢𝑒, 𝑔𝑟𝑒𝑒𝑛}) である. ただし任意の辺 (𝑢, 𝑣) ∈ 𝐸 について

SLCFTG に変換する圧縮法である. 頂点 𝑢 の 𝑖 番目の子頂点

𝜎(𝑢) ≠ 𝜎(𝑣).

を 𝑣 とする. 頂点 𝑢, 𝑣 のラベルをそれぞれ 𝑓 , ℎ としたとき, これ

木分解

らの頂点が構成するダイグラムを ( 𝑓 , 𝑖, ℎ) と表す. TreeRePair は

2.2

グラフ 𝐺 = (𝑉, 𝐸) に対して次の条件を満たす T を木分解によダイグラムのうち最頻出するものを非終端記号に置換することをり 𝐺 から得られた木または分解木とよぶ [11]. 分解木 T の各頂繰り返して木文法を構成する. ただし置換はその前後でサイズが点 𝑥 (以降, 𝑥 ∈ T と表記する) には 𝐺 の部分グラフ 𝐵 𝑥 = (𝑉𝑥 , 𝐸 𝑥 )減少する場合のみ行う. このようにして木から SLCFTG を構成が割当てられる. これを 𝑥 のバッグとよぶ. バッグは以下の条件

することを圧縮という. 逆に SLCFTG 𝐺𝑟 から 𝑡 ∈ 𝐿 (𝐺 𝑟 ) であるを満たさなければならない:

木 𝑡 を求めることを解凍という.
2.4• ∪ 𝑥 ∈T 𝑉𝑥 = 𝑉.
• 𝐺 の全ての辺 (𝑢, 𝑣) ∈ 𝐸 について (𝑢, 𝑣) ∈ 𝐸 𝑥 となる 𝑥 ∈ T

𝐴𝑡 上 の 解

集合プログラム Π とは次の形式の規則 𝑟 の有限集合であが存在する.

る. 𝑟 = 𝑎 1 ∨ 𝑎 2 ∨ . . . ∨ 𝑎 𝑘 ← 𝑏 1 , . . . 𝑏 𝑚 , 𝑛𝑜𝑡 𝑏 𝑚+1 , . . . , 𝑛𝑜𝑡 𝑏 𝑛• 𝑥, 𝑦, 𝑧 ∈ T とする. 頂点 𝑦 が 𝑥 から 𝑧 への T における経路(𝑎 1 , . . . , 𝑎 𝑘 , 𝑏 1 , . . . , 𝑏 𝑛 ∈ 𝐴𝑡)

上にあるとき 𝐸 𝑥 ∩ 𝐸 𝑧 ⊆ 𝐸 𝑦 .
2.3

解集合プログラム𝐴𝑡 を 原 子 命 題 (ア ト ム と 略 す) の 集 合 と す る.

𝑟 ∈ Π の 構 成 要 素 を, ℎ(𝑟) = {𝑎 1 , . . . , 𝑎 𝑘 }, 𝑏 + (𝑟) ={𝑏 1 , . . . , 𝑏 𝑚 }, 𝑏 − (𝑟) = {𝑏 𝑚+1 , . . . , 𝑏 𝑛 } と 定 義 す る.

木および木文法𝑏 − (𝑟) = ∅ ならば 𝑟 をファクトとよぶ.

ランク付きアルファベット Σ に対し, 𝑎 ∈ Σ のランク (引数の数) を rank(𝑎) で表す. Σ と変数の集合 X によって生成される木𝑏 + (𝑟) =ファクトである規則 𝑟については ← を省略して 𝑎 1 ∨ . . . ∨ 𝑎 𝑘 と表記する.

全体の集合を 𝑇 (Σ, X) と表記する. 木 𝑡 ∈ 𝑇 (Σ, X) において各

アトムの集合 𝐼 と規則 𝑟 に対し, 𝐼 ∩ ℎ(𝑟) ≠ ∅ か 𝑏 − (𝑟) ∩ 𝐼 ≠ ∅変数 𝑥 ∈ X が高々 1 回しか現れないとき 𝑡 は線形であるという.

か 𝑏 + (𝑟)\𝐼 ≠ ∅ のいずれかが成り立つとき，すなわち, 𝐼 が 𝑏 + (𝑟)木を 2 分木へ変換する方法として fcns 符号化 [10] が知られていのアトムを全て含み 𝑏 − (𝑟) のアトムをどれも含まないならば左る. 𝑡 1 , . . . , 𝑡 𝑛 を木とし, 𝑡 1 = 𝑓 (𝑠1 , . . . , 𝑠 𝑚 ) とする. fcns 符号化

辺のアトムを少なくとも 1 つ含むとき， 𝐼 は 𝑟 を満たすとい

fcns(𝑡1 , . . . , 𝑡 𝑛 ) を次のように定義する.

う. 特に 𝑘 = 0 すなわち左辺が空 (false) であるとき, 規則 𝑟 は
右辺のすべてが同時には成り立たないことを表している. 𝐼 が• fcns() = #.
• fcns(𝑡1 , . . . , 𝑡 𝑛 ) = 𝑓 (fcns(𝑠1 , . . . , 𝑠 𝑚 ), fcns(𝑡 2 , . . . , 𝑡 𝑛 )).

Π に属する任意の規則を満足するとき Π のモデルとよぶ. 𝐼 が
Π𝐼 = {ℎ(𝑟) ← 𝑏 + (𝑟) | 𝑟 ∈ Π, 𝑏 − (𝑟) ∩ 𝐼 = ∅} の (集合の包含関係

𝐺𝑟 = (𝑁, Σ, 𝑅, 𝑆) を文脈自由木文法 (CFTG) とよぶ [20]. こに関する) 極小モデルであるとき, 𝐼 は Π の解集合であるという.

こで 𝑁, Σ (𝑁 ∩ Σ = ∅) はランク付きアルファベットで, それぞ3れ, 非終端記号, 終端記号の有限集合, 𝑅 は生成規則の有限集合.

分解木の表現形式

生成規則は 𝐴(𝑥 1 , . . . , 𝑥 𝑛 ) → 𝑡 の形をしたものであり, 𝐴 ∈ 𝑁,

本節では分解木を表現し, かつ効果的に圧縮可能なデータ構造

rank( 𝐴) = 𝑛, 𝑡 ∈ 𝑇 (Σ ∪ 𝑁, {𝑥 1 . . . 𝑥 𝑛 }). 𝑆 ∈ 𝑁 は開始非終端記号(以降, この段落では表現とよぶ) を提案する．本研究において, 分

で, rank(𝑆) = 0.

解木は木分解ツールの出力を利用する. 木の根頂点の選択や兄木 𝑡 に お け る 変 数 𝑥1 , . . . , 𝑥 𝑛 を そ れ ぞ れ 木 𝑡1 , . . . , 𝑡 𝑛 に置 き 換 え て 得 ら れ る 木 を 𝑡 [𝑥 1 /𝑡 1 , . . . , 𝑥 𝑛 /𝑡 𝑛 ] と 表 す.

弟頂点の並べ方は複数考えられるが, 圧縮はこれらに依存しない.

𝑠 =一方, 分解木上の問合せ処理は木の構造によって効率が変化する

𝐶 [𝑧/𝐴(𝑡 1 , . . . , 𝑡 𝑛 )], 𝑠 ′ = 𝐶 [𝑧/𝑡 [𝑥 1 /𝑡 1 , . . . , 𝑥 𝑛 /𝑡 𝑛 ]] であるようなことが考えられるが, これは木分解に基づくグラフアルゴリズム

𝐴(𝑥 1 , . . . , 𝑥 𝑛 ) → 𝑡 ∈ 𝑅 と 𝐶 ∈ 𝑇 (Σ ∪ 𝑁, X ∪ {𝑧}) が存在する

共通の問題であるため, 本研究では検討の対象としていない.

とき, 𝑠 ⇒𝐺𝑟𝑠 ′ とかく.

⇒𝐺𝑟 の推移閉包, 反射推移閉包をそ

分解木は木構造を持つためそれ自体にも木圧縮のアルゴリズム

れぞれ ⇒+𝐺𝑟 ,⇒∗𝐺𝑟 とかく. また, 𝐺𝑟 から生成される木言語をを適用できる．しかし分解木の頂点の内容であるバッグはグラフ

2

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

𝐵1

𝑏

𝐵2

𝑎

𝑒

𝑑

図1

グラフ 𝐺

𝑓

𝑎

𝑑

𝑎

𝑏
𝐵3

𝑐

𝑐

𝑐

𝑑
𝑐

𝑏
𝐵4

𝑒
𝑓

𝐵1

𝐵1

𝐵1

𝑎−𝑏

𝐵2

𝐵3

𝑎−𝑐 𝑎−𝑏 𝑑−𝑒

𝐵1

𝐵1

𝐵1

𝐵3

𝑎−𝑏

𝐵2

𝐵3

𝐵3

𝐵4

𝑎−𝑐 𝑎−𝑏 𝑑−𝑒𝐵4𝑏−𝑐 𝑎−𝑐 𝑏−𝑐 𝑑− 𝑓𝑏−𝑐 𝑎−𝑐 𝑏−𝑐 𝑑− 𝑓

𝑐−𝑑 𝑏−𝑐 𝑐−𝑑

𝑐−𝑑 𝑏−𝑐 𝑐−𝑑𝑑
図 2 分解木
図3

提案する分解木の表現

図 4 fcns 符号化を行った分解木構造であるためバッグ自体を頂点のラベル名とみなした場合, 異データ構造を提案した点が本研究における新規性である. なお,なる頂点 𝑥 と 𝑦 のバッグ 𝐵 𝑥 と 𝐵 𝑦 に大きな重複があっても木圧
縮ではそれを考慮して圧縮を行うことはできない．そこでバッグ

バッグに含まれるグラフにグラフ構造を対象とした圧縮を適用すについてはそれに属する各辺を頂点で表しそれらの頂点を辺で直る方法も考えられるが, バッグ内のグラフは密となる (頂点数に列に接続し経路 (分岐のない木) として表現する．与えられた分対して辺数が多い) 傾向があり, そのようなグラフに対する効果

解木 T に対し, 次の手順で圧縮に適した T の表現形式 D を生成

的圧縮は期待できない. そのため本研究ではデータ構造を木構造に統合することで圧縮および問合せ処理を単純化することを狙いする (D も木である).

としている.

1. T の各頂点 𝑥 をラベルにもつ頂点を D に含める. これを

4.1

バッグ頂点とよぶ.

分解木の fcns 符号化

本研究で木圧縮に用いる TreeRePair はまず, 入力された分解木

2. 各バッグ頂点 𝑣(そのラベルを 𝑥 とする) について, 以下を行の fcns 符号化を行う．図 3 の分解木を fcns 符号化したものを図う.

4 に示す．図 3 における破線は fcns 符号化によって削除される

T における 𝑥 の親 𝑦 をラベルにもつ頂点 𝑢 を 𝑣 の親として辺, 図 4 における太い実線は追加される辺を表す．符号化されたD に含める. (ただし 𝑥 が T の根頂点であるときは 𝑢 のラベ

分解木には以下の特徴がある．

ルは未定義とし, 𝑢 を D の根とする.)

1. 根頂点の子はただ一つに限られる．

3. D の頂点のうち, ラベルが同じ頂点すべてが兄弟頂点となる

2. 同じバッグ頂点が複数個存在するとき, それらの位置関係はように辺を追加する. ただしバッグ頂点が最も左の子頂点と兄弟関係から祖先子孫関係に変わる．

なるように配置する.

3. 符号化前にバッグ頂点 𝐵 𝑥 が 𝐵 𝑦 の子頂点であったならば符4. 各バッグ頂点のラベルである部分グラフについて, その各辺

号化後もそうである．

をラベルにもつ頂点 (辺頂点) を D に含める. これらの辺頂

4. 同一バッグ内の辺頂点間の位置関係も符号化によって変化し点をバッグ頂点 𝑢 の子として接続する. 辺頂点の接続する際ない．

の順序はラベルである辺について, その 2 つの端点のうちより出現するバッグ数が少ない端点に注目し, この頂点につい4.2て昇順とする. 端点の出現数が等しい場合は, もう一方の端分解木から得られる SLCFTG

前節で述べた fcns 符号化後の分解木は続いて SLCFTG に変換

点の出現数を用いて順序を決定する.

される．分解木において非終端記号に置換されるダイグラムはバッグ頂点同士, 辺頂点同士に限られる．その理由は, バッグ頂点

上記の 4. において辺頂点を出現数に従って並べている. これによってバッグ間に共通する辺が分解木上で隣り合う可能性が高まと辺頂点の組み合わせからなるダイグラムは, 同一のバッグ 𝐵 𝑥

るため圧縮の効果が高まることを予備実験を確認している. 図 2に対しては 1 回しか分解木に現れないことによる．

の分解木をこの方法で表現したものを図 3 に示す．以降, この表

Example 4.1 (ダイグラムの非終端記号への置換例) 図 4 に 示 し現も分解木とよび, あるバッグ 𝐵 𝑥 をラベルにもつ頂点をバッグた分解木に対するダイグラムの置換について説明する．

頂点, また, ある辺 (𝑢, 𝑣)(図 3–5 では, 𝑢 − 𝑣 と表している) をラベ• ダイグラム (𝐵1 , 1, (𝑎, 𝑏)),(𝐵2 , 1, (𝑎, 𝑏)),(𝐵3 , 1, (𝑑, 𝑒)),(𝐵4 , 1, (𝑑, 𝑓 ))ルに持つ頂点を辺頂点とよぶ.

4

は一度のみ出現するため非終端記号に置換されることは

木文法を用いた圧縮法

ない．

• ダイグラム ((𝑎, 𝑏), 1, (𝑎, 𝑐)) は 2 回出現するため非終端記号

本研究では木圧縮の手法である TreeRePair を利用し, その前提の上で分解木の圧縮および非解凍問合せを行う手法を提案してい𝐴1 への置換が行われる．このときダイグラムを生成する規る. 圧縮および非解凍問合せの効果を発揮できるよう, 分解木の則 𝐴1 → ((𝑎, 𝑏), 1, (𝑎, 𝑐)) が構成される．

3

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月• ダイグラム ((𝑏, 𝑐), 1, (𝑐, 𝑑)) は 2 回出現するため非終端記号

5.2

𝐴2 への置換が行われる．このときダイグラムを生成する規SLCFTG の特徴を用いた単一バッグ内の独立集合の計算

木文法において非終端記号の右辺は複数のバッグに出現する部

則 𝐴2 → ((𝑏, 𝑐), 1, ((𝑐, 𝑑), 1, 𝛼)) が構成される．

分グラフを表す (4.2 参照)．非終端記号の右辺が表す部分グラフに対する独立集合を予め計算し，それ以外の部分，つまりその非以上より, 図 4 に TreeRePair を適用すると図 5 に示した SLCFTG

終端記号を参照している部分についての独立集合と合成することが得られる．

で実行時間の短縮が見込まれる．
このアルゴリズムの詳細を図 6 に示す． 𝐵 𝑥 について非終端記
号の右辺から計算された独立集合の集まり I 𝑦 とその非終端記号
を参照している部分に対する独立集合の集まり I 𝑥 が入力であ

𝐵1
𝐴1
𝐴2

→ 𝑎−𝑏

る．まず独立集合 𝐼 𝑥 ∈ I 𝑥 が全ての 𝐼 𝑦 ∈ I 𝑦 と交差する場合, 𝐼 𝑥

𝐵3

𝑎−𝑐

立集合を追加する．更に追加した集合と I 𝑥 に最初から存在する

𝑑−𝑒

𝐵4

𝛼

𝐴2

𝑑− 𝑓

𝐵1

𝐵1

𝐵2

𝐵3

𝐴1

を I 𝑥 から削除する. 次に I 𝑥 に含まれない I 𝑦 の要素である独集合の和集合を追加する．

𝐴1
𝑏−𝑐

𝐴2

→ 𝑏−𝑐

Input: 𝑉𝑥 , 𝑉𝑦 , I 𝑥 , I 𝑦
Output: I 𝑥

𝑐−𝑑
図5

1

図 4 の分解木から得られる SLCFTG

foreach 𝐼 𝑥 ∈ I 𝑥 do

2

𝑚𝑎𝑡𝑐ℎ ← 𝑓 𝑎𝑙𝑠𝑒3

foreach 𝐼 𝑦 ∈ I 𝑦 do
if 𝐼 𝑥 ∩ (𝑉𝑦 − 𝐼 𝑦 ) = ∅ then

45

𝑚𝑎𝑡𝑐ℎ ← 𝑡𝑟𝑢𝑒

6

if 𝑚𝑎𝑡𝑐ℎ = 𝑓 𝑎𝑙𝑠𝑒 then7

I 𝑥 ← I 𝑥 − {𝐼 𝑥 }直接問合せ例:最大独立集合問題

5

グラフ問題の例として最大独立集合問題を取り上げる．独立集
合はグラフの頂点集合であり, 任意の 2 頂点間に辺が存在しない

8ものである. 最大独立集合問題は, 与えられたグラフの独立集合のうち頂点数が最大であるものを求める問題である. この問題は

9

NP 完全であるが幅有界な分解木に変換できるグラフの部分クラ

10スに対しては多項式時間可解であることが知られている．

11

分解木における問合せ処理は以下の手順で計算できる. まずそ12

れぞれのバッグ (すなわち元のグラフの部分グラフ) に対する全foreach 𝐼 𝑦 ∈ I 𝑦 doforeach 𝐼 𝑥 ∈ I 𝑥 do
if ((𝑉𝑥 − 𝐼 𝑥 ) ∩ 𝐼 𝑦 ) ∩ ((𝑉𝑦 − 𝐼 𝑦 ) ∩ 𝐼 𝑥 ) = ∅ thenI 𝑥 ← I 𝑥 ∪ {𝐼 𝑦 } ∪ {𝐼 𝑥 ∪ 𝐼 𝑦 }return I 𝑥
図6ての局所解を求める (5.2 参照). 次にバッグが分解木の葉でない

非終端記号の右辺から計算された独立集合の合成

アルゴリズム場合は，自身の局所解に対して子頂点に対応するバッグの局所解との組み合わせを求める．この組合せ操作を分解木においてボト
ムアップに繰り返し，根頂点のバッグにおいてコスト (最大独立集合問題では頂点数) が最大である集合が元のグラフにおける解5.3

分解木全体の最大独立集合の計算となる．なお，このアルゴリズムの時間計算量は分解木の幅の指

分解木の各バッグの独立集合に対して子バッグの独立集合との数オーダとなる．(グラフの大きさに対して幅が十分小さい定数

和集合を取ったときも独立集合となる組合せで要素数最大となる以下である場合に，効率よく動作することを目的としている．)

ものを求める. 子バッグが複数存在する場合についてもそれぞれ

5.1

単一バッグ内の独立集合の計算について独立に組み合わせを求める．これを分解木においてボト

バッグ 𝐵 𝑥 内の独立集合を求める単純なアルゴリズムについて

ムアップに繰り返す．元のグラフにおける最大独立集合は分解木

述べる．このアルゴリズムはバッグ 𝐵 𝑥 を入力し 𝐵 𝑥 の独立集合の根頂点にあるバッグにおける最大独立集合と一致する．

のすべてからなる集まり I 𝑥 を出力する．

5.4

アルゴリズムは辺 (𝑢, 𝑣) を一つずつ読み込み，その端点を独立

5.4.1

評価実験
実装ツール・実験環境・ベンチマーク

集合に追加する操作を繰り返し，部分グラフにおける独立集合をグラフに対する木分解の計算ツール htd [1] に分解木を提案形

求める．辺 (𝑢, 𝑣) を読み込んだとき端点 𝑢 を含まない既存の独立式 (3 節) で出力する処理を追加した．また，htd で提供されてい集合 𝐼 𝑥 に 𝑢 を追加した集合 𝐼 𝑥 ∪ {𝑢} を I 𝑥 に追加する．𝑣 につる木分解の計算法のうち Minimum ﬁll ordering アルゴリズムをいても同様の処理を行う．一方，𝑢, 𝑣 を含む独立集合は（辺 (𝑢, 𝑣)

使用した．評価実験に使用したデータセット [5] は表 1 の通りでが存在することが分かったので）I 𝑥 から削除する．これを 𝐸 𝑥

ある．これらのグラフに対する木分解によって得られた分解木のの全ての辺に対して繰り返すことで独立集合が求められる．

規模は表 2 の通りである．

4

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

表 1 グラフデータ

表 2 分解木データ

表4

問合せ時間

#

ファイル名

頂点数

辺数

#

頂点数

幅

1

myciel5

47

236

1

26

21

2

huck

74

301

2

34

10

3

queen5

25

160

3

7

18

myciel5

0.913

139.6191.4203440.018

4

david

87

406

4

59

13

huck

1.060

0.573

1.876

0.687

queen50.603

67.733

1.182

462.364

david

1.5172

2.339

3.392

3.413

ファイル名

圧縮率

5.4.2

直接問合せ

解凍後問合せ入力処理

最大独立集合解凍

最大独立集合(𝑚𝑠)

計算 (𝑚𝑠)(𝑚𝑠)

計算 (𝑚𝑠)

TreeRePair によって表 2 の分解木を圧縮した結果を表 3 に示す．表 3 における圧縮率は，圧縮後の木文法のデータサイズを圧
縮前の分解木のデータサイズで割った値を表している．
表3

分解木の圧縮結果

ファイル名

分解木 (kB)

木文法 (kB)

圧縮率 (%)

myciel5

8.22

1.47

17.9

huck

9.34

2.10

22.4

queen5

7.91

david

22.44

1.06
3.32

表 5 問合せ時の使用メモリ

ファイル名

直接問合せ

解凍後問合せ13.3

入力処理

最大独立集合解凍

最大独立集合14.8(kB)

計算 (kB)(kB)

計算 (kB)myciel5

4188

11008

4068

11272

huck

4116

4208

4332

3472

問合せ例として取り上げる最大独立集合の頂点数はそれぞれ#1

queen5

4120

5700

4000

6008

は 23 個，#2 は 27 個，#3 は 5 個，#4 は 36 個であった．表 4，表

david

4140

4744

4168

3776

5.4.3

問合せの実行効率

5 は表 2 に示した分解木についてそれぞれ最大独立集合の要素数
算出を 100 回行ったときの平均実行時間，最大使用メモリを示したものである．これらの表において直接問合せの欄の「入力処理」は終端記号，非終端記号に付与されたラベルおよび木文法の読み込みである．「最大独立集合計算」はバッグに含まれる頂点，辺の読み込みと最大独立集合の要素数の計算を指す．

6

解集合プログラム6.1

解集合プログラムを使用した問合せ

解凍にかかる時間が全体の実行時間に占め

5 節では圧縮された分解木を解凍することなく問合せを行う方

る割合が小さいため，解凍による影響はない．ただし入力の処理法を提案した. しかし, 問合せアルゴリズムは問題ごとに個別ににかかる時間に着目すると直接問合せを行った場合が実行時間が記述する必要があった. 例えば最大独立集合問題の問合せを記述■5.4.3.1 実行時間

するために C++ で約 180 行を要し, 圧縮データへ直接問合せを短い．

行うためプログラムの了解性も低かった.

最大独立集合の計算にかかる時間を比較する．直接問合せでは
図 6 のアルゴリズムを利用することで単一バッグ内の独立集合

本節では解集合プログラムによってアルゴリズムを宣言的にを計算する際の実行時間を解凍後問合せより短縮することがで記述しソルバで実行することで問合せの記述コストを低減する

きた.

ことを提案する. 解集合プログラムを利用した問合せの記述は直接問合せではいずれのグラフデータ

D-FLAT においても提案されている. 本研究では, 分解木に基づに対しても入力処理に必要なメモリ量が大きい．今回使用していくプログラミングを支援する基本的な機能は D-FLAT を参考にる SLCFTG は部分的な解凍が可能である．しかし直接問合せ時して設計したが, 圧縮箇所の直接問合せを支援する機能を新規ににおいても全ての頂点ラベルを処理開始時に読み込むことから考案 · 実装し (6.4, 6.5), その効果を実験的に評価した (6.6). グラ

重複が少ないグラフデータについては直接問合せの恩恵が得に

フ, 分解木, 解集合プログラムについての処理フローを図 7 に示

くい．

す. しかし, 分解木の情報を解集合プログラムのソルバに入力す■5.4.3.2 必要メモリ量

最大独立集合の計算では#1，#3 については直接問合せが解凍ることは容易でない. さらに, 異なる問合せ間で共有できる処理

後問合せより必要なメモリ量が小さい．実行時間と同様に直接問が相当数存在する. そこで分解木のバッグに含まれる部分グラフ

合せについては図 6 のアルゴリズムが利用でき重複部分に対するの情報を参照するための解集合プログラムの組込み述語を実装し独立集合の計算を減らすことができるためである．対して#2，#4

た. 分解木に対する問合せはバッグごとの局所解の計算とそれらについては分解木の重複部分が少ないため，独立集合を格納するの合成プロセスからなる. これら各プロセスに必要な処理についメモリ量の減少量が処理関数に必要なメモリ量に満たない．そのても実装した (図 7 の実行エンジン). 本研究では解集合プログラ

ため必要メモリ量が増大する．

ムの実行には Clingo [15] を使用している.

5日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

1
グラフ

1
木分解

1
分解木

1
木圧縮

グ (親バッグ) の局所解と, 𝑥 のいずれかの子頂点のバッグ (子バッ1
木文法グ) の局所解とを実行エンジン (図 7) 内で保持している. 子バッ
グの局所解は一般に複数存在するので, 𝑐ℎ𝑖𝑙𝑑_𝑟𝑜𝑤(𝑅) によって,「現在は子バッグの 𝑅 番目の局所解を処理中である」ことを表す.

解集合

実行

問合せ

プログラム

1

局所解の合成は親バッグの局所解に対して子バッグの局所解の

エンジン

結果

うち, 矛盾しないものを選択することで行う. 子バッグの局所解

1

解集合プログラム1+

木文法

Clingo1と親バッグの局所解とを区別をするために次のような述語が用意されていると仮定する (6.5 参照).

問合せ処理

𝑐ℎ𝑖𝑙𝑑_𝑚𝑎 𝑝(𝑅, 𝑋, 𝐶): 子バッグの 𝑅 番目の局所解において

図 7 本提案手法による処理フロー

頂点 𝑋 が色 𝐶 で塗られている
6.2

Clingo における解集合プログラム

𝑎𝑐𝑐𝑒 𝑝𝑡 (𝑅) で, 子バッグの 𝑅 番目の解が親バッグの解と合成可能

Clingo 処理系は規則左辺が成り立つとき後の推論のため記憶であることを表す. 対して 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅) で, 𝑅 番目の解が合成できするので, これを「ファクトを生成する」とよぶ. 与えられたグラ

ないことを表す. これら 2 つの述語を定義する規則, すなわち, 解フ 𝐺 = (𝑉, 𝐸) の独立集合を求める解集合プログラムを示す.

の合成を示す規則は以下の通りである:{𝑖𝑛(𝑋) : 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋)}.

(1)← 𝑖𝑛(𝑋), 𝑖𝑛(𝑌 ), 𝑒𝑑𝑔𝑒(𝑋, 𝑌 ).

(2)

𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅) ← 𝑚𝑎 𝑝(𝑋, 𝐶), 𝑐ℎ𝑖𝑙𝑑_𝑚𝑎 𝑝(𝑅, 𝑋, 𝐶 ′), 𝐶! = 𝐶 ′ .

𝑐𝑜𝑠𝑡 (𝐶) ← #𝑐𝑜𝑢𝑛𝑡{𝑋 : 𝑖𝑛(𝑋)}.

(3)

𝑎𝑐𝑐𝑒 𝑝𝑡 (𝑅) ← 𝑛𝑜𝑡 𝑐ℎ𝑖𝑙𝑑_𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅), 𝑐ℎ𝑖𝑙𝑑_𝑟𝑜𝑤(𝑅), 𝑛𝑜𝑡 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅).
(7)

規則に現れる 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋) は 𝑋 ∈ 𝑉, 𝑒𝑑𝑔𝑒(𝑋, 𝑌 ) は (𝑋, 𝑌 ) ∈ 𝐸

規則 (6) では親, 子バッグの局所解に共通して含まれる頂点にを表す. 𝑖𝑛(𝑋) は 𝑋 が独立集合に属することを表す. 𝑐𝑜𝑠𝑡 (𝐶) はついて, 同じ色でないとき 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅) が生成される (𝐶! = 𝐶 ′ は 𝐶

ここでは頂点数を表す.

と 𝐶 ′ が異なることを表す Clingo 記法). 合成可能となるのは任

規則 (1) は Clingo 独自の記法 (以降, Clingo 記法とよぶ) であ意の共通する頂点に関して同じ彩色が行われるときである. よっり, 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋) を満たす 𝑋 が非決定的に選ばれ, ファクト 𝑖𝑛(𝑋) がて規則 (7) では合成が可能なことを表す 𝑎𝑐𝑐𝑒 𝑝𝑡 (𝑅) が生成される生成される [15]. (これに対してもし, 規則を 𝑖𝑛(𝑋) ← 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋).

ための必要条件として, 子バッグの 𝑅 番目の局所解が 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅)とした場合 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋) であるすべての 𝑋 について 𝑖𝑛(𝑋) が生を持たないことを求めている.

成される.) 規則 (2) は 𝑖𝑛(𝑋), 𝑖𝑛(𝑌 ) である任意の 𝑋, 𝑌 について

3 色問題などの決定問題にはなく, コスト最大化問題に必要な𝑒𝑑𝑔𝑒(𝑋, 𝑌 ) が成り立たないことを表す (規則左辺が空であること

コスト計算について述べる. コスト最大化問題の例として最大独に注意. 2.4 参照). つまり独立集合が 𝑋, 𝑌 を要素として持つとき,

立集合問題を再び取り上げる. ここでいうコストとは独立集合のその頂点間に辺が存在しないことを表す (2.1 参照). 規則 (3) は頂点数を指す. 親, 子バッグの局所解を合成したときにコストの𝑖𝑛(𝑋) が成立しているような 𝑋 の個数を数え上げて 𝐶 に代入し𝑐𝑜𝑠𝑡 (𝐶) を生成する. #𝑐𝑜𝑢𝑛𝑡{𝑋 : 𝑃(𝑋)} は 𝑃(𝑋) を満たす 𝑋 の更新も必要である.
親バッグ, 子バッグの 𝑅 番目の各局所解の頂点数の和から共通個数を表す Clingo 記法である.
6.3

(6)

する頂点数を減ずることでコストを更新する. まず子バッグの 𝑅

分解木における問合せ

番目の解と親バッグの局所解に共通する頂点数を計算する規則を問合せアルゴリズムの設計を 3 色問題を例にして述べる. 分解示す.

木に対するグラフ問題の問合せは各バッグにおける局所解を計算し, それらを木に沿って合成することで行う. 問合せアルゴリズ

𝑐𝑜𝑚𝑚𝑜𝑛(𝑅, 𝐶𝐶) ← 𝑐ℎ𝑖𝑙𝑑_𝑟𝑜𝑤(𝑅),ムとして与える解集合プログラムもこの各段階ごとに設計する.

𝐶𝐶 = #𝑐𝑜𝑢𝑛𝑡{𝑋 : 𝑖𝑛(𝑋), 𝑐ℎ𝑖𝑙𝑑_𝑖𝑛(𝑅, 𝑋)}.

まず局所解の計算処理について述べる. 規則 (4) の左辺はClingo 記法であり, 𝑋 に対してただ 1 つの色 (𝐶) を与え, ファク(8)

各局所解の構成要素 𝑖𝑛(𝑋), 𝑐ℎ𝑖𝑙𝑑_𝑖𝑛(𝑅, 𝑋)(6.5 参照) の両方

ト 𝑚𝑎 𝑝(𝑋, 𝐶) を生成する. 規則 (5) は辺 (𝑋, 𝑌 ) の両端点が同じに含まれる頂点 𝑋 を数え上げる.

色であってはならないことを表す.

その頂点数 𝐶𝐶 に対して

𝑐𝑜𝑚𝑚𝑜𝑛(𝑅, 𝐶𝐶) が生成される.
更新後のコストを計算する規則を以下に示す.

1{𝑚𝑎 𝑝(𝑋, 𝐶) : 𝑐𝑜𝑙𝑜𝑟 (𝐶)}1 ← 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋).

(4)← 𝑒𝑑𝑔𝑒(𝑋, 𝑌 ), 𝑚𝑎 𝑝(𝑋, 𝐶), 𝑚𝑎 𝑝(𝑌 , 𝐶).

(5)𝑢 𝑝_𝑐𝑜𝑠𝑡 (𝑅, 𝐷) ←𝑛𝑜𝑡 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅), 𝑐𝑜𝑠𝑡 (𝐶), 𝑐ℎ𝑖𝑙𝑑_𝑐𝑜𝑠𝑡 (𝑅, 𝐶 ′),次に分解木において親子関係にあるバッグの局所解の合成について述べる. 本手法では D-FLAT [2, 4] と同様に, 分解木に対する

𝑐𝑜𝑚𝑚𝑜𝑛(𝑅, 𝐶𝐶), 𝐷 = 𝐶 + 𝐶 ′ − 𝐶𝐶.

(9)𝑢 𝑝_𝑐𝑜𝑠𝑡 (𝑅, 𝐶) ←𝑐ℎ𝑖𝑙𝑑_𝑟𝑜𝑤(𝑅), 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅), 𝑐𝑜𝑠𝑡 (𝐶).

(10)

動的計画法を表すプログラムの実行を支援するため, プログラム

子バッグの 𝑅 番目の局所解が親バッグの局所解と合成可能な

実行中は, 与えられた分解木における現在処理中の頂点 𝑥 のバッ

場合 (規則 (9)) は更新後のコスト 𝐷 を各解のコスト 𝐶, 𝐶 ′ の和か6日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

ら共通部のコスト 𝐶𝐶 を減算した値と定義する. 合成ができない

フの情報を表す述語を用いたファクトを生成する. さらに, ユー

場合 (規則 (10)) は親バッグの解のコストは変更しない.

ザーが定義した述語 𝑃 に対して, 子バッグの 𝑅 番目の局所解において 𝑃 が成り立つことを表す述語 𝑐ℎ𝑖𝑙𝑑_𝑃 を自動的に定義して圧縮部分に対する問合せ

6.4

SLCFTG において非終端記号に関する生成規則の右辺に当たユーザーが利用可能とする機能を実現している.

る部分グラフについて問合せを実行する. 各バッグでは圧縮され6.6ない部分グラフの問合せを行い, 圧縮部分の解と合成することで

6.6.1

評価実験
実装ツール・実験環境・ベンチマーク

解を求める. 解の合成に関しては 6.3 と同様の手法で解集合プロ

5 節で使用したグラフデータのうち, huck および queen5 を使

グラムを与える. 子バッグの局所解と同様, 圧縮部分に関する述用した. これらのデータについての詳細は表 1, 表 2, 表 3 にそれ語を接頭辞"𝑐ℎ𝑖𝑙𝑑"を用いて表現する.

ぞれ示している. 更に頂点数 23, 辺数 71 である myciel4 を評価対親, 子バッグの解の合成では, 合成可能な組み合わせを求め象に加えている. myciel4 に対して木分解を適用した結果, 頂点数て Clingo 内で「一時的に」参照するだけであった. 対して圧12, 幅 12 の分解木が得られた. 圧縮前の分解木のファイルサイズ

縮部分とそれ以外の部分の解を合成するときは合成後の解をは 1.41kB であり圧縮により, そのサイズは 0.44kB となった.

後の段階で一般に複数回使用する. そのため既存の解を更新

6.6.2

最大独立集合問題

しファクトとして実行エンジンに渡して「保存」しなければな

myciel4 の最大独立集合問題の解 (頂点数) は 11 個, 他 2 つにつらない. 更新すべき情報は頂点 ("𝑣𝑒𝑟𝑡𝑒𝑥(𝑋)"), 解に関するファいては 5.4.3 参照. 表 7，表 8 は各分解木についてそれぞれ最大

クト (𝑃(𝑅, 𝑋1 , . . . , 𝑋𝑛 )) である. これらの情報を表すファクト

独立集合の要素数算出を行ったときの実行時間，最大使用メモリ

𝑛𝑒𝑤_𝑣𝑒𝑟𝑡𝑒𝑥(𝑋), 𝑛𝑒𝑤_𝑃(𝑅, 𝑋1 , . . . , 𝑋𝑛 ) を生成する規則を以下にを示したものである．これらの表において直接問合せの欄の「入示す.

力処理」,「最大独立集合計算」の意味は表 4, 表 5 と同じである

𝑛𝑒𝑤_𝑣𝑒𝑟𝑡𝑒𝑥(𝑋) ← 𝑛𝑜𝑡 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋), 𝑐ℎ𝑖𝑙𝑑_𝑣𝑒𝑟𝑡𝑒𝑥(𝑋).

(5.4.3 参照).

(11)

𝑛𝑒𝑤_𝑃(𝑅, 𝑋1 , . . . , 𝑋𝑛 ) ← 𝑛𝑜𝑡 𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅), 𝑛𝑜𝑡 𝑣𝑒𝑟𝑡𝑒𝑥(𝑋),
𝑛𝑒𝑤_𝑃(𝑅, 𝑋1 , . . . , 𝑋𝑛 ).

表7

(12)
ファイル名

規則 (11), (12) によって生成されるファクトは実行エンジンに直接問合せ

解凍後問合せ入力処理

最大独立集合解凍

最大独立集合(𝑚𝑠)

計算 (𝑚𝑠)(𝑚𝑠)

計算 (𝑚𝑠)

渡され, 実行エンジンの内部状態が更新される.
圧縮部分とそれ以外の部分において共通する頂点は共通する解

問合せ時間

myciel4

0.4658094.55

3.043

7961.09を導かれなければならない. そのために圧縮部分の解を合成する

huck

1.29

1025.66

3.474

402.13

過程で既存の解が否定されることがある. 例えば 3 色問題では圧queen50.7271560.1

6.654

16165.39

縮箇所で頂点 𝑎, 𝑏 について解として 𝑚𝑎 𝑝(𝑎, 𝑟𝑒𝑑), 𝑚𝑎 𝑝(𝑏, 𝑟𝑒𝑑)があるときそれ以外の箇所の解においても, これらのファクトを

表 8 問合せ時の使用メモリ持つ解が存在しなければならない. 同一の解は少なくとも 1 つあればよい. 規則 (6), (7) によって解の合成可否を判定している. 非

ファイル名

圧縮箇所の解に対応する, 圧縮箇所の矛盾しない解があるときは𝑎𝑐𝑐𝑒 𝑝𝑡 (𝑅) が生成される. すなわち 𝑎𝑐𝑐𝑒 𝑝𝑡 (𝑅) が成り立たないときは解を削除する.
6.5

解集合プログラム中の組込み述語
表6

直接問合せ

解凍後問合せ入力処理

最大独立集合(kB)

計算 (kB)myciel45608

huck
queen5

解凍

最大独立集合(kB)

計算 (kB)

10268

4720

8584

6872

9652

4752

7940

5696

11532

4754

8900

実装システムが提供する組込み述語

名前説明

6.6.3 3 色問題

𝑣𝑒𝑟𝑡𝑒𝑥(𝑋)

グラフに頂点 𝑋 が含まれる

𝑒𝑑𝑔𝑒(𝑋, 𝑌 )グラフに辺 (𝑋, 𝑌 ) が含まれる

3 色問題の問合せについての結果を示す. 表 9，表 10 は各分解木についてそれぞれ 3 色問題の問合せを行ったときの実行時間，

𝑐ℎ𝑖𝑙𝑑_𝑣𝑒𝑟𝑡𝑒𝑥(𝑋)子バッグに頂点 𝑋 が含まれる

最大使用メモリを示したものである．全データについて解は存在

子バッグの 𝑅 番目の局所解がしない. すなわち 3 色の塗り方は存在しない.

𝑐ℎ𝑖𝑙𝑑_𝑟𝑒 𝑗 𝑒𝑐𝑡 (𝑅)𝑐ℎ𝑖𝑙𝑑_𝑟𝑜𝑤(𝑅)𝑐ℎ𝑖𝑙𝑑_𝑃(𝑅, 𝑋1 , . . . , 𝑋𝑛 )合成可能な解を持たない

表9

子バッグの 𝑅 番目の局所解を処理中
子バッグの 𝑅 番目の局所解において

ファイル名

𝑃(𝑋1 , . . . , 𝑋𝑛 ) が成り立つ

問合せ時間

直接問合せ

解凍後問合せ

入力処理

3 彩色

解凍

3 彩色

(𝑚𝑠)

計算 (𝑚𝑠)(𝑚𝑠)

計算 (𝑚𝑠)

分解木および, 圧縮データに対する問合せを処理するために実

myciel4

0.388

53.393

2.849

46.99

装システム側で提供する組込み述語を表 6 に示す. 実装システ

huck

1.057

363.98

3.496

42.41

ムは実行時に圧縮データを読み込み, ”𝑣𝑒𝑟𝑡𝑒𝑥”, ”𝑒𝑑𝑔𝑒” などグラ

queen50.754

1626.55

6.606

18.17

7

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月

表 10

ファイル名

6.6.4

ない. 直接問合せについて局所解の計算時にその使用メモリ量が問合せ時の使用メモリ

直接問合せ

全プロセス中で最大となる. これは圧縮箇所の抽出によってグラ

解凍後問合せ

入力処理

3 彩色

解凍

3 彩色

(kB)

計算 (kB)(kB)

計算 (kB)myciel4

5620

9536

4688

8068

huck

6680

9464

4680

6420

queen5

5708

10040

4708

7652

フの情報が失われ, 後に削除される解が多く出現することが要因である. 一方, 解凍後問合せについては解の合成時に使用メモリ量が最大となる. バッグごとの局所解を格納することによって使用メモリ量は単調に増大する. 更に局所解の合成時に, 組み合わせ可能な解を記録しているために, 使用メモリ量が増大する.

実行時間

最大独立集合問題, 3 色問題ともにデータの入力および解凍にして TreeRePair を用いた. 提案した表現形式を用いることで効果

かる時間によってこの差が生じる.

的な圧縮が可能であることが示された.

両問題とも問題の計算にかかる時間は解凍後問合せが直接問合

更に圧縮データに対して解凍を行わず問合せを評価する 2 種のせより小さい. 問合せ手法間で子バッグの局所解を親バッグの局手法を提案し実装した. 問合せアルゴリズムを直接記述する手法

所解と合成する処理に違いはない. 一方, バッグの局所解を計算と解集合プログラムの形式で与える手法である.

する処理は問合せ手法により異なる. 具体的には直接問合せではアルゴリズムを直接記述する手法においては最大独立集合問題

圧縮箇所 (複数のバッグに共通する部分グラフ) について先に問を例にし評価実験を行った. 実験の結果, 解凍せずに問合せを行合せ処理を実行する. 次に非圧縮箇所の解を計算し, それらの解う提案手法は, 解凍後問合せを行う手法に比べ実行時間においてを合成することでバッグ全体の解を求めている. 解の計算と合成優れていることがわかった. 問合せアルゴリズムの記述に解集合

は, まずデータに対して問合せプログラムとグラフデータの両方

プログラムを利用する手法においては最大独立集合問題に加え, 3を Clingo の規則に変換する処理を行い, 次にソルバの Clingo を

色問題を例に評価実験を行った. 今回の実装では直接問合せを行呼び出すことで実行している. 最大独立集合問題の問合せを実行う場合より解凍後に問合せする場合が実行時間が小さくなった.

したときの Clingo の呼び出し回数を測定した結果を表 11 に示

7.2

す. myciel4 についてはバッグ間に共通する部分グラフの圧縮がては実行時間, データサイズが増大し変換が困難となる. これは圧縮箇所に対して事前の問合せがなされているため, その局所解

分解木を提案する表現形式 (3 節) で出力する際に予め非終端記号に対する合成処理に関しても Clingo が呼び出されている. デー

への置換を一部実行することで, 重複部分の処理が低減できるたタの変換と呼び出し, 実行にかかる時間が大きくなってしまうた

め解消できると考えられる.

めに, 全体の実行時間が増大してしまう. 現在の実装では非圧縮

実社会で使用されるグラフデータは, それらに対する更新頻度

部分の一つの解ごとに合成可能な解を求めている. これによりが高い. 更新を反映させるためには, 圧縮した木を解凍し, デー

Clingo の呼び出し回数が増大してしまう. また圧縮効果の大きいタを更新した後に再度圧縮する必要がある. 木に対する圧縮法

データにおいては, 圧縮箇所は多数存在する. 圧縮箇所ごとに解について解凍することなく直接更新を行う手法が提案されていの合成を実行しているため合成の処理回数が増大してしまっている [16]. これらの手法を基に圧縮された分解木を直接更新するこる. 更に合成過程において削除される解が多いため, 最終的な解とで提案した圧縮法の実用性が高まることが期待できる.

の個数に比べ Clingo の呼び出し回数が増大してしまう.

アルゴリズムを問題ごとに記述した場合において直接問合せの実行時間は解凍後問合せに比べて実行時間は小さい. しかし改善

最大独立集合問題における Clingo 呼び出し回数

解凍後問合せ

12

12

huck

396

queen56708

myciel4

今後の課題

提案した分解木の表現形式は木の頂点数や幅が大きい木に対しなされておらず, 問合せについても差異はない. 他の 2 データは

直接問合せ

まとめ

法を利用した圧縮を前提とし, 実装実験においては, 圧縮ツールとにかかる時間は直接問合せが解凍後問合せより小さい. 解凍にか

データ名

7.1

果的に圧縮可能な構造へ変換する手法を提案した. ここでは木文

よって異なるが, その読み込みにかかる時間は小さい. 入力処理

局所解の計算あとがき
本研究では, グラフに対する木分解により得られた分解木を効

ついては共通の処理を行っている. 解集合プログラムは問題に

表 11

7

が小さいグラフデータもあり, 効率に影響を与える要素を特定し,グラフの構造に応じた手法の改善が見込めると考えられる.

解の合成

アルゴリズムの記述に解集合プログラムを利用した場合におい2077て直接問合せの実行時間が大きい. その要因は圧縮箇所を利用し

34

294

た解の合成にかかる Clingo の呼び出し回数の増大が原因であっ

7

1272

た. 現在の実装は個別の解ごとに Clingo が呼び出されているが,全ての解を同時に処理することで実行時間を短縮できると考えら

6.6.5

れる.

最大使用メモリ量

最大独立集合問題, 3 色問題いずれも最大使用メモリ量は直接問合せにおいて大きい. 6.6.4 に示した実行時間と同様に局所解の合成処理は問合せ手法によって違いがなく, 使用メモリに影響は8日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 16, 2022 年 3 月[25] 小島和之，関浩之, 木分解と木文法圧縮を利用したグラフ圧縮法お謝辞

よび圧縮データへの直接問合せ処理法の提案と評価，電子情報通信
学会データ工学研究会，DE2020-13, 2020.09.
[26] 小島和之, 関浩之, 木分解の圧縮および解集合プログラミングによる問合せ, 電子情報通信学会データ工学研究会, DE2021-16, 2021.12.

木圧縮に関して種々ご助言を頂いた名古屋大学助教 橋本健二
氏, ならびに, 木分解ツール htd および解集合プログラムソルバ

Clingo についてご教示頂いた名古屋大学教授 番原睦則先生に感謝いたします.

参考文献[1] M. Abseher. https://github.com/mabseher/htd[2] M. Abseher, B. Bliem, G. Charwat, F. Dusberger, M. Hecher and S.
Woltran, The D-FLAT System for Dynamic Programming on Tree
Decompositions, JELIA 2014, LNAI 8761, 558–572.
[3] M. Besta and T. Hoeﬂer, Survey and Taxonomy of Lossless Graph
Compression and Space-Eﬃcient Graph Representations, CoRR
abs/1806.01799, 2018.
[4] B. Bleim, M. Morak and S. Woltran, D-FLAT: Declarative Problem
Solving Using Tree Decompositions and Answer-Set Programming,
Theory Prac. Log. Program, 12(4-5), 445–464, 2012.
[5] H. L. Bodlaender, TreewidthLIB.
http://www.cs.uu.nl/research/projects/treewidthlib[6] P. Boldi and S. Vigna, The Webgraph Framework I: Compression
Techniques, 13th International Conference on World Wide Web, 595–
602, 2004.
[7] N. R. Brisaboa, S. Ladra and G. Navarro, K2 -trees for Compact Web
Graph Representation, 16th International Symposium on String Processing and Information Retrieval, 18–30. 2009.
[8] G. Buehrer and K. Chellapilla, A Scalable Pattern Mining Approach to
Web Graph Compression with Communities, International Conferenceon Web Search and Data Mining, 95–106, 2008.
[9] F. Claude and S. Ladra, Practical Representations for Web and Social Graphs, 20th ACM Conference on Information and Knowledge
Management, 1185–1190, 2011.
[10] H. Comon, et al., Tree Automata Techniques and Applications, 2008.
http://tata.gforge.inria.fr/[11] R. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity, Chapter 10 Tree Width and Dynamic Programming, 2013.
[12] W. Fan, J. Li, X. Wang and Y. Wu, Query Preserving Graph Compression, ACM Special Interest Group on Management of Data, 157–168,
2012.
[13] J. Fischer and D. Peters, GLOUDS: Representing Tree-Like Graphs,
Journal of Discrete Algorithms, 36, 39–49, 2016.
[14] A. P. Francisco, T. Gagie, S. Ladra and G. Navarro, Exploiting
Computation-Friendly Graph Compression Methods for AdjacencyMatrix Multiplication, Data Compression Conference, 307–314, 2018.
[15] M. Gebser, R. Kanminski, M. Lindauer, M. Ostrowski, J. Romero, T.
Schaub, S. Thiele and P. Wanko, Potassco guide version 2.2.0.
[16] K. Hashimoto, R. Takayama and H. Seki, Direct Update of XML
Documents with Data Values Compressed by Tree Grammars, IEICE Transactions on Information and Systems, E101-D(6), 1467–1478,
June 2018.
[17] C. Hernández and G. Navarro, Compressed Representations for Web
and Social Graphs, Knowledge and Information Systems, 40, 279–313,
2014.
[18] M. Jark, R. Pichler and S. Wotran, Answer-Set Programming with
Bounded Treewidth, IJCAI 2009, 816–822.
[19] U. Kang, C. E. Tsourakakis and C. Faloutsos, PEGASUS: Mining
Peta-Scale Graphs, Knowledge and Information Systems, 303–325,
2011.
[20] M. Lohrey, S. Maneth and R. Mennicke, XML Tree Structure Compression Using RePair, Information Systems, 38, 1150–1167, 2013.
[21] S. Maneth and F. Peternek, A Survey on Methods and Systems forGraph Compression, CoRR abs/1504.00616, 2015.
[22] S. Maneth and F. Peternek, Compressing Graphs by Grammars, IEEE
32nd International Conference on Data Engineering, 109–120, 2016.
[23] F. Merz and P. Sanders, PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies, European Symposium
on Algorithms, 701–712, 2014.
[24] H. Yildirim, V. Chaoji and M. J. Zaki, GRAIL: A Scalable Index for
Reachability Queryies in Very Large Graphs, The VLDB Journal, 21,
509–534, 2012.

9