原因結果グラフ(げんいんけっかぐらふ)情報システム用語事典

CEG / cause-effect graph / 原因効果グラフ

» 2011年11月07日 00時00分 公開
[@IT情報マネジメント編集部,@IT]

 システムへの入力条件と、それに対応するシステムの動作との間の論理関係を視覚化した有向グラフのこと。複数の入力要素が一定の規則で作用し合い、出力結果を導くような問題を記述する際に有効である。ソフトウェアテストのテスト設計などに利用される。

 原因結果グラフは、原因−結果や原因−原因の間にNOT・AND・ORなどの論理規則や制限があるとき、それらをブーリアングラフの形式にして要素間の論理関係を視覚化する。自然文による表現に代え、ブール演算子(and, or, not)を使ってシステム仕様やビジネスルールを記述することは、それらに潜むあいまいさや矛盾の発見に役立つ。

原因結果グラフのイメージ

 原因結果グラフにはさまざまな流儀があるが、基本的には「ノード」「リンク」「制約」の3つの要素で構成される。

 ノードは“原因”や“結果”を表す。数学的にいえば命題変数であって、真理値(真か偽)を持つ。情報システムやソフトウェアの仕様であれば入力条件、入力条件の同値クラス、システムの動作を引き起こすイベント、あるいは期待出力結果や事後条件が該当する。表記としては円形や矩形で表現され、通常は左に原因、右に結果を配置する。

 リンクはノード同士を接続する要素で“論理演算”を表す。数学的には論理記号、論理結合子であって、原因ノードの真理値を操作して結果ノードの値を出力する。リンクでノードを連鎖的に結合することで、システムの論理関係を記述する。

 標準的な原因結果グラフではノードとリンクの表記として、次の4つの基本記号が用意されている。IDENTITY(※)は原因と結果を直結する記号で真偽値は変化しない。NOTはブール演算子の否定に該当するもので原因が真ならば結果は偽、原因が偽ならば結果は真を返す。ORとANDは多項演算子で、前者は複数の原因のうちいずれかが真ならば結果は真を返し、そうでなければ偽を返す。後者は複数の原因のすべてが真ならば真を返し、そうでなければ偽を返す。

※ 同値と訳されること多いが、同値分割の同値(equivalence)とは区別すべきものである。初期にはDIRECTと呼ばれていた

原因結果グラフの基本記号

 原因と結果の論理関係とは別に、原因同士が特定の条件を持っている場合もある。例えば、「性別欄の入力値は、男性か女性のどちらか1つ」といったようなものだ。原因結果グラフにはノード間の制約を表す表記法が用意されている。

 EXCL制約は「あるノードが真になったとき、ほかのノードは偽」、INCL制約は「少なくとも1つ以上のノードが真」、ONE制約は「真になるノードは1つだけ」、REQ制約は「このノードが真となるために、先に真になっているノードが必要」、MASK制約は「このノードが真になると、真偽を問われなくなるノードがある」の6つである。

原因結果グラフの基本記号

 原因結果グラフは、原因ノードに入力条件を与えると結果ノードの出力が決定する組み合わせ論理回路のグラフ表現である。論理を表現する図式形式言語であり、システムやソフトウェアの仕様の記述に使用すれば、形式仕様記述ということになる。従って原因結果グラフは、テストケースの抽出する以外に、仕様の論理的矛盾点やあいまいさの検証に利用できるとされる。

 原因結果グラフは、米国IBMのテスト担当者だったウィリアム・R・エルメンドルフ(William R. Elmendorf)によって考案された。エルメンドルフは論文『Automated Design of Program Test Libraries』(1970年)で、テスト設計プロセスを自動化するTELDAP(Test Library Design Automation Program)というツールを提唱、その中で原因結果グラフ(cause-and-effect graph)を紹介した。

 これは電子回路(ハードウェア)のロジックテスト用に考案されたDアルゴリズム(1966年)の双方向経路探索法に基礎を置き、ソフトウェアテスト向けに制約などを付加したテスト技法である。エルメンドルフの原因結果グラフでは結合子にAND・NAND・OR・NOR・NOT・DIRECTの6つが、制約に相互排他・総包括・相互排他総包括の3つが導入されている。

 原因結果グラフを有名にしたのは、グレンフォード・J・マイヤーズ(Glenford J. Myers)の著書『The Art of Software Testing』(1979年)である。このロングセラーで提案された技法によって、原因結果グラフはテスト設計ツールとして広く認知されるようになった。本稿の説明もマイヤーズの方法に基づいている。

参考文献

  • 『ソフトウェア・テストの技法〈第2版〉』 グレンフォード・J・マイヤーズ、トム・バジェット、テッド・M・トーマス、コーリー・サンドラー=著/長尾真=監訳/松尾正信=訳/近代科学社/2006年7月(『The Art of Software Testing: 2nd ed』の邦訳)
  • 『ソフトウェア設計の基礎』 大木幹雄=著/日本理工出版会/1999年1月
  • 『ソフトウェアのテスト技法――計算機科学・ソフトウェア技術講座 13』 玉井哲雄、松田茂広、三嶋良武=著/共立出版/1988年1月
  • 『ソフトウェアの検査と品質保証――日科技連ソフトウェア品質管理シリーズ 第4巻』 石井康雄=編/日科技連出版社/1986年10月
  • 『Cause-Effect Graphs in Functional Testing』 William R. Elmendorf=著/IBM Technical Report TR-00.2487/IBM Systems Development Division/Nov. 1973
  • 『Automated Design of Program Test Libraries』 William R. Elmendorf=著/IBM Technical Report TR 00.2089/IBM Systems Development Division/Aug. 1970

Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