2004年 4月16日 並列 (連言)と再帰 >> 目次 (作成日順)
  ● QUESTION   再帰は、並列ではないのか。
  ▼ ANSWER   ちがう。 再帰は、帰納関数である。
2009年 5月 1日 補遺  



再帰は、関数の観点から言えば、帰納関数である。

 関係の論理 aRb として、a=b となる状態が、「再帰 (recursive)」である。
 「再帰 (recursive)」 は、その呼称が示しているように、帰納関数 (回帰) である。
 [ f (y + 1) = h (y, f (y)) ]。
 データベース 設計では、「再帰」 というのは、(帰納関数の考えかたを応用して、) 1つの entity のなかの元 (メンバー) を、順次、後続として、1つの構造を生成することをいう。

 以下を前提にする。

 (1) 部品 entity のなかに、製品・半製品・原材料がいっしょに収録されている。
   言い換えれば、部品番号の コード 体系のなかで、製品・半製品・原材料が記述されている。
 (2) 製品・半製品・原材料は、製品形態区分コードを使って、識別されている。
 (3) 以下の部品構成とする。

     製品 001
      半製品 002
       原材料 004
       原材料 005
      半製品 003
       原材料 006
       原材料 007

 
resource 系の再帰は、T字形 ER手法の観点から言えば、対照表の変形である。

 部品構成では、階数 (部品表の階 [ レベル ])と次数 (同じ レベル の部品の種類) を考慮しなければならない。したがって、以下の データ 構造となる。  ただし、次数は、部品の数でわかるので、必要ない。

   { 階数、部品 コード (R)、部品 コード (R)、員数 }.

 
 { 部品 コード (R)、部品 コード (R) } は、多義でもなければ、HDR-DTL でもない。対照表の変形である。
 すなわち、自らを対象とした (aRb において、a=b となる) 対照表 [ 部品. 部品. 対照表 ] である(注意)

 この部品構成は、上述の データ 構造では、以下のように記述される。

  { 0、001、002、 2個 }
  { 0、001、003、 4個 }
  { 1、002、004、10個 }
  { 1、002、005、 4個 }
  { 1、003、006、10個 }
  { 1、003、007、 4個 }
  { 2、004、null }
  { 2、005、null }
  { 2、006、null }
  { 2、007、null }

 
 この構造で問題点となるのは、階数と員数の扱いである。
 たとえば、{ 0、001、002、2個 } では、レベル 0 として、製品 001 を扱っていながら、半製品の員数を記述している。したがって、最下位では、null が起こっている。階数と員数を揃えるために、前述した構造のなかの順序 (部品構成の階数) を 1つ ズラ す──ちなみに、データ 件数が減った点にも注意されたい。

  { 1、001、002、 2個 }
  { 1、001、003、 4個 }
  { 2、002、004、10個 }
  { 2、002、005、 4個 }
  { 2、003、006、 6個 }
  { 2、003、007、30個 }

 
構成の停止 (あるいは、継続) を示すために、LOW-LEVEL-FLAG が使われる。

 さて、たとえば、上述した構造では、レベル 2 の下に展開が、まだ、あるのかどうか、を判断できない。
 たとえば、万が一、だれかが、{ 1、001、003、4個 } を削除したら、プログラム の アルゴリズム は、以下の構造しか提示しない。

     製品 001
      半製品 002
       原材料 004
       原材料 005

 
 したがって、展開の 「継続有り」 と 「停止」 を示すために、LOW-LEVEL-FLAGLOW-LEVEL-CODE と云うことが多い) を使う。以下の構造では、LOW-LEVEL-CODE を LLC と略称する。

  { 1、001、002、 2個、LLC }
  { 1、001、003、 4個、LLC }
  { 2、002、004、10個、LLC }
  { 2、002、005、 4個、LLC }
  { 2、003、006、 6個、LLC }
  { 2、003、007、30個、LLC }

 
