CS186 笔记03

信息检索 (IR) 与数据库管理系统 (DBMS)

什么是信息检索 (IR)？ (What it is)

信息检索 (IR) 是一个传统上与数据库领域分离的研究领域.
Hans P. Luhn在1959年提出了“Keyword in Context (KWIC)”.
G. Salton在60、70年代开发了SMART系统.
这与关系数据库的革命大约同时发生.
自那时起进行了大量的研究，尤其是在网络时代.
IR产品传统上是独立的，最初是文档管理系统. 它们服务于图书馆、政府、法律等领域.
随着网络搜索和广告的兴起，IR迎来了复兴. 在“企业搜索”领域仍是一个小众市场.

IR与DBMS有何异同？ (Why it's needed)

IR和DBMS看起来非常不同.
然而，在底层，它们并非如看起来那么不同.
实践中，目前没有产品能同时做好两者.
IR引擎通常比大多数DBMS更“定制化”.

特性	IR (信息检索)	DBMS (数据库管理系统)
语义	不精确语义	精确语义
查询方式	关键词搜索	SQL
数据类型	非结构化文本	结构化数据
更新方式	读多写少，批量添加文档	事务性更新
结果呈现	分页显示Top K结果	生成完整答案

DBMS架构：包括SQL客户端、查询解析与优化、关系运算符、文件与索引管理、缓冲区管理、磁盘空间管理、并发控制和恢复.
搜索引擎架构：包括查询、搜索修饰/自动补全、排名算法、索引、文件、操作系统层面的缓冲区管理和磁盘空间管理、爬虫和批量加载器.
IR和关系型系统共享可扩展性的构建块.
内部地，搜索引擎将文本转换为关系型元组. 例如，都使用等值索引（B-树）、数据流（迭代器）和并行数据流、以及“连接”算法，特别是合并连接.
IR对查询、模式和语义承诺有约束. 这会影响存储格式、索引和并发控制以及连接算法和选择性估计.
IR有不同的性能目标，例如快速返回排名靠前的最佳答案.

文本搜索的核心构建块

什么是IR的“词袋模型”？ (What it is)

典型的IR数据模型是每个文档被视为一个词的集合（“术语包”）.
停用词 (Stop Words)：某些不具帮助的词（例如“the”或HTML标签<H1>) 不会放入词袋中.
词干提取 (Stemming)：使用特定语言的规则，将词转换为基本形式，例如“surfing”、“surfed”转换为“surf”. 这需要针对每种语言进行处理. 有许多开源库可以实现这一点，例如Python的nltk.

文本“索引”是如何工作的？ (How it works)

A. 倒排文件 (Inverted Files) (What it is)

当IR人员说“文本索引”时，通常比DB人员所指的含义更广.
它实际上是一个逻辑模式（即表）和物理模式（即索引）.
通常不存储在DBMS中，而是将表实现为文件系统中的文件.
给定一个文本文件集合 Files(docID text, content text).
创建并填充一个表 InvertedFile(term text, docID text).
在 InvertedFile.term 上构建B+-树或哈希索引 (例如使用“Alternative 3”索引).
保持底层的列表按 docID 排序，这通常被称为**“倒排列表” (postings list)**.
这样就可以进行单字查询.
“倒排文件”是所有文本搜索引擎的核心工作机制. 它们只是基于词袋模型的B+-树或哈希索引.

B. 布尔文本搜索如何实现？ (How it works)

查找所有匹配布尔表达式的文档，例如“Windows” AND (“Glass” OR “Door”) AND NOT “Microsoft”.
查询词会被词干提取/停用.
网页搜索引擎显示的“10,000,000 documents found”大体上就是布尔搜索的结果大小.
“term1” OR “term2”：是两个倒排列表（docID集合）的并集.
“term1” AND “term2”：是两个倒排列表的交集，可以通过合并已按 docID 排序的倒排列表来实现.
“term1” AND NOT “term2”：是集合减法，同样可以通过合并实现.
“term1” OR NOT “term2”：通常不允许，因为它会产生巨大的结果集.
SQL中的布尔搜索：例如，查询“Berkeley Database Research”可以用SQL表示为连接操作. 查询计划通常涉及对每个术语的索引扫描，并通过流式合并连接（Merge-join）来实现.
其他大部分内容是文本和网络特有的，例如语言学和统计学 (更多是后者)、利用网络的图结构、理解内容类型和用户需求.

C. 词组和“近义词”查询如何处理？ (How it works)

为了支持词组查询（如“Happy Days”），可以增强 InvertedFile 模式，添加 position 字段：InvertedFile (term string, docID string, position int).
倒排列表按 (docID, position) 排序.
查询时先找到单个词，然后后处理结果，检查词的位置是否相差1. 这可以在 AND 操作合并列表时完成.
“term1” NEAR “term2” 也可以类似实现，检查位置是否相差小于k.

