論文

DBSJ Letters Vol.4, No.1

Web サービスにおけるトランザクションの隔離性
Isolation Property of Web Service Composition Transactions
徐 海燕☆

Haiyan XU
Yihua SHI

古川 哲也☆☆

史 一華☆☆☆

Web services have quickly become a very important technology for enterprise system development
and it has become possible to build distributed systems using web services as components. This paper
discusses the isolation property of web service composition transactions. By discussing the data interaction between diﬀerent instances, we propose a condition to guarantee the isolation property in web service composition transactions, which is weaker thanthe conventional serializablity property. The mechanism for the isolation is also discussed.

1. は じ め に
ビジネス取引の自動化を目指すために、Web サービスについての研究が盛んに行われている。複数の Web サービスをインターネット上で統合して新たな Web サービスを定義するために、
BPEL4WS (Business Process Execution Language for WebServices) が発表された1) 。複合 Web サービスの設計と分析に際しては、どのような複合 Web サービスは正しく動くのか、どのように Web サービスの実行の正しさを保証すればよいのか、などのように、多くの課題が残されている4) 。本論文では、Webサービスの密結合によって企業内の情報システムを組み立てる際に必要となるトランザクションの隔離性の管理について検討し、一般的な疎結合の場合まで触れる。
密結合による企業内の情報システムにおいて、複数のインスタンスが同時に実行されるとき、トランザクションの隔離性の管理が必要となる場合がある。
例 1 融資の申込みを処理するプロセスが図 1 のように構築☆☆

正会員 福岡工業大学情報工学部情報工学科
xu@cs.fit.ac.jp

正会員 九州大学大学院経済学研究院
furukawa@en.kyushu-u.ac.jp☆☆☆
正会員 西南学院大学商学部
shi@seinan-gu.ac.jp

1

process/flow

Tetsuya FURUKAWA

Web サービスの普及に伴って、インターネット上で公開された様々な Web サービスを構成部品として利用し、企業の情報システムを組み立てるという時代が到来する。このため、複合Web サービスのトランザクションが並行実行時に互いに与えうる影響について検討する必要がある。本論文では、複合 Web
サービスに従って単独で実行された各トランザクションが満たさなければならない性質を一貫性、並行実行時に同じ性質を満たすための性質を隔離性と定義し、隔離性を保証するための ACID属性よりも緩められた条件を提案する。また、BPEL4WS のようなフローエンジンが他のサービスを呼び出す場合における隔離性の実現法について検討する。

☆

されているとする。顧客の融資申込みを受け付け、その顧客に関する収入／財産／ローンなどの経済状況をデータベースから検索し、金融機関の Web サービスであるローン審査を呼び出してその顧客の融資へのリスクを判断する。融資のリスクが低いと判断された場合は、融資を承認し、ローンの貸出しを行う。それ以外の場合は、融資ができない旨の返信を行う。しかし、ある顧客が複数件の融資申請を同時に行った場合、貸出しできないロー
ンを融資してしまう場合が生じうる。

情報検索
a3

ローン
発行

receivea1

invokea2

ローン
審査

invoke

審査結果=”yes”

審査結果=”no”

invoke

a4
reply

a５

図 1 融資申込みプロセス
Fig. 1 A loan approval process

