● 2項関係

　集合 A および集合 B のあいだで、直積 A×B の部分集合 R を、A から B への 2項関係 （あるいは、単に、A から B への関係 [ relation ]）といい、R： A → B というふうに記述する。そして、（a, b）∈ R であるとき、a と b は、関係 R にあるといい、aRb とも記述する。
　とくに、A から A 自身への関係を 「A の上の関係」 ともいう。

　
● 恒等関係

　R を A の上の 2項関係とする。R の ベキ 乗を、以下のように定義する。

　（1） R⁰ ＝ id_A ＝ { (a, a) | a ∈ A }.
　（2） Ｒⁿ⁺¹ ＝ Rⁿ・R　　{ n ＝ 0, 1, 2,・・・}.

　id_A を、A の上の恒等関係という。

　
● 同値関係

　R を A の上の 2項関係とする。同値関係は、以下の 3つの性質を満たす 2項関係として定義される。

　（1） 反射律 （aRa）
　（2） 対称律 （aRb → bRa）
　（3） 推移律 （aRb ∧ bRc → aRc）

　
● 全関係、同値関係および恒等関係

　R ＝ A × A は、A上の 2項関係である。これを、A 上の全関係ともいう。
　R は、同値関係であり、A/R ＝ { A } である。
　また、A 上の恒等関係 ｛（a, a）| a ∈ A } は同値関係であり、A/R⁰ ＝｛｛a｝| a ∈ A } である。

　
● 順序 （半順序）

　R を A 上の 2項関係とする。数の大小関係は、以下の 3つを満たす 2項関係である。

　（1） 反射律 （aRa）
　（2） 推移律 （aRb ∧ bRc → aRc）
　（3） 反対称律 （aRb ∧ bRa → a ＝ b）

　反射的、推移的かつ反対称的である 2項関係を、半順序 （partial order） あるいは、単に、順序という。半順序は、「等号付きの不等号 （≦）」 の一般化である。

　
● 擬順序

　R を A 上の半順序とする。
　ｘRｙ において、x ≠ y を、xR’y とする。つまり、反射律が成立しない、とする （したがって、R’＝ R − id_A）。
　xR’y において、以下が成り立つ。

　（1）’ 反-反射律 （aR’a は成立しない）
　（2）’ 推移律 （aR’b ∧ bR’c → aR’c）
　（3）’ 非対称律 （aR’b → bR’a）

　（1）’、（2）’および（3）’を満たす関係 R’を、擬順序という （ただし、R’を半順序といい、R を順序という人もいるので注意されたい）。

　擬順序 R’に対して、xR’y において、x ＝ y であれば、xRy とする、というふうに定義すれば──R ＝ R' ∨ id_A とすれば──、前述した半順序が成立する。つまり、「等号 （＝）」 をふくむかどうかの違いである──半順序は、「≦」 という 「等号付きの不等号」 を使い、擬順序は、「＜」 という不等号を使う。

　
● 半順序集合

　半順序 （≦） として定義された集合のことを、半順序集合といい、（A, ≦） を使って記述する。
　A の メンバー { a, b } に対して、a ≦ b （あるいは、b ≦ a） が成立するとき、a と b は比較可能である、という。任意の 2つの メンバー が比較可能である半順序のことを、全順序 （total order） という （あるいは、線形順序ともいう）。

　集合のあいだに成立する包摂関係 （⊆） は、半順序である。
　ベキ 集合 （集合族） は、半順序である──そして、（2^A, ⊆） は、半順序集合である。ただし、｜A｜ ≧ 2 であれば──A の濃度 （メンバー の数） が 2以上であれば──、比較不能な部分集合があるので、⊆ は、2^A 上の全順序ではない。

　
● 関係 データベース と n項関係

　コッド 関係 モデル では、n項関係が重視される──つまり、A₁×A₂×・・・A_n という直積が重視される。
　たとえば、以下を考えてみる──A₁ を学生番号の セット、A₂ を科目名の セット、A₃ を合格判断の セット とする。

　　　A₁ ＝ { 001, 002 }.
　　　A₂ ＝ { 英語、数学、哲学 }.
　　　A₃ ＝ { 合格、不合格 }.

