## Diagram Set: Logical Query Decomposition Patterns ### Overview The image displays a collection of 14 distinct diagrams arranged in a grid pattern (4 rows, with the last row containing 2 diagrams and a legend). Each diagram is labeled with a short alphanumeric code (e.g., "1p", "2i", "pin") and illustrates a transformation from an initial logical query structure (top) to a decomposed or executed form (bottom), indicated by a large downward-pointing arrow. The diagrams use a consistent visual language of colored shapes and symbols to represent entities, relations, and logical operations, likely in the context of knowledge graph querying or semantic reasoning. ### Components/Axes There are no traditional chart axes. The components are defined by a legend located in the bottom-right corner of the image. **Legend (Bottom-Right):** * **Green Circle (r):** "Projection with Relation r" * **Orange Circle (e):** "Question Entities" * **Orange Square (A):** "Answer Entities" * **Blue Circle (Λ):** "Intersection over the entity sets" * **Purple Circle (V):** "Union over the entity sets" * **Pink Circle (¬):** "Negation of a relation" **Diagram Labels (Top of each diagram):** The 14 diagrams are labeled as follows, reading left-to-right, top-to-bottom: 1. **1p** 2. **2p** 3. **3p** 4. **2i** 5. **3i** 6. **ip** 7. **pi** 8. **2u** 9. **up** 10. **2in** 11. **3in** 12. **inp** 13. **pin** 14. **pni** ### Detailed Analysis Each diagram follows a pattern: an initial query graph at the top transforms into a set of simpler, executable sub-queries at the bottom. The transformation is indicated by a large, white, downward-pointing arrow. **Diagram-by-Diagram Breakdown:** 1. **1p (Single Projection):** * **Initial:** `e1 -> r1 -> A` * **Transformed:** `e1 -> r1 -> A1` (A single sub-query). 2. **2p (Two-hop Projection):** * **Initial:** `e1 -> r1 -> r2 -> A` * **Transformed:** Two sub-queries: `e1 -> r1 -> A1` and `A1 -> r2 -> A`. 3. **3p (Three-hop Projection):** * **Initial:** `e1 -> r1 -> r2 -> r3 -> A` * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `A1 -> r2 -> A2`, `A2 -> r3 -> A`. 4. **2i (Two-entity Intersection):** * **Initial:** Two paths (`e1 -> r1` and `e2 -> r2`) converge via an Intersection (Λ) to `A`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, and `A1, A2 -> Λ -> A`. 5. **3i (Three-entity Intersection):** * **Initial:** Three paths (`e1 -> r1`, `e2 -> r2`, `e3 -> r3`) converge via an Intersection (Λ) to `A`. * **Transformed:** Four sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, `e3 -> r3 -> A3`, and `A1, A2, A3 -> Λ -> A4`. 6. **ip (Intersection then Projection):** * **Initial:** Two paths (`e1 -> r1`, `e2 -> r2`) intersect (Λ), then project via `r3` to `A`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, `A1, A2 -> Λ -> A3`, and `A3 -> r3 -> A`. 7. **pi (Projection then Intersection):** * **Initial:** Two paths: one is `e1 -> r1 -> r2`, the other is `e2 -> r3`. They intersect (Λ) to `A`. * **Transformed:** Four sub-queries: `e1 -> r1 -> A1`, `A1 -> r2 -> A2`, `e2 -> r3 -> A3`, and `A2, A3 -> Λ -> A4`. 8. **2u (Two-entity Union):** * **Initial:** Two paths (`e1 -> r1`, `e2 -> r2`) converge via a Union (V) to `A`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, and `A1, A2 -> V -> A`. 9. **up (Union then Projection):** * **Initial:** Two paths (`e1 -> r1`, `e2 -> r2`) unite (V), then project via `r3` to `A`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, `A1, A2 -> V -> A3`, and `A3 -> r3 -> A`. 10. **2in (Two-entity Intersection with Negation):** * **Initial:** Two paths: `e1 -> r1` and `e2 -> r2 -> ¬` (negation). They intersect (Λ) to `A`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> ¬r2 -> A2`, and `A1, A2 -> Λ -> A`. 11. **3in (Three-entity Intersection with Negation):** * **Initial:** Three paths: `e1 -> r1`, `e2 -> r2`, `e3 -> r3 -> ¬`. They intersect (Λ) to `A`. * **Transformed:** Four sub-queries: `e1 -> r1 -> A1`, `e2 -> r2 -> A2`, `e3 -> ¬r3 -> A3`, and `A1, A2, A3 -> Λ -> A4`. 12. **inp (Intersection with Negation, then Projection):** * **Initial:** Two paths (`e1 -> r1`, `e2 -> r2 -> ¬`) intersect (Λ), then project via `r3`. * **Transformed:** Three sub-queries: `e1 -> r1 -> A1`, `e2 -> ¬r2 -> A2`, `A1, A2 -> Λ -> A3`, and `A3 -> r3 -> A`. 13. **pin (Projection, then Intersection with Negation):** * **Initial:** Two paths: one is `e1 -> r1 -> r2 -> ¬`, the other is `e2 -> r3`. They intersect (Λ) to `A`. * **Transformed:** Four sub-queries: `e1 -> r1 -> A1`, `A1 -> ¬r2 -> A2`, `e2 -> r3 -> A3`, and `A2, A3 -> Λ -> A4`. 14. **pni (Projection, Negation, then Intersection):** * **Initial:** Two paths: one is `e1 -> r1 -> r2`, the other is `e2 -> r3 -> ¬`. They intersect (Λ) to `A`. * **Transformed:** Four sub-queries: `e1 -> r1 -> A1`, `A1 -> r2 -> A2`, `e2 -> ¬r3 -> A3`, and `A2, A3 -> Λ -> A4`. ### Key Observations * **Naming Convention:** The labels appear to be abbreviations describing the query structure: `p` for projection/hop, `i` for intersection, `u` for union, `n` for negation. The number indicates the count (e.g., `2i` = two-entity intersection). * **Consistent Transformation:** Every diagram shows a complex query being decomposed into a sequence of simpler, likely executable, sub-queries. The final sub-query always produces the ultimate answer `A`. * **Logical Operators:** The diagrams explicitly model core logical operations (Intersection Λ, Union V, Negation ¬) as nodes within the query graph. * **Color Coding:** Strict adherence to the legend's color scheme is maintained throughout all diagrams for visual consistency. ### Interpretation This image serves as a visual taxonomy or reference sheet for **logical query patterns over knowledge graphs or semantic networks**. It demonstrates how complex queries involving multi-hop paths, set operations (intersection, union), and negation can be systematically decomposed into a series of simpler, executable sub-queries. The diagrams likely illustrate the operational semantics of a query language or reasoning system. The transformation from top to bottom represents the **query planning or rewriting phase**, where a high-level logical query is broken down into a sequence of basic graph traversal operations (projections) and set operations. This is a fundamental concept in database theory, semantic web technologies (like SPARQL), and neuro-symbolic AI, where symbolic queries are executed over structured knowledge bases. The presence of negation (`¬`) is particularly significant, as it introduces the concept of "non-existence" or "exclusion" into the query logic, which is more complex to implement than positive projections. The set of diagrams provides a comprehensive catalog of common query shapes, serving as a valuable reference for understanding, designing, or implementing systems that perform logical reasoning over graph-structured data.