第8章データ管理

Physical Design物理設計

Attributing logical concepts to physical constructs is called physical database design. The input to the physical design step is a logical representation of the system. It is a joint responsibility of the database designer and DBA. The main responsibility of the physical design is optimizing performance while ensuring data integrity. The main issues addressed in physical design are storage media, file structures, and indexes. The database is stored on a disk using a “standard” file system, not one “tailored” to the database. The database runs on an unmodified general-purpose operating system.

英語のヒント

論理的な概念を、物理的な構成へ割り当てることを、データベースの物理設計という。物理設計の段階への入力は、システムの論理的な表現である。データベース設計者とDBAが、共同で責任を負う。物理設計の主な責任は、データの整合性を保ちながら、性能を最適化することである。主な検討事項は、記憶媒体、ファイル構造、索引である。データベースは、専用に「仕立てた」ものではなく、「標準的な」ファイルシステムを使ってディスクに保存される。変更を加えていない汎用のオペレーティングシステム上で動作する。

Disk Storage and Basic File Structuresディスク格納と基本的なファイル構造

Database tables are stored in disk storage—which is the memory device that stores the data—such as hard disks, flash memory, magnetic disks, optical disks, and tapes as shown in Figure 8.9. The records in the tables could be of fixed length, which means the records are exactly the same length, or variable length, which means the records differ in their length. All records are classified into blocks, and the length of the record can exceed the size of a block, which is called a spanned record. Assume that each relation is stored as a file and each tuple is a record in the file. The files could be ordered (i.e., the records are sequenced on some field) or unordered (i.e., the records are not in any order). The average record access time is the average time taken for a system to access the record. A redundant array of inexpensive disks (RAID) stores information across an array of low-cost hard disks.

英語のヒント

データベースの表は、図8.9に示すハードディスク、フラッシュメモリ、磁気ディスク、光ディスク、テープなどの、データを保存する記憶装置であるディスク記憶に格納される。表のレコードは、すべてがまったく同じ長さの固定長の場合も、長さが異なる可変長の場合もある。すべてのレコードはブロックに分けられ、レコードの長さが一つのブロックの大きさを超えることもある。そのようなレコードを、ブロックをまたぐレコードという。各関係は一つのファイルとして保存され、各タプルはそのファイル内の一つのレコードだとしよう。ファイルは、整列されている場合、つまりあるフィールドに従ってレコードが並ぶ場合と、整列されていない場合、つまりレコードに順序がない場合がある。平均レコードアクセス時間は、システムがレコードへアクセスするのにかかる平均時間である。安価なディスクの冗長配列（RAID）は、低価格のハードディスクの配列にまたがって情報を保存する。

Figure 8.9 This storage hierarchy includes primary and secondary storage. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図8.9 この記憶階層には、主記憶と補助記憶が含まれる。（出典：著作権 Rice University、OpenStax、CC BY 4.0ライセンス）

Physical File Organization and Indexing物理的なファイル編成と索引付け

File organization and indexing are used to minimize the number of block accesses for frequent queries. There are many types of file organization, with the most popular being sequential, relative, and indexed organization. In a sequential file organization, records are organized in the order they are stored and any new record is added at the end. In a relative organization, each record is assigned a numeric key to rearrange the order of the records at any time. Similar to the relative organization, indexed organization uses a key, but the key is unique and fixed. In addition, there are many other file organization types such as heap, hash, B+, and cluster file organization. A heap in file organization refers to an unordered collection of records where new records are placed wherever there is free space, and no particular ordering is enforced. Figure 8.10 shows an example of a heap file organization.

英語のヒント