従来のトランザクション管理は、原子性（Atomicity）、一貫性（Consistency）、隔離性（Isolation）、耐久性（Durability）によって表される ACID 属性に基づいている2) 。しかし、このACID 属性は Web サービスのような疎結合や密結合がある結合環境においては、柔軟性に欠け、制限が多すぎるという問題が広く認識されている5) 。このため、標準化組織 OASIS による Business Transaction Processing (BTP) や、BEA、IBM、Microsoft による WS-Transaction とその付属仕様である WSCoordination が公開されている3),6) 。BTP は疎結合システムへの適用を前提としており、WS-Transaction は密結合用の ACIDトランザクションと疎結合のための長大トランザクションの両者をサポートしている。これらの仕様に共通しているのは、全て実行されるかまったく実行されないかという後退復帰方式ではなく、ビジネスロジックに合わせた個々の例外処理を行う補償方式を使用することである。しかし、Web サービスの連携によって企業内の情報システムを組み立てるという密結合の場合においても厳密な議論はなされておらず、ACID 属性が必ずしも適しているとは限らない。
従来の企業におけるワークフローシステムにおいて、トランザクションの隔離性が内部設計によって実現されている場合が多い。しかし、インターネット上で公開している Web サービスを利用する場合に入手できるのはインタフェースに関する情報のみで、内部ロジックに頼ることは現実的でない。本論文では、
Web サービスにおける基本的な操作単位であるアクティビティの入出力データの種類について分析し、トランザクションにおける一貫性上で関連するデータ項目の集合を明確にする。それに基づいて Web サービストランザクションにおける隔離性は ACID属性よりも緩められることを示す。
本論文は、次のように構成される。2 節で Web サービスとその連携であるフローモデルを定義し、3 節では密結合と疎結合の場合に分けて、Web サービスのトランザクションの隔離性の正当性基準について検討する。4 節では BPEL4WS エンジンのようなフローエンジンとデータベースの連携による隔離性の実

日本データベース学会 Letters Vol.4, No.1

論文
現方法を、施錠方式の立場から提案する。5 節は全体のまとめである。

2. Web サービスモデル
Web サービスは XML フォーマットのメッセージデータを交換する。使用されるメッセージのデータフォーマットや、メッセージの処理ルールは、通信規約 SOAP によって定められている。
Web サービスのインタフェースは、WSDL によって記述される。
複数の Web サービスを連携して新たな複合 Web サービスを作成する際は、パートナーによって提供される Web サービスを呼び出す < invoke >、パートナーからのメッセージを受け取る< receive >、パートナーへメッセージを送信する < reply >、大域変数の引き渡しを行う < assign > が基本的なアクティビティになる。
個々の基本的なアクティビティのインタフェースを定義する
WSDL には、名前、パートナー、ポートタイプ、操作、入出力データといったパラメータについての記述が含まれている。本論
文では、基本的なアクティビティa を a(I, O, p) として抽象化して記述する。ここで、I は a によって検索される大域変数、O は aによって値が代入される大域変数である。例えば、基本的なアクティビティでは、< receive > は出力データのみを、< reply >は入力データのみを持つ。< invoke > と < assign > は入力データと出力データの両方を含む。また、p は a のパートナーを記述しているが、パートナーが重要でない場合は省略する。
I と O の和集合をアクティビティa(I, O, p) の操作データ集合という。実際の場合には、利用される Web サービスによってインタフェースの粒度が異なってくる。一般的に企業内ではメッセージが必要なビジネス情報を全て含むような粒度の細かいインタフェース、外部利用者に対してはキーワード情報しか含まない粒度の粗いインタフェースが使われている。本論文では、企業内の連携においては、必要とする全ての入出力情報をインタフェースに含むとする。
例 2 図 1 には、a1 , a2 , a3 , a4 , a5 の 5 つの基本的なアクティビティがある。それらの記述を次に示す。
• 申請受付 a1 :I1 = φ,O1 ={ 顧客 ID:x1 , 申請額:x2 },• 情報検索 a2 :I2 ={ 顧客 ID:x1 },O2 = { 経済状況:x3 },• 審査 a3 :I3 ={ 顧客 ID:x1 , 申請額:x2 , 経済状況:x3 },O3 = { 審査結果:x4 },• ローン発行 a4 :I4 ={ 顧客 ID:x1 , 申請額:x2 },O4 ={ 経済状況:x3 }• 結果返信 a5 :I5 ={ 顧客 ID:x1 , 審査結果:x4 },O5 = φ.
すなわち、a1 では顧客の申請を受け付け、顧客 ID や申請額を大域変数に代入している。a2 では企業データベースに記憶されている申請者の経済状況に関する情報を、a1 で代入された大域変数 x1 をキーワード にして検索し、その結果を大域変数 x3 に代入している。それらによって得られた情報に基づいて、申請者に対する審査を a3 によって行う。a4 で申請額のローンを発行するが、申請者の経済状況にも今回のローンの発行を反映する。
a5 では顧客への審査結果の返信を行う。

