SQL实现树与层次结构解析

3星 · 超过75%的资源需积分: 34 154 浏览量更新于2024-07-29 收藏 2.51MB PDF 举报

"《SQL权威指南：Joe Celko谈树与层次结构》" 在数据库管理中，处理树形结构和层级数据是常见的挑战。SQL，作为结构化查询语言，提供了处理这类数据的方法。《SQL权威指南：Joe Celko谈树与层次结构》一书由知名数据库专家Joe Celko撰写，深入探讨了如何在SQL环境中有效地实现和操作树和层次结构。 SQL处理树和层次结构通常涉及到以下几个核心概念： 1. **递归查询**：在SQL中，递归查询允许通过自身引用来遍历层级关系。例如，通过员工的上级ID找到整个组织架构。Celko可能会讲解如何使用递归公用表表达式（Recursive Common Table Expressions, CTE）或者自连接来实现这一功能。 2. **自连接**：在同一个表中，一个记录可以与另一个记录建立连接，这在表示层次结构时非常有用。例如，在一个部门表中，每个部门可能有一个父部门，通过自连接可以查询出所有子部门。 3. **路径枚举法**：这种方法将层级路径存储为字符串，如“1.2.3”表示层级的第三级。Celko可能讨论如何存储、检索和操作这些路径，以及其优缺点。 4. **嵌套集模型**：也称为Madjidov模型，它使用两个字段（左值和右值）来表示每个节点的位置。通过比较这些值，可以快速构建和查询树形结构。 5. **物质化路径**：与路径枚举法类似，但路径可能包含实际的键值，而不是顺序号，这样可以直接定位到特定的节点。 6. **连接表**：当层次结构过于复杂时，可能需要额外的表来存储父子关系。这种方式虽然灵活，但查询性能可能受到影响。 7. ** Closure Table**：这是一种存储所有可能的祖先-后代对的表，提供高效的查询性能，但需要更多的存储空间。 Joe Celko的书会详细解释这些方法，并提供实用的例子和最佳实践，帮助读者理解如何在实际项目中选择和应用适合的策略。此外，他还可能讨论不同的数据库管理系统（DBMS）如何支持这些技术，以及在处理大量数据或复杂查询时的性能考虑。这本书对于数据库开发者、数据分析师和系统架构师来说是一本宝贵的参考书，它不仅传授理论知识，还提供了实践技巧，帮助读者更好地理解和处理SQL中的树形和层次数据结构。

LET’S START WITH a little mathematical background. Graph theory is a branch

of mathematics that deals with abstract structures, known as graphs.

These are not the presentation charts that you get out of a spreadsheet

package.

Very loosely speaking, a graph is a diagram of “dots” (called nodes or

vertices) and “lines” (edges) that model some kind of “flow” or relationship.

The edges can be undirected or directed. Graphs are very general models. In

circuit diagrams the edges are the wires and the nodes are the components. On

a road map the nodes are the towns and the edges are the roads. Flowcharts,

organizational charts, and a hundred other common abstract models you see

every day are all shown as graphs.

A directed graph allows a “flow” along the edges in one direction only, as

shown by the arrowheads, whereas an undirected graph allows the flow to

travel in both directions. Exactly what is flowing depends on what you are

modeling with the graph.

The convention is that an edge must join two (and only two) nodes. This

lets us show an edge as an ordered pair of nodes, such as (Atlanta, Boston) if

we are dealing with a map, or (a, b) in a more abstract notation. There is an

implication in a directed graph that the direction is shown by the ordering. In

an undirected graph we know that (a, b) = (b, a), however.

A node can sit alone or have any number of edges associated with it. A node

can also be self-referencing, as in (a, a).

Graphs, Trees, and Hierarchies

CHAPTER

Ch01.qxd 03/31/04 6:32 AM Page 3

The terminology used in graph theory will vary, depending on which book

you had in your finite math class. The following list, in informal language,

includes the terms I will use in this book.

Order of a graph: number of nodes in the graph

Degree: the number of edges at a node, without regard to whether the graph is

directed or undirected

Indegree: the number of edges coming into a node in a directed graph

Outdegree: the number of edges leaving a node in a directed graph

Subgraph: a graph that is a subset of another graph’s edges and nodes

Walk: a subgraph of alternating edges and nodes that are connected to

each other in such a way that you can trace around it without lifting your

finger

Path: a subgraph that does not cross over itself—there is a starting node with

degree one, an ending node with degree one, and all other nodes have

degree two. It is a special case of a walk. It is a “connect-the-dots” puzzle.

Cycle: a subgraph that “makes a loop,” so that all nodes have degree two. In a

directed graph all the nodes of a cycle have outdegree one and indegree one

(Figure 1.1).

Connected graph: a graph in which all pairs of nodes are connected by a path.

Informally, the graph is all in one piece.

Forest: a collection of separate trees. Yes, I am defining this term before we

finally get to discussing trees.

There are a lot more terms to describe special kinds of graphs, but frankly,

we will not use them in this book. We are supposed to be learning SQL

programming, not graph theory.

The strength of graphs as problem-solving tools is that the nodes and edges

can be given extra attributes that adapt this general model to a particular problem.

Edges can be assigned “weights,” such as expected travel time for the roads on a

highway map. Nodes can be assigned “colors” that put them into groups, such as

men and women. Look around and you will see how they are used.

1.1 Modeling a Graph in a Program

Long before there was SQL, programmers represented graphs in the

programming language that they had. People used pointer chains in assembly

4 CHAPTER 1: GRAPHS, TREES, AND HIERARCHIES

Ch01.qxd 03/31/04 6:32 AM Page 4

剩余237页未读，继续阅读

雪峰

粉丝: 75
资源: 43

SQL实现树与层次结构解析

SqlServer树形结构、层次查询

flora-sql-parser：将SQL（选择）语句解析为抽象语法树（AST），并将AST转换回SQL

SQL处理多级分类,查询结果呈树形结构

Microsoft SQL Server中T-SQL关于树(层次)结构的处理研究.pdf

用SQL实现树的查询

SQL数据库设计：探索树与层次结构模型

SQL SERVER 实现无级树结构查询与更新

sqlserver实现树形结构递归查询(无限极分类)的方法

SQL实现无限级树形菜单

asp+sql 目录树实现

最新资源