...
The above sections only partly describe the current and proposed solutions. In both casesthe existing solution, a CPS path query is actually sent as two multiple database queries:
- The first SQL query performs the CPS path query.
- The second SQL query fetches Additional SQL queries fetch the descendant nodes, if required.
- Alternatively, if an ancestor CPS path was provided, the second SQL query would fetch the ancestors (and their descendants if required).
...
Recursive SQL query
...
to fetch descendants
The , while the proposed solution will use recursive SQL to fetch descendants of fragment returned from the CPS path query:
| Code Block | ||
|---|---|---|
| ||
WITH RECURSIVE descendant_search AS (
SELECT id, 0 AS depth
FROM fragment
WHERE id IN (:fragmentIds)
UNION
SELECT child.id, depth + 1
FROM fragment child INNER JOIN descendant_search ds ON child.parent_id = ds.id
WHERE depth <= :maxDepth
)
SELECT f.id, anchor_id AS anchorId, xpath, f.parent_id AS parentId, CAST(attributes AS TEXT) AS attributes
FROM fragment f INNER JOIN descendant_search ds ON f.id = ds.id |
...
Proof of Concept
A proof of concept (poc) implementation was developed so that performance could be compared against existing Cps Path query algorithms.
...
| Fetch descendants | Omit Descendants | Direct Descendants | All Descendants |
|---|---|---|---|
| Query | /openroadm-devices/openroadm-device[@status="success"] | /openroadm-devices/openroadm-device[@status="success"] | /openroadm-devices/openroadm-device[@status="success"] |
| Comparison graph |
|
|
|
| Graph detail |
|
|
|
Time complexity of | Unclear, as there is very high variance. Likely O(N). | O(N2) | O(N2) |
| Time complexity of proposed solution | O(N) | O(N) | O(N) |
Why does the existing solution have worst case quadratic complexity
...
?
The reason the existing solution is quadratic time when fetching descendants is because the path query translates into a number of SQL queries:
- An SQL query that returns nodes matching query criteria - O(N)
- For each node returned from query 1: issue an SQL query to fetch that node with descendants, using a LIKE operator - O(N).
The LIKE operator has linear time complexity, as all nodes' xpaths in a given anchor need to be examined.
In the case of a query that matches all N nodes, we are issuing 1+N queries, each with complexity O(N). Thus the overall complexity is O(N2).
...