各節点の作業によってデータベースに対しても検索や変更が

2

DBSJ Letters Vol.4, No.1
なされているので、IDB と ODB でそれぞれ各節点によって検索と変更がなされたデータベースの項目を表すとする。例 2 においてデータベースに対する入出力データは次のようになる。
I2DB ={ 顧客 ID:x1 , 経済状況:x3 }I4DB ={ 顧客 ID:x1 }O4DB ={ 経済状況:x3 }データベースからの入力データとデータベースへの出力デー
タに関する情報は、アクティビティのインタフェースからは得られない。本論文では、データベースレベルでの介入によってそれらの情報を入手する方法を導入する。
一方、基本的なアクティビティ間の実行順序は、制御フローによって記述する。BPEL4WS では < sequence >, < f low > な
どの構造化されたアクティビティによって、基本的なアクティビティのインスタンス間の実行順序を定義している（図 1）。
制御フローに従う実行であるトランザクションを記述するた
めに、データ項目 x およびデータ項目集合 X のインスタンス
を Ix および IX とし、A(II , IO , p) で基本的なアクティビティa(I, O, p) の実行を記述する。トランザクションは、基本的なアクティビティの実行を表す節点と分岐節点／結合節点からなる節点集合と、それらの間の実行順序を表す枝集合からなる有向グラ
フ W T (T N, T E) である。分岐節点に対しては分岐枝は 1 つしか存在せず、真となる経路条件に関わるデータ項目とその値が、分岐節点の出力データとそのインスタンス IO となる。トランザ
クション W T (T N, T E) は、有向非巡回グラフである。これは、複数回実行される基本的なアクティビティは異なる節点に展開され、条件分岐は特定の経路のタスクに従って実行されるためである。
トランザクション W T (T N, T E) におけるデータの流れは、通常データフローと呼ばれる有向グラフ DT (T N, DE) によって記述される。節点 Ai が W T (T N, T E) において祖先である Ajの出力データを入力データとして利用するなら、データフローDT (T N, DE) に Aj から Ai への枝がある。分岐節点に対しては、真となる経路条件に関わるデータ項目によって分岐節点から分岐経路上の節点への枝が存在するとする。すなわち、データフロー DT (T N, DE) 中の枝はトランザクション W T (T N, T E)の枝の推移的閉包に含まれる (DE ⊆ T E ∗ )。
異なるトランザクションが同時に実行される場合に、スケジュールが生成される。W Ti (T Ni , T Ei ) (i = 1, 2, · · ·) からなるスケジュールは、次のような有向非巡回グラフ W H(HN, HE) である。

• HN = i T Ni , HE ⊇ i T Ei ,• 異 な るト ラ ンザ ク ション の 節点 As と At が 競 合す る（(OsDB ∩(ItDB ∪OtDB ) = φ) ∨(OtDB ∩(IsDB ∪OsDB ) =φ)）なら、 それらの間の実行順序を示す枝か推移的な枝がHE に含まれる。
例 3 図 2 は例 1 の Web サービスに従う実行である W T1と W T2 からなるスケジュール W H1 を示している。一方、
W T1 (T N1 , T E1 ) におけるデータフロー DT1 (T N1 , DE1 ) には、
A12 (A13 , A14 , A15 ) の入力データ x1 は A11 の出力データを利用しているので、枝 (A11 , A12 )((A11 , A13 ), (A11 , A14 ), (A11 , A15 )) を含む。同じように、A13 の入力データ x3 は A12 の出力データを利用しているので、枝 (A12 , A13 ) が存在する。一方、A13 の出力デー
タ x4 は、経路条件にも A15 の入力データにも利用されたので、
枝 (A13 , A14 ) と (A13 , A15 ) が存在する。

3. 隔 離 性
本節では、トランザクションの隔離性を、密結合と疎結合の二つの場合に分けて検討する。

日本データベース学会 Letters Vol.4, No.1

論文

DBSJ Letters Vol.4, No.1

WT2

WT1

A

11

A2

A

3

1

1

receiveA

1

invokeA

2

invokeA

3

審査結果
invoke A
1
5receive2

invoke2

invoke

審査結果=”yes”

