MariaDB で Newton 法の計算をする方法 #

概要 #

MariaDB [1]¹ はデータベース管理システムのひとつで，MySQL と呼ばれる歴史あるデータベース管理システムの派生として開発されているものです．

Newton 法 は非線形方程式の解を反復によって数値計算するための方法です．求める解の近くでは高速に解に収束する性質をもち，広く使われています．具体的にいえば，微分可能な関数 \(f:\mathbb{R}\to\mathbb{R}\) について，適当な初期値 \(x^{(0)}\in\mathbb{R}\) を与えて， \(x^{(k+1)}=x^{(k)}-f(x^{(k)})/f'(x^{(k)})\) \((k=0,1,\dots)\) として解を更新する方法です．

本ノートの作成者は，データベースの初心者です．データベース管理システムに慣れるため，MariaDB でこの Newton 法を動かしてみようと思います．

まずは，MariaDB のドキュメントを参考に，SQL の主要なキーワードである SELECT や WITH で何ができるのかを確認します．次に，WITH RECURSIVE というキーワードで再帰処理ができることを確認します．最後にこれらを組み合わせて，方程式 \(x^2-2=0\) の正の解を Newton 法で計算することで \(\sqrt{2}\) を求めます．

SQLの文法 #

データベース管理システムにおいて，データの操作や定義を行うための言語を SQL といいます．統一標準規格が存在しますが，具体的な文法はデータベース管理システムごとに微妙な差があります．本節では，Newton 法を動かすために使う MariaDB の SQL の文法をまとめます．

SELECT #

MariaDB では加法の演算ができて，SELECT を使ってその結果が確認できます．
https://mariadb.com/kb/en/addition-operator/

SELECT 3+5;
+-----+
| 3+5 |
+-----+
|   8 |
+-----+

これは式 3 + 5 の評価結果が 8 ということなのだと思います．

これをより単純化した例として， SELECT 1; を実行したところこうなりました．

SELECT 1;
+---+
| 1 |
+---+
| 1 |
+---+

これは式 1 の評価結果が 1 ということなのだと思います．

この仕様について，SELECT 文の説明ページでは明示的に述べられてはいませんでした． BNF記法による説明はありますが，select_expr の定義まで詳細に書かれていません．
https://mariadb.com/kb/en/select/

なお，AS で別名を付けられるので，こんなことができます．標準的ではありませんが，本ページではこれを \(x=1\) という式のSQLにおける表現と捉えておきます．

SELECT 1 AS x;
+---+
| x |
+---+
| 1 |
+---+

この表を T とおいて，表 T の列 x の値を選択するSQL文は FROM を使って以下のように書けます．

SELECT 
  x
FROM
  (SELECT 1 AS x) AS T;
+---+
| x |
+---+
| 1 |
+---+

表が2つあっても同様です．

SELECT 
  x, y
FROM
  (SELECT 1 AS x) AS T1,
  (SELECT 2 AS y) AS T2;
+---+---+
| x | y |
+---+---+
| 1 | 2 |
+---+---+

WITH #

WITH は以下の構文で使えます．
https://mariadb.com/kb/en/with/

WITH [RECURSIVE] table_reference [(columns_list)] AS  (
  SELECT ...
)
[CYCLE cycle_column_list RESTRICT]
SELECT ...

前節の例は WITH を使って表現できます．

WITH T AS (
  SELECT 1 AS x
)
SELECT 
  x
FROM
  T;
+---+
| x |
+---+
| 1 |
+---+

テーブルが2つの場合も同様に WITH を使って表現できます．

WITH T1 AS (
  SELECT 1 AS x
),
T2 AS (
  SELECT 2 AS y
)
SELECT
  x, y
FROM
  T1, T2;
+---+---+
| x | y |
+---+---+
| 1 | 2 |
+---+---+

columns_list を使うとこう書けます．

WITH T1 (x) AS (
  SELECT 1
),
T2 (y) AS (
  SELECT 2
)
SELECT
  x, y
FROM
  T1, T2;
+---+---+
| x | y |
+---+---+
| 1 | 2 |
+---+---+

WITH を使って作られる一時的なテーブルまたはそれに対するクエリを 共通テーブル式 (Common Table Expression, CTE) と呼ぶようです．
https://mariadb.com/kb/en/with/

UNION #

2つの表を結合するには UNION というキーワードを使います．
https://mariadb.com/kb/en/union/

UNION を使って (1, 1), (1, 2) というレコードをこの順に結合すると以下のようになります．

SELECT 1 AS x, 1 AS y
UNION
SELECT 1, 2;
+---+---+
| x | y |
+---+---+
| 1 | 1 |
| 1 | 2 |
+---+---+

2つの行が完全に一致すると追加されません． UNION は重複行を削除します．

SELECT 1 AS x, 1 AS y
UNION
SELECT 1, 1;
+---+---+
| x | y |
+---+---+
| 1 | 1 |
+---+---+

UNION の代わりに UNION ALL を使うと削除されません．

SELECT 1 AS x, 1 AS y
UNION ALL
SELECT 1, 1;
+---+---+
| x | y |
+---+---+
| 1 | 1 |
| 1 | 1 |
+---+---+

WITH RECURSIVE #

WITH で紹介した共通テーブル式 (CTE) ですが，RECURSIVE というキーワードを使うと，CTE を再帰的に参照することができるようです．
https://mariadb.com/kb/en/recursive-common-table-expressions-overview/

このページの説明によると，

with recursive R as (
  select anchor_data
  union [all]
  select recursive_part
  from R, ...
)
select ...

とすると，以下のように処理されるようです．

anchor_data を計算する．
新しいデータを取得するために recursive_part を計算する．
新しいデータが空でなければ2に戻る．

例えば，以下のように WITH RECURSIVE を使って \(n=1,2,\dots,10\) に対応するテーブルを生成できます．

WITH RECURSIVE T (n) AS (
  SELECT
    1
  UNION ALL
  SELECT
    n + 1
  FROM
    T
  WHERE
    n < 10
)
SELECT
  n
FROM
  T;
+------+
| n    |
+------+
|    1 |
|    2 |
|    3 |
|    4 |
|    5 |
|    6 |
|    7 |
|    8 |
|    9 |
|   10 |
+------+

これを一般の等差数列に拡張します．つまり， \(a_n=a+(n-1)d,\ n=1,2,\dots,n_{\mathrm{max}}\) を計算します． \(n\ge2\) ならば \(a_n=a_{n-1}+d\) であることを使います．ここでわかりやすさのため， \(a,d,n_{\mathrm{max}}\) は設定値とみなして，これらをひとつの共通テーブル式 Config で表現することにします．

これらをふまえて \(a=2,d=3,n_{\mathrm{max}}=8\) の場合の SQL 文を考えると以下のようになります．

WITH RECURSIVE T (n, a_n) AS (
  SELECT
    1, a
  FROM
    Config
  UNION ALL
  SELECT
    n + 1, a_n + d
  FROM
    T, Config
  WHERE
    n < n_max
),
Config (a, d, n_max) AS (
  SELECT 2, 3, 8
)
SELECT n, a_n FROM T;
+------+------+
| n    | a_n  |
+------+------+
|    1 |    2 |
|    2 |    5 |
|    3 |    8 |
|    4 |   11 |
|    5 |   14 |
|    6 |   17 |
|    7 |   20 |
|    8 |   23 |
+------+------+

Newton 法の計算 #

前節より，WITH RECURSIVE を利用すると再帰処理ができることがわかりました．そこで，本節では，WITH RECURSIVE を使って MariaDB で Newton 法を実行してみます． SQL 文は等差数列の場合と同様に作れます．

まず，Newton 法とは， \[ x^{(k+1)}=x^{(k)}-\frac{f(x^{(k)})}{f'(x^{(k)})},\quad k=0,1,\dots \] の形で近似解を更新する計算法でした．このままでは計算が終わらないので，適当な基準で反復を停止する必要があります．そこで， \(\theta>0,k_{\mathrm{max}}>0\) に対して，収束判定条件を \(k\ge1\) のとき \(|x^{(k)}-x^{(k-1)}|/|x^{(k-1)}|<\theta\) として，最大反復回数を \(k_{\mathrm{max}}\) とします．これは，ほとんど解が更新されなくなったか最大反復回数に達したら反復を終了するということになります．ここで， \(k\ge1\) ならば， \[ \frac{|x^{(k)}-x^{(k-1)}|}{|x^{(k-1)}|}=\frac{|f(x^{(k-1)})/f'(x^{(k-1)})|}{|x^{(k-1)}|} \] であることに注意してください．

収束したときの値が取得できる SQL 文を作るものとして，具体的な SQL 文を考えます．

まず， Newton という共通テーブル式を用意します．この Newton は列 k, x, err, converged をもつものとします．定義は以下のとおりです．

列	型	意味
k	INT	反復回数を表すインデックス \(k\) .
x	DOUBLE	第 \(k\) 近似解 \(x^{(k)}\) .
err	DOUBLE	第 \(k\) 近似解における直前の近似解との相対誤差 \(\|x^{(k)}-x^{(k-1)}\|/\|x^{(k-1)}\|\) , ただし \(k=0\) のとき `NULL`.
converged	BOOLEAN	第 \(k\) 反復で収束判定条件を満たしたかどうか．

次に，Config という共通テーブル式を用意します．この Config は列 x0, theta, k_max をもつものとします．定義は以下のとおりです．

列	型	意味
x0	DOUBLE	初期値 \(x^{(0)}\) .
theta	DOUBLE	収束判定条件のしきい値 \(\theta\) .
k_max	INT	最大反復回数 \(k_{\mathrm{max}}\) .

これらを用いて，方程式 \(x^2-2=0\) の正の解を Newton 法で計算することで \(\sqrt{2}\) を求めるための SQL 文を考えます．その SQL 文と実行結果は以下のようになります．ただし，意図通り動作するように，適宜 CAST で型を明示的に与えています．

WITH RECURSIVE Newton (k, x, err, converged) AS (
  SELECT
    0, CAST(x0 AS DOUBLE), CAST(NULL AS DOUBLE), FALSE
  FROM
    Config
  UNION ALL
  SELECT
    k + 1,
    x - (POWER(x, 2) - 2)/(2*x),
    ABS((POWER(x, 2) - 2)/(2*x)) / ABS(x),
    ABS((POWER(x, 2) - 2)/(2*x)) / ABS(x) < theta
  FROM
    Newton, Config
  WHERE
    k < k_max AND converged = FALSE
),
Config (x0, theta, k_max) AS (
  SELECT
    1, 1.0e-15, 100
)
SELECT
  k, x, err
FROM
  Newton;
+------+--------------------+--------------------------------+                    
| k    | x                  | err                            |                                  
+------+--------------------+--------------------------------+                                 
|    0 |                  1 |                           NULL |                                  
|    1 |                1.5 |                            0.5 |                                  
|    2 | 1.4166666666666667 |            0.05555555555555555 |                                  
|    3 | 1.4142156862745099 |          0.0017301038062284225 |                                  
|    4 | 1.4142135623746899 |       0.0000015018217097673717 |                                  
|    5 | 1.4142135623730951 | 0.0000000000011276535261092282 |                                  
|    6 |  1.414213562373095 |         1.1102230246251564e-16 |                                  
+------+--------------------+--------------------------------+

第 \(k=6\) 反復にて収束判定条件を満たし， \(\sqrt{2}\) の近似値 \(1.414213562373095\) が得られていることがわかります．

公式としてまとめると以下のようになります．

\[ \begin{aligned} &\verb|WITH RECURSIVE Newton (k, x, err, converged) AS (|\\ &\verb| SELECT|\\ &\verb| 0, CAST(x0 AS DOUBLE), CAST(NULL AS DOUBLE), FALSE|\\ &\verb| FROM|\\ &\verb| Config|\\ &\verb| UNION ALL|\\ &\verb| SELECT|\\ &\hspace{20pt}\verb|k + 1|,\\ &\hspace{20pt}\mathtt{x} - f(\mathtt{x})/f'(\mathtt{x}),\\ &\hspace{20pt}|f(\mathtt{x})/f'(\mathtt{x})|/|\mathtt{x}|,\\ &\hspace{20pt}|f(\mathtt{x})/f'(\mathtt{x})|/|\mathtt{x}|<\verb|theta|\\ &\verb| FROM|\\ &\verb| Newton, Config|\\ &\verb| WHERE|\\ &\verb| k < k_max AND converged = FALSE|\\ &\verb|),|\\ &\verb|Config (x0, theta, k_max) AS (|\\ &\verb| SELECT|\\ &\verb| |x_0, \theta, k_{\mathrm{max}}\\ &\verb|)|\\ &\verb|SELECT|\\ &\ \ \verb| k, x, err|\\ &\verb|FROM|\\ &\verb| Newton;| \end{aligned} \]

反復途中の値は不要で，結果だけ取得したい場合の SQL 文を考えます．収束した時点の x を sqrt2 として取得する SQL 文とその実行結果は以下のとおりです．

WITH RECURSIVE Newton (k, x, err, converged) AS (
  SELECT
    0, CAST(x0 AS DOUBLE), CAST(NULL AS DOUBLE), FALSE
  FROM
    Config
  UNION ALL
  SELECT
    k + 1,
    x - (POWER(x, 2) - 2)/(2*x),
    ABS((POWER(x, 2) - 2)/(2*x)) / ABS(x),
    ABS((POWER(x, 2) - 2)/(2*x)) / ABS(x) < theta
  FROM
    Newton, Config
  WHERE
    converged = FALSE
),
Config (x0, theta, k_max) AS (
  SELECT
    1, 1.0e-15, 100
)
-- ここまでは同じ．
SELECT
  x AS sqrt2
FROM
  Newton, Config
WHERE
  err < theta;
+-------------------+
| sqrt2             |                                                                           
+-------------------+                                                                           
| 1.414213562373095 |                                                                           
+-------------------+

\(\sqrt{2}\) の近似値 \(1.414213562373095\) だけが得られました．

まとめ #

本ページではまず，MariaDB のドキュメントを参考に，SELECT や WITH で何ができるのかを確認しました．次に，WITH RECURSIVE というキーワードで再帰処理ができることを確認しました．最後にこれらを組み合わせて，方程式 \(x^2-2=0\) の正の解を Newton 法で計算することで \(\sqrt{2}\) を求めました．

冒頭でお断りしたとおり，本ノートの作成者は，データベースの初心者です．より標準的な記法で実現する方法や，その他の数値計算を MariaDB で実行するための方法の検討は今後の課題とします．

参考文献 #

[1] MariaDB Foundation, “MariaDB Foundation - MariaDB.org”, https://mariadb.org/, 2025/3/23 最終アクセス．

以下本ページのURLリンクは同リンク先のページを参照しています． ↩︎