情報科学研究科Graduate School of Computer and Information Sciences
COT500K1（計算基盤 / Computing technologies 500）データベースプログラミング言語Database Programming Languages
日高 宗一郎Soichiro HIDAKA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学研究科Graduate School of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | TZ010 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 木4/Thu.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This course overviews programming languages suitable for data-intensive processing, such as query processing of database systems, along with their theoretical background, implementations and research trends.
Algebraic properties of primitive data and their collections are exploited to uniformly represent data processing that might seem different using constructs such as monoid homomorphism, which also opens various optimization opportunities through systematic program transformations.
We also deal with graphs as natural extensions to trees, along with transformations and their implementations by structural recursions.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
データベースに対する問い合わせ処理等を記述するプログラミング言語について、理論的背景や実装、研究動向を概観する。
到達目標Goal
データベースに対する問い合わせ処理等を記述するプログラミング言語について、基本データやその集まりに関する代数的性質を利用した統一的な扱い等の意義、意味論などの形式的な扱いに関す理解、代数的性質を利用した最適化を含む処理系の構造の理解を目標とする。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
データベースに対する問い合わせ処理等を記述するプログラミング言語について、理論的背景や実装、研究動向を概観する。
基本データやその集まりに関する代数的性質を利用し、一見異なるデータ処理をモノイド準同型などの機構で統一的に表現し、系統的なプログラム変換を通した最適化にもつなげる。
また、木の自然な拡張としてのグラフの捉え方と構造再帰によるグラフの変換処理、その実装方法も扱う。
授業で課した課題を取り上げ、授業内で全体に対してフィードバックを行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：序論
データベースプログラミング言語の特徴と意義
2[対面/face to face]：データベースプログラミング言語のための数学的準備
正規表現、オートマトン、内包表記、推論規則など本講義に必要となる基本概念や記法の確認
3[対面/face to face]：モノイド準同型
ブール値からリストまで広範囲にわたるデータとその操作を特徴付ける代数的構造を学ぶ
4[対面/face to face]：データベースプログラミング言語における型
モノイド準同型およびモノイド内包表記などの型付けの推論規則による表現を学ぶ
5[対面/face to face]：データベースプログラミング言語における型
対象とするデータを木やグラフに広げ、それらの型としての木スキーマとグラフスキーマの例について学ぶ
6[対面/face to face]：木オートマトン(1)
文字列に対するオートマトンの木への自然な拡張としての木オートマトンの基本定義とスキーマからの生成
7[対面/face to face]：木オートマトン(2)
木オートマトンが受理する言語のブール演算に対応する木オートマトン上の演算などの基本操作と性質
8[対面/face to face]：木オートマトン(3)
木オートマトンによる木のパターンマッチング
9[対面/face to face]：グラフデータモデル
木の自然な拡張としてのグラフの捉え方、グラフをボトムアップに構築する基本演算子であるデータコンストラクタとそれによる任意のグラフの表現の可能性
10[対面/face to face]：グラフデータモデル
二つのグラフが同じかどうかの定義の一つである値等価性とそれを判定する決定手続き
11[対面/face to face]：構造再帰(1)
グラフの枝を繰り返し辿る操作としての構造再帰と、それによるグラフの変換
12[対面/face to face]：構造再帰(2)
異なる構造再帰関数がお互いを呼び合う相互構造再帰とそれを単一再帰への変換する組化、構造再帰による結合(Join)処理の表現
13[対面/face to face]：構造再帰(3)
経路の正規表現によるグラフ問い合わせとオートマトン
14[対面/face to face]：データベースプログラミング言語の実装およびまとめ
データベースプログラミング言語の実装法について、講義で取り上げたグラフ変換言語の実装例を紹介し、部分的な実装に取り組む
講義全体の総括を行う
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
参考文献等の予習、授業内に出される小課題やレポート課題に取り組む。
本授業の準備・復習等の授業時間外学習は、各週につき4時間を標準とする。
テキスト（教科書）Textbooks
なし。
参考書References
Leonidas Fegaras and David Maier. Optimizing object queries using an effective calculus. ACM Transactions on Database Systems Volume 25, Issue 4 , pp.457-516, December 2000
Peter Buneman, Mary Fernandez, Dan Suciu. UnQL: a query language and algebra for semistructured data based on structural recursion, The International Journal on Very Large Data Bases, Volume 9, Number 1, pp.76--110, March 2000
Haruo Hosoya, "Foundations of XML Processing -- The Tree-Automata Approach," Cambridge University Press, 2010年11月
五十嵐淳「プログラミング言語の基礎概念」サイエンス社 2011年07月
Benjamin C. Pierce 著／住井英二郎 監訳「型システム入門 プログラミング言語と型の理論」オーム社 2013年3月
成績評価の方法と基準Grading criteria
最終レポート(40%)および、小課題とその授業内での発表、質疑、討論による上記目標の達成度の確認(60%)により総合的に判断する。ただし、最終レポートの提出は必須であり、提出がない場合はE判定とする。
学生の意見等からの気づきChanges following student comments
サンプルプログラムの紹介などを通して講義で扱う概念の具体的なイメージを掴みやすくする。
理解を深めるための小課題を増やす。
学生が準備すべき機器他Equipment student needs to prepare
Web上の資料の参照や演習に用いるコンピュータ