　そうすれば、A₁、A₂ および A₃ の直積は以下のようになる。

　（001, 英語, 合格）, （001, 英語, 不合格）,
　（001, 数学, 合格）, （001, 数学, 不合格）,
　（001, 哲学, 合格）, （001, 哲学, 不合格）,
　（002, 英語, 合格）, （002, 英語, 不合格）,
　（002, 数学, 合格）, （002, 数学, 不合格）,
　（002, 哲学, 合格）, （002, 哲学, 不合格）

　（　）のなかの値は、それぞれの セット から、ひとつずつ メンバー を選んで並べた組である。この組 （n-組） を「タプル （tuple）」という。

　そして、それらの部分集合 R として、以下が成り立つ、とする。

　R ＝｛（001, 英語, 合格）, （001, 数学, 合格）, （001, 哲学, 不合格）, （002, 数学, 合格）｝.

　この部分集合を、関係 R という。
　なお、タプル のなかの属性値の並びは、半順序であるが、関係 R のなかの タプル には、順序付けはない。

　また、セット A₁、A₂ および A₃ を、関係 R の属性値集合という。そして、関係 モデル では、属性値集合は、「単純 （simple）、原子的 （atomic）」 でなければならない、とされる。言い換えれば、「値の集合」 や、「構成された」 レコード であってはいけない、ということになる。つまり、属性値集合は、正規形として、単純定義域でなければならず、「集合を組とする」 構成 （複合定義域） であってはいけない、ということである。

　さて、たとえば、A₁ を部品番号の セット とし、A₂ を数量の セット とする。そして、A₁上の 2項関係を考えてみる。すなわち、部品番号のあいだに、親子関係 （半順序） が成立する部品構成を考えてみる。

　　A₁＝｛001, 002, ...｝.
　　A₂＝｛10, ...｝.
　　R ＝｛（（001, 002）, 10）, （（001, 003）, 10）,...｝.

　関係 R において、たとえば、（001, 002） は、（親-部品番号、子-部品番号） という 「集合を組とする オブジェクト （組 オブジェクト）」 である。

　部品表番号を付与して、部品構成表のなかで、階数 （縦列の階） と次数 （横列の類） を考えて、以下のように、関係 R を作ることもできる。なお、A₁ は部品構成表番号の セット であり、A₂ は部品番号の セット であり、A₃ は階数であり、A₄ は次数であり、A₅ を数量とする。

　　A₁＝｛01, 02, ...｝.
　　A₂＝｛001, 002, ...｝.
　　A₃＝｛0, 1, 2, ...｝.
　　A₄＝｛0, 1, 2, ...｝.
　　A₅＝｛10, ...｝.
　　R ＝｛（01, 001, 0, 0, 0）, （01, 002, 1, 1, 10）, （01, 003, 2, 1, 10）...｝.

　そうすれば、部品構成表を、単純定義域として、テーブル 構成にすることはできる。^（参考）
　しかし、自己言及的な セット （A の上の関係） では、半順序を意識した 「親子関係」 を考えるほうが──すなわち、ｎ-項関係のなかで、2項関係として、「組 オブジェクト」 を考えたほうが──、データ を演算しやすいのではないか。そして、「組 オブジェクト」 を前提にした複合定義域では、それぞれの属性値集合は、「単純かつ原子的な」 構成ではない──つまり、「階層的な構成」 を作り、非正規形になる。｛部品番号｝のなかを、（親-部品番号、子-部品番号） として複合的に構成する。

　ただし、どの程度まで、この複合的構成を許すか、という点は、悩ましい論点にはなるが、、、。

　
（参考）

　これを、グラフ 理論の観点に立って考えれば──グラフ 上の巡回として考えれば──、（u, v）∈ E であるとき、u を v の 「親」 といい、v を u の 「子」 という。そして、（u, v₁）∈ E かつ （u, v ₂）∈ E のとき、v₁ と v₂ を 「兄弟」 である、という。
　グラフ 上を巡回する手順として、以下の 2つの基本法がある。

　　（1） DFS （縦検索法）
　　（2） BFS （横検索法）