(注意)
 本稿のなかで示した例は、resource 系の例であるが、event 系であっても、T字形 ER手法の 「関係文法」 として、aRb において、a≠b のとき、関係が 「1:複数」 である ルール を、後続 event に適用すれば、先行 event の認知番号が後続 event のなかに複写される。 その ルール が、自らを対象とした (aRb において、a=b となる) 状態が再帰である。
 たとえば、伝票の 「赤黒方式」 が典型的な例である。

  { 受注番号、受注日、受注数 }
  { 受注番号 (R)、受注番号 (R) }

 



[ 補遺 ] (2009年 5月 1日)

 本 エッセー を今読み返してみたら、ずいぶん冗長な説明をしていると思う。
 「再帰」 は、ひとつの集合のなかの任意の元を選んできて、並べる関数のことです。たとえば、以下の集合を例にして説明します。

 { a1, a2, ・・・, an }.

 そして、この集合において、元を並べる n-項 特徴関数を考えます。

 f ( a1, a2, ・・・, an ).

 そして、この特徴関数を 「2項関係」 f ( ak, ak+1 ) で構成したのが 「再帰」 です。

 本 エッセー の説明が長くなった理由は、「部品構成」 において、LLC も述べたかったからでしょうね。
 「再帰」 で注意してほしい点は、「指示関係」 と 「関係に付与する呼称」 を混同しないでほしいという点です。たとえば、以下の部品構成を例にします。

 { 部品番号、部品名称、・・・ }.
 { 部品番号 (R)、部品番号 (R) }.

 この構成において、{ 部品番号 (R)、部品番号 (R) } に対して、「方法論が未熟だから、同じ名前 [ 部品番号 (R) ] を使っているのであって、正式には、{ 親部品、子部品 } にしなければならない」 と非難したひとがいましたが、論理的意味論を理解していないのでしょうね。部品構成では、「道」 (グラフ では、頂点と頂点とのあいだの辺を 「道」 と云います) を辿る やりかた には、以下の 2つが考えられます。

 (1) DFS (Depth First Search)
 (2) BFS (Breadth First Search)

 DFS は 「階数」 を辿る やりかた で、BFS は 「次数」 を辿る やりかた です。したがって、 f ( ak, ak+1 ) において、DFS は 「親-子 関係」 を示し、BFS は 「兄弟 関係」 を示します──言い換えれば、「親-子 関係」 のみが特徴関数 f ( ak, ak+1 ) を構成する訳ではないということに注意してください。「親-子 関係」 とか 「兄弟 関係」 というのは、 f ( ak, ak+1 ) において、2 項の 「関係」 に対して付与された呼びかたであって、元の指示関係ではない、という点に注意してください。f (部品番号 (R)、部品番号 (R)) は、「部品」 entity の元を指示して──言い換えれば、それらは 或る前提から導出されていることを示して、すなわち、「構成」 の途中で、いままで定義されてもいない項を導入していないことを示していて──、かつ、「並べる」 関数です。したがって、部品番号 (R) は、指示関係を示しているのであって、部品どうしの関係を示している訳ではないのです。この関数のなかに、どういう値が入るかは──すなわち、DFS の道における値が代入されるのか、あるいは、BFS の道における値が代入されるのかは、べつの論点です。逆に言えば、定義されていない語を いきなり途中で導入するのは、構文論・意味論の違反になります。ただし、RDB は、一つの テーブル のなかで同じ名称が複数付与されることを禁止しているので、実装するときには、以下のように、部品番号 (R) の名称を変えなければならない。

 { 部品番号-1、部品番号-2 }.

 そして、{ 部品番号-1、部品番号-2 } を { 親部品、子部品 } と呼ぶのなら そうすればいいし、{ 先行部品、後続部品 } とするなら そうすればいいでしょう。





  << もどる HOME すすむ >>
  データ解析に関するFAQ