D. 如何获取文档内容？ (How it works)

docID 通常转换为整数以进行更好的压缩.
Files 表可能包含 (docID int, URL string, snippet string, …) 以及可能的缓存文件ID.
在 InvertedFile.term 上和 Files.docID 上都会有B树索引.
这需要在查询结果和 Files.docID 之间进行最终的“连接”步骤，通常是惰性执行，一次一页结果.

文本搜索中的更新与并发控制

文本搜索引擎如何处理更新？ (How it works)

文本搜索引擎通常设计为查询为主.
删除和修改很少发生.
更新可以推迟 (没有人会注意到，也没有事务的概念).
可以基于索引的并集进行操作，然后批量合并它们（通常是重新批量加载一个新索引），这被称为“Log-Structured Merge”索引.
如果系统不能离线更新，可以创建第二个索引在单独的机器上，然后用它替换第一个.
因此，不存在并发控制问题.
可以将数据压缩成有利于搜索但不利于更新的格式，并保持倒排列表排序.

补充信息

排名 (Ranking)：magic_rank() 是搜索引擎的“秘诀”，结合了统计、语言学和图论的技巧.
IR常用术语：
- Corpus：文档的集合.
- Term：一个独立的字符串（可搜索的单元）.
- Index：将术语映射到文档的机制.
- Inverted File (倒排文件) / Postings File (倒排列表文件)：包含术语及其关联倒排列表的文件.
- Postings List (倒排列表)：指向文档的指针列表.
其他技巧：包括更快的倒排列表交集、内存中的多路合并连接算法、文档“聚类”以使输出多样化、如何利用压缩提高I/O性能（例如缩小倒排列表）、如何处理同义词、拼写错误、缩写、如何编写好的网络爬虫和索引加载器、处理SEO（即网络垃圾邮件）以及用户自定义.

逻辑数据库设计：实体-关系模型

什么是数据库设计？ (What it is)

数据库设计步骤：
1. 需求分析 (Requirements Analysis)：了解用户需求，数据库必须做什么.
2. 概念设计 (Conceptual Design)：高层描述（通常使用ER模型完成）. 对象-关系映射（ORM：Hibernate, Rails, Django等）鼓励在此阶段进行编程.
3. 逻辑设计 (Logical Design)：将ER模型转换为DBMS数据模型. ORM通常也要求在此处提供帮助.
4. 模式细化 (Schema Refinement)：关注一致性、规范化.
5. 物理设计 (Physical Design)：包括索引、磁盘布局.
6. 安全设计 (Security Design)：确定谁可以访问什么以及如何访问.

什么是数据模型和抽象层次？ (What it is)

数据模型 (Data model)：描述数据的一系列概念集合.
模式 (Schema)：使用给定数据模型对特定数据集合的描述.
关系模型 (Relational model of data)：
- 主要概念：关系 (table)，由行和列组成.
- 每个关系都有一个模式，描述列名和域.
抽象层次 (Levels of Abstraction)：
- 视图 (Views)：描述用户如何看到数据.
- 概念模式 (Conceptual schema)：定义逻辑结构.
- 物理模式 (Physical schema)：描述使用的文件和索引.

A. 示例：大学数据库 (How it works)

概念模式：
- Students(sid text, name text, login text, age integer, gpa float)
- Courses(cid text, cname text, credits integer)
- Enrolled(sid text, cid text, grade text)
物理模式：
- 关系存储为无序文件.
- 在Students表的第一列上建立索引.
外部模式 (View)：
- Course_info(cid text, enrollment integer)