A2

1
4

reply

=”yes”

invokeA

A

reply

2524

図 2 スケジュール W H1Fig. 2 Schedule W H1

3.1 密結合の場合における隔離性
複合 Web サービスに従う実行であるトランザクションが、複数個同時に実行されるときに単独実行と同様に正当な実行でなければならない。本節では、単独実行時に各トランザクションが満たさなければならない性質を一貫性として形式的に定義し、並行実行時に同じ性質を満たすようにするための隔離性について検討する。
節点の集合であるトランザクションの一貫性は、各節点の一貫性と節点間の一貫性に分けられる。
• 各節点の一貫性は、それぞれの節点の入出力データ間の一貫性を意味する。
• 節点間の一貫性は、各節点とトランザクションのこれまでの実行環境との対応を表す。
基本的なアクティビティは入力データに対して正しく出力データを生成できると仮定するので、原子性の単位となる基本的なアクティビティの実行である節点は、入出力データ間の一貫性を満たす。節点間の一貫性を分析するためには、各節点の作業によってデータベースに対して検索や変更がなされていることを考慮する必要がある。大域変数は並行実行の影響を受けないが、データベースに対する入出力データは例 1 で示したように並行実行の影響を受ける。したがって、大域変数からの入力の場合も、データフローの親の実行環境が並行実行時に受ける影響を再帰的に考慮する必要がある。また、分岐節点は分岐経路上の各節点のデータフロー上の親となるため、分岐条件に使われるデータ項目のデータフロー上の親の実行環境が受けた影響も考慮する必要がある。このため、トランザクションの一貫性は次のように表せる。
定義 1 入出力データの一貫性を満たす個々の節点からなるトランザクションは、トランザクションが単独で実行する場合に各節点が実行されるときにデータフローの祖先節点のデータベースに対する入出力データ間で成り立っている性質を満たしてい
るならば、一貫性を満たしている。
並行実行において、各々のトランザクションの節点の大域変数が、他のトランザクションの実行によって変更されることはない。このため、トランザクションの一貫性にそのような入力データとの一貫性を含めていない。一方、W H1 で示しているように、データベースに対する入出力データはトランザクションの実行中に他のトランザクションによって変更されることによって一貫性上で問題が生じうる。隔離性は、そのような問題に対処するための性質である。

3定義 2 単独実行において一貫性を満たすトランザクション
W Ti (i = 1, · · · , n) からなるスケジュール W H(HN, HE) において、一貫性を満たさないトランザクションが存在しなければ、各々のトランザクションは隔離性を満たす。
W H1 で示したように、W T2 によって操作されたデータ項目が他のトランザクションによって変更されたため問題が生じた。
このため、問題を引き起こしうるすべての変更を禁止することで対処する。
定義 3 トランザクション W Ti (i = 1, · · · , n) からなるスケ
ジュール W H(HN, HE) において、各々のトランザクションに対して、データベースに対する入出力データが操作されてからデータフローの子孫節点が全て終了するまで他のトランザクションによって変更されていなければ、各々のトランザクションは論
理性を満たす。
例えば、スケジュール W H1 においては、A22 のデータベースに対する入出力データ x3 が、A24 が終了するまで W T1 中の節
点 A14 によって変更されている。このため、W T2 は論理性を満たさない。
トランザクション W Ti (i = 1, · · · , n) からなる 2 つのスケ
ジュール W H と W H  で、各トランザクションの実行と最終結果がそれぞれ同じであれば、W H と W H  は等価であるという2) 。従来では、直列実行と等価なものを直列可能スケジュールといい、直列可能性を隔離性の基準としてきた。入出力データの一貫性を満たす個々の節点からなる Web サービストランザク
ションに対して、隔離性の基準は次のようになる。
定理 1 単独実行において一貫性を満たすトランザクション
W Ti (i = 1, · · · , n) からなるスケジュール W H(HN, HE) において、W H と等価で各 W Tj (j ∈ {1, 2, · · · , n}) が論理性を満たすスケジュール W H  が存在すれば、各 W Tj は一貫性を満たす。
証明： トランザクション W Tj (T Nj , T Ej ) が一貫性を満たさないとすると、定義 1 より節点間の一貫性を満たさない節点 Aが存在することになる。すなわち、A が実行されるときにデータフローの祖先節点のデータベースに対する入出力データはデータベースの一貫性を満たさない。A のデータフローの祖先節点のデータベースに対する入出力データを DB  とすると、単独実行
時に W T は一貫性を満たすため、W T によって操作された DB 
中のデータ項目は A が実行されるまで他のトランザクションによって変更されたことになる。しかし、これは各トランザクショ
ン W Tj (j ∈ {1, 2, · · · , n}) は W H  において論理性を満たすことと矛盾する。
論理性を満たす等価なスケジュールが存在する基準は直列可能性よりも緩和した基準であり、施錠方式を用いる場合は、専有施錠と共有施錠間の競合を緩和できることが、論文7) によって示されている。また、定理 1 により、各トランザクションが一貫性を満たす単位は、トランザクション単位ではなくデータフローの経路単位でよい。通常トランザクションは複数のデータフローの経路に細分されるため、定理 1 の条件は従来のトランザクション単位での ACID 属性よりも緩和されている。

