This Engineering Notebook post continues the previous ENB post. It discusses how a Database Access Plugin (DAP) could convert the results of a query to a DAG (a Leo outline).
This post is a proof of concept. I have no intention of writing any DAP. Still, the ideas are interesting in themselves. In general, the results of a query will be a graph. Ordered lists are a special kind of graph. Let's look at lists first. *Converting lists to outlines* Suppose a query returns an *ordered *list of 10,000 results. Let's call this list the *results list*. Leo could represent the results list as a single node with 10,000 lines, but let's put each result in a separate node. We could represent the query as a node with 10,000 children, but that would be difficult for humans to use. Instead, let's convert the list into an *organizer outline*. Most of this outline will consist of organizer nodes. Only the bottom-level nodes (the nodes without children) contain results. Let's call these nodes the *result nodes*. In our example, our organizer outline will contain 10 + 100 + 1000 organizer nodes in a 4-level outline: - Level 0: A *query node* represents the entire result. It will have 10 children, the *level 1 organizer nodes*, each having 10 children. - Level 1: 100 *level 2 organizer nodes*, each having 10 children. - Level 2: 1000 *level 3 organizer nodes*, each having 10 children. - Level 3: 10,000 results nodes. I'll leave the algorithm that creates this outline as an exercise for the reader :-) *Summary*: we can organize lists into an outline whose traversal yields the result nodes *in the same order as the results list.* *Converting graphs to outlines* In this section, I'll sketch some ideas for converting a general graph to an outline. The details don't matter much, but there will be a surprise at the end. In general, the nodes of a graph have no natural order, so a Database Access Plugin may create an outline without worrying about its order. We can assume that the graph is a directed graph. We'll convert undirected links into two directed links in opposite directions. We'll convert a (directed) graph to an outline much like we converted (directed) lists: - Choose any 10 nodes of the graph. These *root nodes* are the top-level nodes of the outline. - Remove all links *to *the root nodes. - For each root node, choose up to 10 *level-one children*. - Remove the links from the level-one children to their parents. - Continue recursively with all level-one children :-) Yes, there is some hand-waving here. I have deliberately ignored some complications: 1. This approach might not guarantee that there will be links from the roots to all nodes. In that case, we will add the "orphaned" nodes to the top-level root nodes. 2. The algorithm doesn't say whether nodes may have more than one parent. Leo's outlines allow this possibility, but we may want to convert the graph to a tree instead of a DAG. 3. There are *many* ways of choosing roots, children, and which links to delete. Thus, there are *many* ways to convert a graph to a DAG. These differences don't matter, provided the resulting DAG has relatively few levels. A post-pass could reassign nodes to improve the DAG's shape, but I am not interested in such details here. *Summary*: Converting a graph to a DAG (or tree) is relatively easy. *Intuitive graph traversals* Earlier I promised a surprise. Here it is. There are many ways to traverse general graphs. None seem intuitive. But consider *any* DAG created from the outline. *Aha*: The DAG's outline order is an *easily understood* ordering of the corresponding graph! *Summary* Database Access Plugins can (and should!) convert the complex results of queries to an organized outline. Outlines with six levels can represent millions of nodes. There are *many* ways of creating results outlines. DAPs might prefer specific organizations, but such choices are beyond the scope of the present discussion. The outline order of an organizer outline is an *easily understood* ordering of the corresponding graph! This post concludes my present thoughts about databases and large outlines. I plan no further Engineering Notebook posts on this topic. Edward -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to leo-editor+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/66accd47-f6ec-47f1-9c0c-e0511933a619n%40googlegroups.com.
