1. Hierarchical Queries
如果嫌描述啰嗦，直接 看 例子 prior 例子
1.
语法
connect by [nocycle] condition [start with condition]
start with condition connect by [nocycle] conditioncondition
start with 指定层次查询的 root row
connect by 指定层次查询中 parent rows 和 child rows 的关系
-
NOCYCLE 参数指示 Oracle 数据库从查询中返回行，即使数据中存在 CONNECT BY 循环。 将此参数与 CONNECT_BY_ISCYCLE 伪列一起使用以查看哪些行包含循环。 有关详细信息，请参阅 CONNECT_BY_ISCYCLE 伪列。
-
在分层查询中，条件中的一个表达式必须使用 PRIOR 运算符限定以引用父行。 例如，
... PRIOR expr = expr
or
... expr = PRIOR expr如果 CONNECT BY 条件是复合条件，则只有一个条件需要 PRIOR 运算符，尽管您可以有多个 PRIOR 条件。 例如：
CONNECT BY last_name != 'King' AND PRIOR employee_id = manager_id ...
CONNECT BY PRIOR employee_id = manager_id and
PRIOR account_mgr_id = customer_id ...PRIOR 是一元运算符，与一元 + 和 – 算术运算符具有相同的优先级。 它为分层查询中当前行的父行计算紧随其后的表达式。
PRIOR 最常用于使用相等运算符比较列值时。 （PRIOR 关键字可以在运算符的任一侧。） PRIOR 使 Oracle 使用列中父行的值。 在 CONNECT BY 子句中理论上可以使用除等号 (=) 以外的运算符。 但是，这些其他运算符创建的条件可能会导致通过可能的组合的无限循环。 在这种情况下，Oracle 在运行时检测到循环并返回错误。
CONNECT BY 条件和 PRIOR 表达式都可以采用不相关子查询的形式。 但是，CURRVAL 和 NEXTVAL 不是有效的 PRIOR 表达式，因此 PRIOR 表达式不能引用序列。
您可以通过使用 CONNECT_BY_ROOT 运算符来进一步细化层次查询，以限定选择列表中的列。 此运算符不仅返回直接父行，而且返回层次结构中的所有祖先行，从而扩展了层次查询的 CONNECT BY [PRIOR] 条件的功能。
2. 执行过程
Oracle 按如下方式处理分层查询：
-
如果存在连接，则首先评估连接，无论连接是在 FROM 子句中指定还是使用 WHERE 子句谓词。
-
评估 CONNECT BY 条件。
-
评估任何剩余的 WHERE 子句谓词。
然后，Oracle 使用来自这些评估的信息通过以下步骤形成层次结构：
-
Oracle 选择层次结构的根行——那些满足 START WITH 条件的行。
-
Oracle 选择每个根行的子行。每个子行必须满足关于其中一个根行的 CONNECT BY 条件的条件。
-
Oracle 选择连续几代的子行。 Oracle 首先选择步骤 2 中返回的行的子代，然后选择这些子代的子代，以此类推。 Oracle 总是通过评估与当前父行相关的 CONNECT BY 条件来选择子行。
-
如果查询包含没有连接的 WHERE 子句，则 Oracle 从层次结构中删除所有不满足 WHERE 子句条件的行。 Oracle 对每一行单独评估此条件，而不是删除不满足条件的行的所有子行。
-
Oracle 按图 9-1 所示的顺序返回行。在图中，孩子出现在父母的下方。有关分层树的说明，请参见图 3-1。
为了找到父行的子行，Oracle 计算父行的 CONNECT BY 条件的 PRIOR 表达式和表中每一行的另一个表达式。 条件为真的行是父项的子项。 CONNECT BY 条件可以包含其他条件以进一步过滤查询选择的行。
如果 CONNECT BY 条件导致层次结构中出现循环，则 Oracle 返回错误。 如果一行既是另一行的父（或祖父母或直接祖先）又是子（或孙子或直接后代），则发生循环。
注意：在分层查询中，不要指定 ORDER BY 或 GROUP BY，因为它们会覆盖 CONNECT BY 结果的分层顺序。 如果要对同一父级的兄弟行进行排序，请使用 ORDER SIBLINGS BY 子句。 请参见 order_by_clause。
3. Hierarchical 例子
3.1
CONNECT BY Example
以下分层查询使用 CONNECT BY 子句来定义员工和经理之间的关系：
SELECT employee_id, last_name, manager_id
FROM employees
CONNECT BY PRIOR employee_id = manager_id;
EMPLOYEE_ID LAST_NAME MANAGER_ID
----------- ------------------------- ----------
101 Kochhar 100
108 Greenberg 101
109 Faviet 108
110 Chen 108
111 Sciarra 108
112 Urman 108
113 Popp 108
200 Whalen 101
203 Mavris 101
204 Baer 101
. . .
3.2
LEVEL Example
下一个示例与前面的示例类似，但使用 LEVEL 伪列来显示父行和子行：
SELECT employee_id, last_name, manager_id, LEVEL
FROM employees
CONNECT BY PRIOR employee_id = manager_id;
EMPLOYEE_ID LAST_NAME MANAGER_ID LEVEL
----------- ------------------------- ---------- ----------
101 Kochhar 100 1
108 Greenberg 101 2
109 Faviet 108 3
110 Chen 108 3
111 Sciarra 108 3
112 Urman 108 3
113 Popp 108 3
200 Whalen 101 2
203 Mavris 101 2
204 Baer 101 2
205 Higgins 101 2
206 Gietz 205 3
102 De Haan 100 1
...
3.3
START WITH Examples
下一个示例添加一个 START WITH 子句来指定层次结构的根行，并使用 SIBLINGS 关键字添加一个 ORDER BY 子句来保持层次结构内的顺序：
SELECT last_name, employee_id, manager_id, LEVEL
FROM employees
START WITH employee_id = 100
CONNECT BY PRIOR employee_id = manager_id
ORDER SIBLINGS BY last_name;
LAST_NAME EMPLOYEE_ID MANAGER_ID LEVEL
------------------------- ----------- ---------- ----------
King 100 1
Cambrault 148 100 2
Bates 172 148 3
Bloom 169 148 3
Fox 170 148 3
Kumar 173 148 3
Ozer 168 148 3
Smith 171 148 3
De Haan 102 100 2
Hunold 103 102 3
Austin 105 103 4
Ernst 104 103 4
Lorentz 107 103 4
Pataballa 106 103 4
Errazuriz 147 100 2
Ande 166 147 3
Banda 167 147 3
...在 hr.employees 表中，员工 Steven King 是公司的负责人，没有经理。 他的员工中有 John Russell，他是部门 80 的经理。如果您更新 employees 表以将 Russell 设置为 King 的经理，您会在数据中创建一个循环：
UPDATE employees SET manager_id = 145
WHERE employee_id = 100;
SELECT last_name "Employee",
LEVEL, SYS_CONNECT_BY_PATH(last_name, '/') "Path"
FROM employees
WHERE level <= 3 AND department_id = 80
START WITH last_name = 'King'
CONNECT BY PRIOR employee_id = manager_id AND LEVEL <= 4;
ERROR:
ORA-01436: CONNECT BY loop in user dataCONNECT BY 条件中的 NOCYCLE 参数使 Oracle 尽管有循环仍返回行。 CONNECT_BY_ISCYCLE 伪列显示哪些行包含循环：
SELECT last_name "Employee", CONNECT_BY_ISCYCLE "Cycle",
LEVEL, SYS_CONNECT_BY_PATH(last_name, '/') "Path"
FROM employees
WHERE level <= 3 AND department_id = 80
START WITH last_name = 'King'
CONNECT BY NOCYCLE PRIOR employee_id = manager_id AND LEVEL <= 4
ORDER BY "Employee", "Cycle", LEVEL, "Path";
Employee Cycle LEVEL Path
------------------------- ---------- ---------- -------------------------
Abel 0 3 /King/Zlotkey/Abel
Ande 0 3 /King/Errazuriz/Ande
Banda 0 3 /King/Errazuriz/Banda
Bates 0 3 /King/Cambrault/Bates
Bernstein 0 3 /King/Russell/Bernstein
Bloom 0 3 /King/Cambrault/Bloom
Cambrault 0 2 /King/Cambrault
Cambrault 0 3 /King/Russell/Cambrault
Doran 0 3 /King/Partners/Doran
Errazuriz 0 2 /King/Errazuriz
Fox 0 3 /King/Cambrault/Fox
...
3.4
CONNECT_BY_ISLEAF Example
以下语句显示了如何使用分层查询将列中的值转换为逗号分隔的列表：
SELECT LTRIM(SYS_CONNECT_BY_PATH (warehouse_id,','),',') FROM
(SELECT ROWNUM r, warehouse_id FROM warehouses)
WHERE CONNECT_BY_ISLEAF = 1
START WITH r = 1
CONNECT BY r = PRIOR r + 1
ORDER BY warehouse_id;
LTRIM(SYS_CONNECT_BY_PATH(WAREHOUSE_ID,','),',')
--------------------------------------------------------------------------------
1,2,3,4,5,6,7,8,9
3.5
CONNECT_BY_ROOT Examples
以下示例返回部门 110 中每个员工的姓氏、层次结构中该员工上方最高级别的每个经理、经理和员工之间的级别数以及两者之间的路径：
SELECT last_name "Employee", CONNECT_BY_ROOT last_name "Manager",
LEVEL-1 "Pathlen", SYS_CONNECT_BY_PATH(last_name, '/') "Path"
FROM employees
WHERE LEVEL > 1 and department_id = 110
CONNECT BY PRIOR employee_id = manager_id
ORDER BY "Employee", "Manager", "Pathlen", "Path";
Employee Manager Pathlen Path
--------------- --------------- ---------- ------------------------------
Gietz Higgins 1 /Higgins/Gietz
Gietz King 3 /King/Kochhar/Higgins/Gietz
Gietz Kochhar 2 /Kochhar/Higgins/Gietz
Higgins King 2 /King/Kochhar/Higgins
Higgins Kochhar 1 /Kochhar/Higgins以下示例使用 GROUP BY 子句返回部门 110 中每个员工的总工资以及层次结构中该员工之上的所有员工：
SELECT name, SUM(salary) "Total_Salary" FROM (
SELECT CONNECT_BY_ROOT last_name as name, Salary
FROM employees
WHERE department_id = 110
CONNECT BY PRIOR employee_id = manager_id)
GROUP BY name
ORDER BY name, "Total_Salary";
NAME Total_Salary
------------------------- ------------
Gietz 8300
Higgins 20300
King 20300
Kochhar 20300
2. Hierarchical Operators
两个运算符 PRIOR 和 CONNECT_BY_ROOT 仅在分层查询中有效
1. PRIOR
在分层查询中，CONNECT BY 条件中的一个表达式必须由 PRIOR 运算符限定。 如果 CONNECT BY 条件是复合条件，则只有一个条件需要 PRIOR 运算符，尽管您可以有多个 PRIOR 条件。 PRIOR 计算层次查询中当前行的父行的紧随其后的表达式。
PRIOR 最常用于使用相等运算符比较列值时。 （PRIOR 关键字可以在运算符的任一侧。） PRIOR 使 Oracle 使用列中父行的值。 在 CONNECT BY 子句中理论上可以使用除等号 (=) 以外的运算符。 但是，这些其他运算符创建的条件可能会导致通过可能的组合的无限循环。 在这种情况下，Oracle 在运行时检测到循环并返回错误。 有关此运算符的更多信息（包括示例），请参阅分层查询。
如果还不理解 prior，见后面的例子 prior 例子
2. CONNECT_BY_ROOT
CONNECT_BY_ROOT 是一元运算符，仅在分层查询中有效。 当您使用此运算符限定列时，Oracle 使用根行中的数据返回列值。 此运算符扩展了分层查询的 CONNECT BY [PRIOR] 条件的功能。
对 CONNECT_BY_ROOT 的限制
您不能在 START WITH 条件或 CONNECT BY 条件中指定此运算符。
3. Hierarchical 伪列
分层查询伪列仅 (Pseudocolumns) 在分层查询中有效。 分层查询伪列是：
-
[CONNECT_BY_ISCYCLE Pseudocolumn]
-
[CONNECT_BY_ISLEAF Pseudocolumn]
-
[LEVEL Pseudocolumn]
要在查询中定义层次关系，您必须使用 CONNECT BY 子句。
3.1 CONNECT_BY_ISCYCLE
如果当前行有一个也是其祖先的子项，则 CONNECT_BY_ISCYCLE 伪列返回 1。 否则返回 0。
仅当您已指定 CONNECT BY 子句的 NOCYCLE 参数时，您才能指定 CONNECT_BY_ISCYCLE。 NOCYCLE 使 Oracle 能够返回查询的结果，否则该查询会因数据中的 CONNECT BY 循环而失败。
3.2 CONNECT_BY_ISLEAF
如果当前行是由 CONNECT BY 条件定义的树的叶子，则 CONNECT_BY_ISLEAF 伪列返回 1。 否则返回 0。此信息指示是否可以进一步扩展给定行以显示更多层次结构。
CONNECT_BY_ISLEAF Example
以下示例显示了 hr.employees 表的前三个级别，为每一行指示它是叶行（在 IsLeaf 列中用 1 表示）还是有子行（在 IsLeaf 列中用 0 表示）：
SELECT last_name "Employee", CONNECT_BY_ISLEAF "IsLeaf",
LEVEL, SYS_CONNECT_BY_PATH(last_name, '/') "Path"
FROM employees
WHERE LEVEL <= 3 AND department_id = 80
START WITH employee_id = 100
CONNECT BY PRIOR employee_id = manager_id AND LEVEL <= 4
ORDER BY "Employee", "IsLeaf";
Employee IsLeaf LEVEL Path
------------------------- ---------- ---------- -------------------------
Abel 1 3 /King/Zlotkey/Abel
Ande 1 3 /King/Errazuriz/Ande
Banda 1 3 /King/Errazuriz/Banda
Bates 1 3 /King/Cambrault/Bates
Bernstein 1 3 /King/Russell/Bernstein
Bloom 1 3 /King/Cambrault/Bloom
Cambrault 0 2 /King/Cambrault
Cambrault 1 3 /King/Russell/Cambrault
Doran 1 3 /King/Partners/Doran
Errazuriz 0 2 /King/Errazuriz
Fox 1 3 /King/Cambrault/Fox
. . .
3.3 LEVEL
对于分层查询返回的每一行，LEVEL 伪列为根行返回 1，为根的子行返回 2，依此类推。 根行是倒排树中的最高行。 子行是任何非根行。 父行是具有子行的任何行。 叶行是任何没有子行的行。 图 3-1 显示了倒排树的节点及其 LEVEL 值。
4. SYS_CONNECT_BY_PATH
SYS_CONNECT_BY_PATH (column, char)
4.1 功能
SYS_CONNECT_BY_PATH 仅在分层查询中有效。 它返回列值从根到节点的路径，对于 CONNECT BY 条件返回的每一行，列值由 char 分隔。
column 和 char 都可以是任何数据类型 CHAR、VARCHAR2、NCHAR 或 NVARCHAR2。 返回的字符串是 VARCHAR2 数据类型，并且与列在同一字符集中。
4.2
例子
以下示例返回从员工 Kochhar 到 Kochhar 的所有员工（及其员工）的员工姓名路径：
SELECT LPAD(' ', 2*level-1)||SYS_CONNECT_BY_PATH(last_name, '/') "Path"
FROM employees
START WITH last_name = 'Kochhar'
CONNECT BY PRIOR employee_id = manager_id;
Path
------------------------------
/Kochhar/Greenberg/Chen
/Kochhar/Greenberg/Faviet
/Kochhar/Greenberg/Popp
/Kochhar/Greenberg/Sciarra
/Kochhar/Greenberg/Urman
/Kochhar/Higgins/Gietz
/Kochhar/Baer
/Kochhar/Greenberg
/Kochhar/Higgins
/Kochhar/Mavris
/Kochhar/Whalen
/Kochhar
5. 例子
5.1 构造数据
CREATE TABLE test_tree (
test_id INT NOT NULL,
pid INT,
test_val VARCHAR(10),
PRIMARY KEY (test_id)
);
INSERT INTO test_tree VALUES(1, 0, '.NET');
INSERT INTO test_tree VALUES(2, 1, 'C#');
INSERT INTO test_tree VALUES(3, 1, 'J#');
INSERT INTO test_tree VALUES(4, 1, 'ASP.NET');
INSERT INTO test_tree VALUES(5, 1, 'VB.NET');
INSERT INTO test_tree VALUES(6, 0, 'J2EE');
INSERT INTO test_tree VALUES(7, 6, 'EJB');
INSERT INTO test_tree VALUES(8, 6, 'Servlet');
INSERT INTO test_tree VALUES(9, 6, 'JSP');
INSERT INTO test_tree VALUES(10, 0, 'Database');
INSERT INTO test_tree VALUES(11, 10, 'DB2');
INSERT INTO test_tree VALUES(12, 10, 'MySQL');
INSERT INTO test_tree VALUES(13, 10, 'Oracle');
INSERT INTO test_tree VALUES(14, 10, 'SQL Server');
INSERT INTO test_tree VALUES(15, 13, 'PL/SQL');
INSERT INTO test_tree VALUES(16, 15, 'Function');
INSERT INTO test_tree VALUES(17, 15, 'Procedure');
INSERT INTO test_tree VALUES(18, 15, 'Package');
INSERT INTO test_tree VALUES(19, 15, 'Cursor');
INSERT INTO test_tree VALUES(20, 14, 'T-SQL');
SELECT
LEVEL,
test_id,
test_val,
SYS_CONNECT_BY_PATH(test_val, '\') AS "FullPath"
FROM
test_tree
START WITH
pid =0
CONNECT BY PRIOR test_id = pid
ORDER SIBLINGS BY test_val;
5.2 执行结果解释
start with 配合 level 解释比较好理解，如果不指定 start with， 那么所有数据都会作为 根行，也就是 level 1。
如果指定了 start with ，被指定的行为根行。
-- 不指定 start with
SELECT level ,test_id, pid, test_val from test_tree CONNECT BY prior test_id= pid
order by 1,2
1 1 0 .NET
1 2 1 C#
1 3 1 J#
1 4 1 ASP.NET
1 5 1 VB.NET
1 6 0 J2EE
1 7 6 EJB
1 8 6 Servlet
1 9 6 JSP
1 10 0 Database
1 11 10 DB2
1 12 10 MySQL
1 13 10 Oracle
1 14 10 SQL Server
1 15 13 PL/SQL
1 16 15 Function
1 17 15 Procedure
1 18 15 Package
1 19 15 Cursor
1 20 14 T-SQL
2 2 1 C#
2 3 1 J#
2 4 1 ASP.NET
2 5 1 VB.NET
2 7 6 EJB
2 8 6 Servlet
2 9 6 JSP
2 11 10 DB2
2 12 10 MySQL
2 13 10 Oracle
2 14 10 SQL Server
2 15 13 PL/SQL
2 16 15 Function
2 17 15 Procedure
2 18 15 Package
2 19 15 Cursor
2 20 14 T-SQL
3 15 13 PL/SQL
3 16 15 Function
3 17 15 Procedure
3 18 15 Package
3 19 15 Cursor
3 20 14 T-SQL
4 16 15 Function
4 17 15 Procedure
4 18 15 Package
4 19 15 Cursor
-- 指定 start with
SELECT level ,test_id, pid, test_val from test_tree
start with test_id=10 CONNECT BY prior test_id= pid order by 1,2
1 10 0 Database
2 11 10 DB2
2 12 10 MySQL
2 13 10 Oracle
2 14 10 SQL Server
3 15 13 PL/SQL
3 20 14 T-SQL
4 16 15 Function
4 17 15 Procedure
4 18 15 Package
4 19 15 Cursorprior例子 由于prior 可能会不大好理解，这里再详细解释一下
SELECT level ,test_id, pid, test_val from test_tree
start with test_id=10 CONNECT BY prior test_id= pid order by 1,2
1 10 0 Database
2 11 10 DB2
2 12 10 MySQL
2 13 10 Oracle
2 14 10 SQL Server
3 15 13 PL/SQL
3 20 14 T-SQL
4 16 15 Function
4 17 15 Procedure
4 18 15 Package
4 19 15 Cursor
此时 形成的 树形结构为
level 1 10
｜
————————----------————————
｜ ｜ ｜ ｜
level 2 11 12 13 14 -----> prior 指定 父行
｜ ｜ ｜ ｜
level 3 15 20 -----> prior 指定
|
---------------
| | | |
16 17 18 19
level 4
-- prior 在另一侧，修改一下 start with 的条件。
SELECT level ,test_id, pid, test_val from test_tree
start with test_id = 15 CONNECT BY test_id = prior pid order by 1,2
1 15 13 PL/SQL
2 13 10 Oracle
3 10 0 Database
此时 形成的 树形结构为
level 1 13 ----> test_id = 13, 此时 pid = 13。 prior 指定的父行
|
level 2 10
|
level 3 0
完整功能
-- 完整的功能有 10 个。
SELECT
test_id, pid, test_val,
-- 1. 操作符
connect_by_root test_id ,
-- 2. 函数
SYS_CONNECT_BY_PATH(pid, '/'),
-- 3. 伪列(三个)
CONNECT_BY_ISCYCLE,
-- 4.
CONNECT_BY_ISLEAF,
-- 5.
level
from test_tree
-- 6. 根行
start with test_id=10
-- 7. 父行和子行的关系
CONNECT BY nocycle /* 8. ( cycle ) */ prior /* 9. 操作符 */ test_id= pid
-- 10. 排序
ORDER SIBLINGS BY test_id;
10 0 Database 10 /0 0 0 1
11 10 DB2 10 /0/10 0 1 2
12 10 MySQL 10 /0/10 0 1 2
13 10 Oracle 10 /0/10 0 0 2
15 13 PL/SQL 10 /0/10/13 0 0 3
16 15 Function 10 /0/10/13/15 0 1 4
17 15 Procedure 10 /0/10/13/15 0 1 4
18 15 Package 10 /0/10/13/15 0 1 4
19 15 Cursor 10 /0/10/13/15 0 1 4
14 10 SQL Server 10 /0/10 0 0 2
20 14 T-SQL 10 /0/10/14 0 1 3
6. SQL 标准 CTE
6.1 CTE 描述
**common table expression **或 CTE 是从简单的 SELECT 语句创建的临时命名结果集，可用于后续的 SELECT 语句。 每个 SQL CTE 就像一个命名查询，其结果存储在一个虚拟表 (CTE) 中，以便稍后在主查询中引用。
6.2 CTE实现 connect by
我们之间将如何使用 CTE 来实现 oracle 的层级查询功能，直接看例子。
-- connect by
SELECT level ,test_id, pid, test_val from test_tree
start with test_id=10 CONNECT BY prior test_id= pid order by 1,2
SELECT LEVEL, empno, ename, mgr, sal
FROM emp_
CONNECT BY PRIOR empno = mgr
START WITH ename = 'BLAKE';
-- ctes 实现上述 层次查询
with recursive cte_tab(level, test_id, pid, test_val) {
select 1 AS level,test_id, pid, test_val from test_tree where test_id=10
union all
select cte_tab.level+1 ,test_treetest_.id, test_tree.pid, test_tree.test_val from test_tree, cte_tab
where cte_tab.test_id= test_val.pid
}
select * from cte_tab;
7. connect by 算法
是一个查找算法。
7.1 基本算法描述
是一个树的前序遍历，本来前序遍历不需要这么复杂。因为需要判断每个分支是否成环，所以需要记录遍历到了第几个孩子。用一个哈希表记录。
7.2 算法伪代码
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
unordered_map<Node *, int> cnt;
stack<Node *> st;
Node * node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
res.emplace_back(node->val);
st.emplace(node);
if (node->children.size() > 0) {
cnt[node] = 0;
node = node->children[0];
} else {
node = nullptr;
}
}
node = st.top();
int index = (cnt.count(node) ? cnt[node] : -1) + 1;
if (index < node->children.size()) {
cnt[node] = index;
node = node->children[index];
} else {
st.pop();
cnt.erase(node);
node = nullptr;
}
}
return res;
}
};