3.2 疎結合の場合における隔離性
疎結合環境におけるトランザクションは、一般的に複数個の密結合環境のサブトランザクションから構成される。ai (Ii , Oi , pi ) (i =1, 2, · · · , k) を基本的なアクティビティとするフローに対して、集合 P に属する企業間の疎結合環境においては、P 中の要素をパートナーとするアクティビティの入出力メッセージだけが残され、P 以外のパートナー間の入出力データに関する情報は利用できないことになる。例えば、例 1 では、a1 と a5 の入出力データが残されることになる。

日本データベース学会 Letters Vol.4, No.1

論文
一般的に、企業内の情報システムを組み立てるための Web サー
ビスは密結合で連携し、企業間の Web サービスは疎結合で連携する。疎結合におけるトランザクションは複数個の密結合で構成されたサブトランザクションから構成される。
各々のサブトランザクションに関して疎結合環境は、さらに次の二つの場合に分けられる。
( 1 ) 異なる企業のデータベースに共通部分が存在しない場合。
例えば、旅行予約の場合、カード会社、航空会社、ホテルのような個々の共通部分が存在しないデータベースの場合である。
( 2 ) 異なる企業のデータベースは共通するデータを扱っている可能性がある場合。例えば、銀行とローン審査会社のデータベースの場合である。
前者の場合は、異なるトランザクションの異なる企業のデータを扱うサブトランザクション間には競合が存在しない。すなわ
ち、個々の密結合環境におけるサブトランザクションが隔離性を満たせばよい。したがって、本論文の隔離性に関する結果はそのまま疎結合環境におけるサブトランザクションの管理に適用できる。一方、後者の場合は、個々のサブトランザクションや個々のデータベースに関する詳細な情報がない限り、隔離性については従来の ACID 属性に留まることにならざるをえない。

DBSJ Letters Vol.4, No.1フローの子孫節点が全て終了するまでに他のトランザクションによって変更されている。しかし、それは施錠に基づく方式の定義 4 と矛盾する。
5. お わ り に
本論文では、インターネット上で公開している Web サービスを部品として組み立てる時代の到来に備えて、Web サービスの連携によって企業内の情報システムを構築する場合に考慮すべ
き並行処理制御に関する問題について検討を行った。Web サー
ビスに対しては内部ロジックが隠されているため、従来の企業内のワークフローシステムに用いられた内部ロジックによる方法は適用できなくなる。本論文では、Web サービスの連携によって企業内の情報システムを構築する場合のモデルを、疎結合と密結合の場合に分けて与えた。また、密結合のトランザクションに対して、各節点の入出力データを分類することによって、従来の ACID 属性よりも緩和した隔離性を保証するための条件を提案した。さらに、その実現方法は、フローエンジンとデータベースの連携によって行えることを示した。

[謝辞] 本研究の一部は、文部省科学研究費補助金基盤研究(C)15500079 の援助を受けている。

4. 連携エンジンとデータベースによる実現法[文献]