ファイル編成と索引付けは、よく行う問い合わせに必要なブロックアクセスの回数を最小限にするために使う。ファイル編成には多くの種類があり、特によく使われるのが、順編成、相対編成、索引編成である。順編成では、レコードを格納した順序に並べ、新しいレコードは末尾へ加える。相対編成では、各レコードに数値のキーを割り当て、いつでも順序を並べ替えられるようにする。索引編成も、相対編成と同様にキーを使うが、そのキーは一意で固定されている。ほかにも、ヒープ、ハッシュ、B+、クラスターなど、多くのファイル編成がある。ファイル編成におけるヒープは、順序を持たないレコードの集まりであり、新しいレコードは空き領域のある場所へ置かれ、特定の順序は強制されない。図8.10に、ヒープファイル編成の例を示す。

Figure 8.10 This heap file organization example shows how to insert a new record (record 4) into the data blocks in the memory. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図8.10 このヒープファイル編成の例は、メモリ内のデータブロックへ、新しいレコード（レコード4）を挿入する方法を示している。（出典：著作権 Rice University、OpenStax、CC BY 4.0ライセンス）

Physical Database Organizationデータベースの物理的な編成

A tablespace is where tables are stored physically in the memory (i.e., the physical container of database objects). The use of tablespaces has an impact on physical database design concerning intraquery parallelism, where different subsets of data can be searched in parallel for a complex query, and interquery parallelism (i.e., many simple queries executed in parallel).

英語のヒント

表領域は、表がメモリ内に物理的に格納される場所、すなわちデータベースオブジェクトの物理的な入れ物である。表領域の利用は、問い合わせ内並列性と問い合わせ間並列性に関する、データベースの物理設計に影響する。問い合わせ内並列性では、複雑な一つの問い合わせのために、データの異なる部分集合を並列に検索できる。問い合わせ間並列性とは、多数の単純な問い合わせを並列に実行することである。

Query Execution Concepts問い合わせ実行の概念

Processing the query includes five steps:

問い合わせの処理には、五つの段階がある。

1. parsing: checking the syntax of the query, user’s privileges, table, and attribute names

1. 解析：問い合わせの構文、利用者の権限、表名、属性名を確認する。

2. translation: translating from high-level language to machine language

2. 翻訳：高水準言語から機械語へ翻訳する。

3. optimizer: selecting the best plan to execute

3. 最適化器：実行する最適な計画を選ぶ。

4. execution: running the selected plan

4. 実行：選んだ計画を動かす。

5. evaluation: returning the query result

5. 評価：問い合わせ結果を返す。

The query optimizer determines the lowest cost strategy for query execution using the internal representations of a query (i.e., query tree and query graph). The mathematical technique for processing the query quickly is called heuristics optimization. The main heuristic is to first apply the operations that reduce the size of intermediate results.

英語のヒント

問い合わせ最適化器は、問い合わせの内部表現、すなわち問い合わせ木と問い合わせグラフを使い、最も費用の小さい実行戦略を決める。問い合わせを速く処理する数学的な手法を、ヒューリスティック最適化という。主な経験則は、中間結果の大きさを減らす操作を、先に適用することである。

Physical Database Design and Tuningデータベースの物理設計と調整

Assume you are looking for a specific record in a huge database and that the record you are looking for is at the end. To retrieve that record, the system moves sequentially record by record and takes a long time to process. Let us follow this SQL exercise using Table 8.9.

英語のヒント

膨大なデータベースから特定のレコードを探しており、そのレコードが末尾にあるとしよう。システムが、そのレコードを取り出すために一つずつ順に調べると、長い処理時間がかかる。表8.9を使い、次のSQLの演習を進めよう。

Employee Employee（従業員）
Number Number（番号）	FName FName（名）	LName LName（姓）	Country Country（国）
1	Sam	Smith	USA
2	Adam	Bell	UK
3	Matt	John	USA
4	John	Zack	USA
5	Andy	Dave	UK

Table 8.9 Employee Table

表8.9 従業員表

We are looking for “Andy” using the following SQL statement:

次のSQL文を使って、「Andy」を探す。

SELECT * FROM employee WHERE Fname = 'Andy';

