順序付き線形型に基づく安全かつ高速な大規模データ処理の実現

基于有序线性类型实现安全快速的大规模数据处理

基本信息

批准号：
19024003
负责人：
小林直樹
金额：
$ 3.9万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2008
项目状态：
已结题

项目摘要

XMLのような木構造を論理構造として持つテキストデータの処理の記述方式としては, その論理的構造に基づいて木構造処理として記述する方式と, 1次元のテキストデータとしての物理構造に即したストリーム処理として記述する方式がある. 本研究では,両者の長所をあわせもつ方式として、ユーザには木構造処理のプログラムを記述させ, それをストリーム処理プログラムに自動変換する方式について研究を進めている.本年度の成果は以下のとおり。1. XML用のストリーム処理プログラム生成器X-Pの有効性の評価昨年度までに順序付線形型に基づくXML用のストリーム処理プログラム生成器X-Pの有効性の評価を行った. その結果, 不要なバッファリングが挿入されるケースがいくつか見つかった.2. 順序付き非線型型を用いた一時的バッファリング従来の変換の枠組みは, (1)木構造処理プログラムPにバッファリングを挿入することにより, 入力木に左から順に一度だけアクセスする中間プログラムIに変換し, (2)I中の木構造処理のための各命令をストリーム処理命令に置換えてストリーム処理プログラムTを得る, という2つの変換から構成されていた. (1)の変換では, Iが順序付線形型システムで型付けされるようにソースプログラムPにバッファリングを挿入することによって実現されていた.上記1の評価で浮上した不要なバッファリングの問題は, バッファリング命令がストリームから無制限にアクセスできるメモリへのコピー命令の一種類のみであったことが主要な原因の一つであった. この問題を解決するため, 順序付き非線形型を導入することによって一時的バッファリングを実現し, 既存の木構造処理プログラムからストリーム処理プログラムへの変換の枠組みを改良した. これにより, 不要なバッファリングの問題を改善できることを実験により確認した.

用于将具有树结构的文本数据的处理描述为逻辑结构（例如XML）的方法有两种：一种将处理描述为基于逻辑结构的树结构的方法；以及一种将处理描述为文本的方法。数据作为基于逻辑结构的树结构，以及将具有树结构的文本数据的处理描述为逻辑结构的方法在本研究中，我们正在研究一种将过程描述为过程的方法。通过让用户编写树结构处理程序并自动将其转换为流处理程序，结合了两种方法的优点的方法今年的结果如下。 1. XML 流处理程序生成器 X-P 的有效性评估直到去年，我们才评估基于有序线性类型的 XML 流处理程序生成器 X-P 的有效性，结果是不必要的缓冲 2. 使用有序非线性的临时缓冲。 types 常规的转换框架为： (1) 通过在树形结构处理程序P中插入缓冲，由两次变换而来：（1）转换为从左侧仅访问输入树一次的中间程序I，（2）将I中每条用于树结构处理的指令替换为流处理指令，得到流处理程序T。 (1) 中的转换是通过在源程序 P 中插入缓冲来实现的，这样我就可以使用有序线性类型系统进行输入。缓冲问题是。主要原因之一是缓冲指令只是一种可以从流中无限制访问的内存复制指令。为了解决这个问题，我们引入了有序非线性类型，我们实现了临时缓冲并改进了框架。将现有的树结构处理程序转换为流处理程序，我们通过实验证实这可以改善不必要的缓冲问题。