Introducing find_all_inheritors_ordered()

Started by Chao Li4 days ago1 messageshackers
Jump to latest
#1Chao Li
li.evan.chao@gmail.com

Hi,

This is follow-up work to patch [1]/messages/by-id/E74C57FA-1DD0-4C8E-8FB1-538034752592@gmail.com, which fixed a bug when altering a CHECK constraint's enforceability. The fix was not very elegant. It had to use upward recursion to traverse all ancestors when deciding a child table's enforceability. This was because the existing function find_all_inheritors() returns a list of descendants without ensuring that parents precede their children.

This patch introduces a new function, find_all_inheritors_ordered(), which guarantees that every ancestor in the returned list appears before its descendants. With this new function, the original fix in commit 0cd17fdd3c0 is significantly simplified. The function could also potentially benefit other features that need to traverse inheritance trees in parent-before-child order.

This patch also strengthens an existing test by adding another level of inheritance. My first version of the implementation failed with the following case:
```
Root ———————————————> child
\ /
\ ——————> a —————> b /
```
(The diagram might not display well. Basically, “child" has parents “b" and “root", “b" has parent “a”, “a” has parent “root")

The current version uses Kahn's topological sorting algorithm, which handles this case correctly. Please see the attached patch for details.

[1]: /messages/by-id/E74C57FA-1DD0-4C8E-8FB1-538034752592@gmail.com

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

Attachments:

v1-0001-Add-find_all_inheritors_ordered.patchapplication/octet-stream; name=v1-0001-Add-find_all_inheritors_ordered.patch; x-unix-mode=0644Download+159-93