Looking for Andy takes five comparisons because Andy is at the end of the table. However, if we sort the data alphabetically (Table 8.10), searching for a name happens faster (two comparisons).

英語のヒント

Andyは表の末尾にいるため、探すには5回の比較が必要である。しかし、データをアルファベット順に並べ替えれば（表8.10）、名前をより速く、2回の比較で探せる。

Employee_sort Employee_sort（従業員の並べ替え）
FName FName（名）	LName LName（姓）	Index Index（索引）
Adam	Bell	2
Andy	Dave	5
John	Zack	4
Matt	John	3
Sam	Smith	1

Table 8.10 Employee Sort Table

表8.10 従業員の並べ替え表

An index holds the field being sorted and points from each record to the corresponding record where the data are stored (Figure 8.11).

英語のヒント

索引は、並べ替えの対象となるフィールドを保持し、各レコードから、データが格納されている対応するレコードを指す（図8.11）。

Figure 8.11 Using indexing can improve the query performance. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図8.11 索引付けを使うと、問い合わせの性能を改善できる。（出典：著作権 Rice University、OpenStax、CC BY 4.0ライセンス）

Indexing helps improve the performance of the query process. Creating an index in SQL retrieves data from the database more quickly. The following are SQL syntaxes for creating an index and creating a unique index. Note that a UNIQUE refers to an index where all rows of the index must be unique. That is, a row may not have identical non-null values for all columns in this index as another row.

英語のヒント

索引付けは、問い合わせ処理の性能向上に役立つ。SQLで索引を作ると、データベースからデータをより速く取り出せる。以下は、索引と一意索引を作成するSQLの構文である。UNIQUEは、索引のすべての行が一意でなければならない索引を指すことに注意しよう。つまり、ある行の、この索引に含まれるすべての列の非ヌル値が、別の行の値とすべて同じであってはならない。

CREATE INDEX index_name ON table_name (column1, ...);
CREATE UNIQUE INDEX index_name ON table_name (column1, ...);

In addition, you can delete the index anytime using the drop statement:

また、drop文を使い、いつでも索引を削除できる。

DROP INDEX index_name ON table_name;

A key is needed to index an attribute; however, an index can be constructed with one or multiple attributes. If a table requires more than one index, we need to decide which attribute we cluster. In general cases, the indexing is implemented using binary tree, B-tree, or B+ tree. In practice, B+ trees are more commonly used in database systems. Binary tree is a tree in which every node has up to two children. B-tree generalizes the binary tree with more than two children and may have one child. B+ tree is a tree with a large number of children per node but in some cases it is more efficient to use hash indexing (e.g., equality conditions). The normalized database is the database with eliminating data redundancy to enhance the data integrity in the table. Denormalization is a strategy to increase the performance of a normalized database. It adds redundant data such as extra attributes, adds new tables, or creates instances. The main goal is to decrease the running time of queries by making data more accessible.

英語のヒント

属性に索引を付けるには、キーが必要である。ただし、索引は一つの属性でも、複数の属性でも構成できる。表に複数の索引が必要なら、どの属性でクラスター化するかを決める必要がある。一般に、索引付けは二分木、B木、B+木を使って実装する。実際のデータベースシステムでは、B+木がよりよく使われる。二分木は、どの節点も子を最大二つ持つ木である。B木は、二つより多い子を持てるように二分木を一般化したもので、一つの子だけを持つ場合もある。B+木は、各節点に多くの子を持つ木である。ただし、等値条件などの場合には、ハッシュ索引のほうが効率的なことがある。正規化されたデータベースは、表のデータ整合性を高めるために、データの冗長性を取り除いたものである。非正規化は、正規化されたデータベースの性能を高める戦略である。追加の属性などの冗長なデータを加えたり、新しい表を加えたり、インスタンスを作ったりする。主な目標は、データにアクセスしやすくして、問い合わせの実行時間を減らすことである。