什么是数据独立性？ (Why it's needed)

数据独立性：使应用程序与数据结构隔离.
逻辑数据独立性 (Logical data independence)：当逻辑结构改变时，维护视图.
物理数据独立性 (Physical data independence)：当物理结构改变时，维护逻辑结构.
重要性：对于DBMS尤为重要，因为数据库及其相关应用程序是持久存在的.

实体-关系 (E-R) 模型

为什么需要ER模型？ (Why it's needed)

关系模型是一种很好的形式化方法，但对于设计阶段来说过于详细.
不适合头脑风暴，也难以与“客户”沟通.
实体-关系模型 (Entity-Relationship model)：一种基于图形的模型.
可以被视为图，或者关系之上的薄层.
“感觉”更灵活，结构化程度更低.
与“对象-关系映射”（ORM）软件包（如Ruby-on-Rails, Django, Hibernate, Sequelize等）高度对应.
概念设计是数据工程的开始. 这也是ORM中MVC模式的“模型”.

ER模型的基本概念是什么？ (What it is)

A. 实体 (Entities) (What it is)

实体 (Entity)：由一组属性值描述的真实世界对象.
实体集 (Entity Set)：相似实体的集合，例如所有员工.
实体集中的所有实体都具有相同的属性.
每个实体集都有一个键 (key)（带下划线标记）.
每个属性都有一个域 (domain).

B. 关系 (Relationships) (What it it)

关系 (Relationship)：两个或多个实体之间的关联. 例如，Attishoo在药房部门工作.
关系可以拥有自己的属性.
关系集 (Relationship Set)：相似关系的集合.
一个n元关系集R关联n个实体集E1...En；R中的每个关系都涉及实体e1属于E1，...，en属于En.
同一个实体集可以参与不同的关系集，或者在同一个关系集中扮演不同的“角色”.

C. 键约束 (Key Constraints) (What it is)

键约束定义了关系中每个实体在参与关系时，可以关联到另一个实体集中的多少个实体.
例如，一个员工可以在多个部门工作；一个部门可以有多个员工.
相比之下，根据Manages关系集中的部门键约束，每个部门最多有一个经理.
键约束定义了1对多关系.
类型：1对1，1对多，多对1，多对多.

D. 参与约束 (Participation Constraints) (What it is)

参与约束 (Participation constraint)：规定一个实体集中的每个实体是否必须参与一个关系集.
例如，每个员工是否都在某个部门工作？如果是，则Employees在Works_In中的参与是总的 (total)（相对于部分的 (partial)）.
如果每个部门都有一个员工在其内工作，则表示至少有一个.

E. 弱实体 (Weak Entities) (What it is)

弱实体 (Weak entity)：只能通过考虑另一个（所有者 (owner)）实体的主键 (primary key) 才能唯一标识的实体.
所有者实体集和弱实体集必须参与一个一对多关系集（一个所有者，多个弱实体）.
弱实体集必须在该标识关系集中具有总参与 (total participation).
弱实体只有**“部分键” (partial key)**（虚线表示下划线）.

F. 聚合 (Aggregation) (What it is)

聚合 (Aggregation)：允许关系拥有关系.

ER模型到关系模式的转换

如何将ER模型转换为关系模式？ (How it works)

ER模型和关系模式具有相当类似的结构.
但ER中许多简单的概念在关系中指定起来很微妙.

A. 实体集到表 (Entity sets to tables) (How it works)

将实体集转换为表很容易.
示例：CREATE TABLE Employees (ssn CHAR(11), name CHAR(20), lot INTEGER, PRIMARY KEY (ssn))

B. 关系集到表 (Relationship Sets to Tables) (How it works)

在将多对多关系集转换为关系时，关系的属性必须包括：
1. 每个参与实体集的键（作为外键）. 这些属性形成关系的一个超键 (superkey).
2. 所有描述性属性.

示例：

sql

CREATE TABLE Works_In(
    ssn  CHAR(11),
    did  INTEGER,
    since  DATE,
    PRIMARY KEY (ssn, did),
    FOREIGN KEY (ssn) REFERENCES Employees,
    FOREIGN KEY (did) REFERENCES Departments
)

C. 转换带有键约束的ER模型 (Translating ER with Key Constraints) (How it works)

如果每个部门最多有一个经理（Manages上的键约束），则可以将 Manages 和 Departments 合并.

示例：

sql

CREATE TABLE Dept_Mgr(
    did  INTEGER,
    dname  CHAR(20),
    budget  REAL,
    ssn  CHAR(11),
    since  DATE,
    PRIMARY KEY  (did),
    FOREIGN KEY (ssn) REFERENCES Employees
)

D. SQL中的参与约束 (Participation Constraints in SQL) (How it works)

我们可以捕获涉及一个实体集在二元关系中的参与约束，但其他情况（不使用 CHECK 约束）则不能.

示例：

sql

CREATE TABLE Dept_Mgr(
    did  INTEGER,
    dname  CHAR(20),
    budget  REAL,
    ssn  CHAR(11) NOT NULL, -- total participation!
    since  DATE,
    PRIMARY KEY  (did),
    FOREIGN KEY  (ssn) REFERENCES Employees ON DELETE NO ACTION
)

NOT NULL 用于实现总参与.

E. 弱实体集的转换 (Translating Weak Entity Sets) (How it works)

弱实体集和标识关系集被转换为单个表.
当所有者实体被删除时，所有被拥有的弱实体也必须被删除.

示例：

sql

CREATE TABLE Dep_Policy (
    pname  CHAR(20),
    age  INTEGER,
    cost  REAL,
    ssn  CHAR(11) NOT NULL,
    PRIMARY KEY  (pname, ssn),
    FOREIGN KEY  (ssn) REFERENCES Employees ON DELETE CASCADE
)

概念设计总结

概念设计的目标和局限性是什么？ (What it is)

概念设计是在需求分析之后进行的.
它产生要存储数据的高层描述.
ER模型在概念设计中很受欢迎. 它的构造富有表现力，与我们思考应用程序的方式接近.
ER模型有多种变体，包括图形和概念上的变体.
基本构造包括：实体、关系和属性（实体和关系的属性）.
其他构造包括：弱实体、ISA层次结构和聚合.

ER模型的完整性约束和设计选择 (What it is)

基本完整性约束：
- 键约束.
- 参与约束.
- 关系集的定义中也隐含了一些外键约束.
局限性：许多其他约束（特别是函数依赖）无法表达.
约束在确定企业最佳数据库设计中起着重要作用.
ER设计是主观的. 针对给定场景有多种建模方式.
分析替代方案可能很棘手. 常见的选择包括：实体 vs. 属性、实体 vs. 关系、二元或N元关系、是否使用聚合.
为了良好的数据库设计：最终的关系模式应进一步分析和细化.

CS186 笔记03 ​

信息检索 (IR) 与数据库管理系统 (DBMS) ​

什么是信息检索 (IR)？ (What it is) ​

IR与DBMS有何异同？ (Why it's needed) ​

文本搜索的核心构建块 ​

什么是IR的“词袋模型”？ (What it is) ​

文本“索引”是如何工作的？ (How it works) ​

A. 倒排文件 (Inverted Files) (What it is) ​

B. 布尔文本搜索如何实现？ (How it works) ​

C. 词组和“近义词”查询如何处理？ (How it works) ​

D. 如何获取文档内容？ (How it works) ​

文本搜索中的更新与并发控制 ​

文本搜索引擎如何处理更新？ (How it works) ​

补充信息 ​

逻辑数据库设计：实体-关系模型 ​

什么是数据库设计？ (What it is) ​

什么是数据模型和抽象层次？ (What it is) ​

A. 示例：大学数据库 (How it works) ​

什么是数据独立性？ (Why it's needed) ​

实体-关系 (E-R) 模型 ​

为什么需要ER模型？ (Why it's needed) ​

ER模型的基本概念是什么？ (What it is) ​

A. 实体 (Entities) (What it is) ​

B. 关系 (Relationships) (What it it) ​

C. 键约束 (Key Constraints) (What it is) ​

D. 参与约束 (Participation Constraints) (What it is) ​

E. 弱实体 (Weak Entities) (What it is) ​

F. 聚合 (Aggregation) (What it is) ​

ER模型到关系模式的转换 ​

如何将ER模型转换为关系模式？ (How it works) ​

A. 实体集到表 (Entity sets to tables) (How it works) ​

B. 关系集到表 (Relationship Sets to Tables) (How it works) ​

C. 转换带有键约束的ER模型 (Translating ER with Key Constraints) (How it works) ​

D. SQL中的参与约束 (Participation Constraints in SQL) (How it works) ​

E. 弱实体集的转换 (Translating Weak Entity Sets) (How it works) ​

概念设计总结 ​

概念设计的目标和局限性是什么？ (What it is) ​

ER模型的完整性约束和设计选择 (What it is) ​

CS186 笔记03

信息检索 (IR) 与数据库管理系统 (DBMS)

什么是信息检索 (IR)？ (What it is)

IR与DBMS有何异同？ (Why it's needed)

文本搜索的核心构建块

什么是IR的“词袋模型”？ (What it is)

文本“索引”是如何工作的？ (How it works)

A. 倒排文件 (Inverted Files) (What it is)

B. 布尔文本搜索如何实现？ (How it works)

C. 词组和“近义词”查询如何处理？ (How it works)

D. 如何获取文档内容？ (How it works)

文本搜索中的更新与并发控制

文本搜索引擎如何处理更新？ (How it works)

补充信息

逻辑数据库设计：实体-关系模型

什么是数据库设计？ (What it is)

什么是数据模型和抽象层次？ (What it is)

A. 示例：大学数据库 (How it works)

什么是数据独立性？ (Why it's needed)

实体-关系 (E-R) 模型

为什么需要ER模型？ (Why it's needed)

ER模型的基本概念是什么？ (What it is)

A. 实体 (Entities) (What it is)

B. 关系 (Relationships) (What it it)

C. 键约束 (Key Constraints) (What it is)

D. 参与约束 (Participation Constraints) (What it is)

E. 弱实体 (Weak Entities) (What it is)

F. 聚合 (Aggregation) (What it is)

ER模型到关系模式的转换

如何将ER模型转换为关系模式？ (How it works)

A. 实体集到表 (Entity sets to tables) (How it works)

B. 关系集到表 (Relationship Sets to Tables) (How it works)

C. 转换带有键约束的ER模型 (Translating ER with Key Constraints) (How it works)

D. SQL中的参与约束 (Participation Constraints in SQL) (How it works)

E. 弱实体集的转换 (Translating Weak Entity Sets) (How it works)

概念设计总结

概念设计的目标和局限性是什么？ (What it is)

ER模型的完整性约束和设计选择 (What it is)