従来のデータベースの並行処理制御方式は、他のトランザクションの問題となる実行を禁止する施錠による保守的な方式から時刻印方式のような楽観的な方式まである。本節では、密結合環境において、BPEL4WS エンジンのようなフローエンジンとデータベースの連携による施錠方式の実現方法について検討する。
各々のトランザクションが論理性を満たすスケジュールのみを生成させる制御方式としては、従来の 2 相施錠方式に対して専有施錠と共有施錠間の競合を緩和した拡張 2 相施錠方式が利用できる7) 。すなわち、すでに専有施錠または共有施錠されたデー
タ項目の他のトランザクションによる専有施錠は禁止されるが、共有施錠は禁止されることなくいつでも施錠できる。本論文のモデルへ適用すると、次のようになる。
定義 4 基本モデルに対する施錠に基づく方式 (Locking protocol) は、次のように施錠と解錠を行う方式である。
• データベース中のデータに対して検索操作／変更操作を行う前に、それぞれ専有施錠／共有施錠を行う。ただし、他のトランザクションによってすでに専有施錠または共有施錠されているデータ項目には再び専有施錠することはできない。
• 大域変数によるデータの引き渡しによって得られるデータフロー情報を活用して、各節点による施錠は、データフロー上の子孫節点がすべて終了するまで保持する。
以降、施錠に基づく方式によって生成されるスケジュールをLP スケジュールという。例えば、スケジュール W H1 において、A12 によって経済状況 x3 に対する共有施錠は A14 まで保持されることになる。同じように A22 によって経済状況 x3 に対する共有施錠も A24 まで保持される。したがって、A14 や A24 による x3に対する専有施錠は禁止されることになり、W H1 は LP スケジュールではない。
定理 2 トランザクション W Ti (i = 1, · · · , n) からなるスケジュール W H(HN, HE) が LP スケジュールならば、各トランザクション W Ti は論理性を満たす。
証明： スケジュール W H(HN, HE) に論理性を満たさないト
ランザクション W Ti が存在するとする。定義 3 よりデータベースに対する入出力データは、W Ti によって操作された後データ[1] Business Process Execution Language for Web Services(BPEL), Version 1.1, http://dev2dev.bea.com/technologies/webservices/BPEL4WS.jsp[2] P. A. Bernstein, V. Hadzilacos and N. Goodman: Concurrency Control and Recovery in Database Systems, AddisonWesley (1987).
[3] Business Transaction Protocol (BTP), http://www.oasisopen.org/committees/ tc home.php?wg abbrev=businesstransaction[4] R. Hull and J. Su: Tools for Design of Composite WebServices, ACM SIGMOD Inter. Conf. on Management ofData, pp. 958-961 (2004) .
[5] M. Little: Transactions and Web services, Communications of the ACM, Vol. 46, No. 10, pp. 49-54 (2003).
[6] Web Services Transaction (WS-Transaction),
http://www-106.ibm.com/developerworks/
webservices/library/ws-transpec/ (August 2002).
[7] 徐海燕，古川哲也，史 一華：並行処理制御方式による独立化可能性クラスと直列可能クラスの比較、情報処理学会論文
誌：Vol. 37, No. 8, pp. 1600-1609 (1996).

4

徐 海燕
Haiyan XU
福岡工業大学情報工学部情報工学科教授。平成 2 年九州大学大学院博士後期課程修了。工学博士。並行処理制御、WEB 型情報システムなどの研究に従事。ACM、IEEE、情報処理学会、電子情報通信学会、日本データベース学会等会員。
Tetsuya FURUKAWA
古川 哲也
九州大学大学院経済学研究院教授。昭和 63 年九州大学大学院博士後期課程修了。工学博士。データベースの設計論・質問処理論、情報システムの研究に従事。情報処理学会、電子情報通信学会、ACM、IEEE、日本 OR 学会等会員。
Yihua SHI
史 一華
西南学院大学商学部教授。平成 4 年年九州大学大学院博士後期課程終了。理学博士。WEB 型教育支援システム、Web サービス、知識ベースシステムなどの研究に従事。電子情報通信学会、人工知能学会、日本データベース学会各会員。

日本データベース学会 Letters Vol.4, No.1