Example



Enhanced Support for Hierarchy Use CasesGerald Krause, SAP SE, September 2019This is a minor revision with a few corrections in section 5.1. They are marked with “V1.6.3” comments.This is a minor revision with a few clarifications and comments to simplify document walkthrough. They are marked with “V1.6.2” comments.This is a minor revision with a few clarifications marked with “V1.6.1” comments.MotivationThe Data Aggregation extension of OData V4 introduces leveled and recursive hierarchies. This document describes a proposal to add further functions to the specification to enhance handling of recursive hierarchies.Hierarchies capabilities address use cases of increasing complexity:A service describes the hierarchy structure with metadata.A client filters nodes in the hierarchy set based on their position in the hierarchy.A client retrieves well-formed sub-hierarchies: Retrieve a thinned-out, still well-formed hierarchy: After restricting the node set to those matching certain filter criteria, extend this result set with their ancestors in the hierarchy.Retrieve one or more sub-hierarchies: After restricting the node set to those matching certain filter criteria, extend this result set with their descendants in the bine a and b.A client retrieves a node result set in a tree-aware order, see client asks for values aggregated along node paths in the (thinned-out) (sub-)hierarchy.The current committee specification 02 of the extension covers the first two points:Ad 1: Annotation term RecursiveHierarchy, section 6.3.2Ad 2: Functions to filter recursive hierarchies: isroot, isdescendant, isancestor, issibling, isleaf, section 6.3.2.1For leveled hierarchies, all of the above use cases can be realized with a sequence of filter/groupby/aggregate/orderby transformations. This document proposes new $apply transformations to address use cases 3-5 for recursive hierarchies. Special formatting applied in this document:Non-normative comments in the new specification text and emphasized terms are set in Italics ExampleThe following sections include example requests to illustrate the usage of hierarchy capabilities. They are based on the data model from the specification:Side notes: Let us remove the ellipsis from SalesOrganizations entity set such that it is complete and results for requests using this hierarchy can be reproduced coherently. In the data model in section 2.2 of the specification add a collection-valued navigation property from SalesOrganization to Sales, which will be used for illustrating aggregation along a hierarchy.The entity type for SalesOrganizations is annotated with term RecursiveHierarchy from the Data Aggregation vocabulary as described in the specification, section 6.3.3:<Annotations Target="SalesModel.SalesOrganization">? <Annotation Term="Aggregation.RecursiveHierarchy"????????????? Qualifier="SalesOrgHierarchy"> ? <Record>????? <PropertyValue Property="NodeProperty" ???????????????????? PropertyPath="ID" />????? <PropertyValue Property="ParentNavigationProperty" ???????????????????? PropertyPath="Superordinate" />??? </Record>??</Annotation></Annotations>DefinitionsAligning the capabilities offered for recursive and leveled hierarchies is facilitated by defining the terms used to describe these capabilities. Therefore, the following existing sections 6.3, 6.3.1 and 6.3.2 are extended with definitions for the relevant terms. Section 6.3 HierarchiesA hierarchy is an arrangement of nodes represented as entity instances being “above”, “below”, or “at the same level as” one another. A hierarchy can be leveled or recursive.Section 6.3.1 Leveled HierarchyA leveled hierarchy has a fixed number of levels each of which is represented by a groupable property. The values of a lower-level property depend on the property value of the level above. A leveled hierarchy can be defined for instances of an entity or complex type and is described with the term LeveledHierarchy that lists the properties used to form the hierarchy.The order of the collection is significant: it lists the properties representing the levels, starting with the root level (coarsest granularity) down to the lowest level of the hierarchy.The term LeveledHierarchy can only be applied to entity or complex types, and the applying Annotation element MUST specify the Qualifier attribute. The value of the Qualifier attribute can be used to reference the hierarchy in grouping with rollup.In addition to annotated leveled hierarchies, a request can define an unnamed leveled hierarchy as a list of property paths. The first path in the list is the root of the hierarchy defining the coarsest granularity and MUST either be a single-valued property path or the virtual property $all. The other paths MUST be singe-valued property paths and define consecutively finer-grained levels of the hierarchy. A node is an instance with values for the first left N>1 properties of the leveled hierarchy. It has a parent node that is an instance consisting of the first N-1 level properties with the same values. A leveled hierarchy is a collection of such nodes with distinct values for all groupable properties at all hierarchy levels.See section 3.10.2 for an example how to generate a leveled hierarchy from an entity collection with a combination of groupby and rollup.Section 6.3.2 Recursive HierarchyA recursive hierarchy organizes the values of a single property of an entity type entities of a collection as nodes of a tree structure. This structure does not need to be as uniform as a leveled hierarchy. It is described by a complex term RecursiveHierarchy with the properties:The NodeProperty contains the path to the identifier of the node.The ParentNavigationProperty allows navigation to the instance representing the parent node. Its type MUST be the entity type annotated with this term, and it MUST be nullable.The optional ChildrenNavigationProperty allows navigation to the instances representing children nodes. Its type MUST be a collection of the entity type annotated with this term.The optional DistanceFromRootProperty contains the path to a property that contains the number of edges between the node and the root node.The optional IsLeafProperty contains the path to a Boolean property that indicates whether the node is a leaf of the hierarchy.The term RecursiveHierarchy can be applied to entity types, and the applying Annotation element MUST specify the Qualifier attribute. The value of the Qualifier attribute can be used to reference the hierarchy in other contexts.A node is an instance of an entity type annotated with RecursiveHierarchy. It has may have a parent node that is the target instance reached via the ParentNavigationProperty. A recursive hierarchy is a collection of such nodes with distinct node identifiers and no cycles in the traversal of parent or children links..A node without parent node is a root node, a nodes with the same parent node are is a child nodes of that nodeits parent node, a node without child nodes is a leaf node. Nodes with the same parent node are sibling nodes. The descendants of a node are the set comprising its child nodes, their child nodes, and so on, up to and including all leaf nodes that can be reached. The ancestors of a node are the set comprising its parent node, the parent of its parent node, and so on, up to and including a root node that can be reached.Retrieving Well-Formed Sub-HierarchiesThis section introduces new $apply transformations for use case under point 3.Ancestors of Nodes This section introduces a new $apply transformation for use case 3a: An OData request with a filter expression restricts the instances to be included in the result. If instances are related to a hierarchy, a client may be interested in an extended result representing the thinned-out hierarchy that comprises all nodes on the paths from the instances matching the filter criteria to the root nodes. For this purpose, the ancestors of the instances matching the filter criteria are to be determined and then added to this set.The ancestors transformation determines ancestors from the recursive hierarchy provided in the input set. The first parameter specifies the hierarchy structure to apply and takes the value of a Qualifier attribute of an annotation with term RecursiveHierarchy. The second parameter receives a filter expression to qualify start nodes in the input set for which ancestors are to be determined. Optionally, keep start may be provided as last parameter ensures that to include the start nodes are included in the returned result.Node entities in the input set passed to ancestors must have values for the properties referenced by NodeProperty and ParentNavigationProperty in the RecursiveHierarchy term annotated to the entity’s type whose qualifier is passed as first parameter.Transformation ancestors first applies the filter expression in the second parameter to the input set to determine the start nodes. For each start node, ancestors then adds all instances ofin the input set to the result that are ancestors of that node with respect to the hierarchy structure specified as first parameter omitting duplicates. Example: Sales org hierarchy restricted to orgs with 'East' or 'Central' in the namein the U.S.GET ~/SalesOrganizations?$apply= ancestors(SalesOrgHierarchy, filter(contains(Name,'East') or contains(Name,'Central'))results in{ "@odata.context": "$metadata#SalesOrganizations", "value": [ { "ID": "EMEA", "SuperOrdinate@navigationlink": "SalesOrganization('Sales')", "Name": "EMEA" }, { "ID": "US", "SuperOrdinate@navigationlink": "SalesOrganization('Sales')", "Name": "US" }, { "ID": "Sales", "SuperOrdinate@navigationlink": null, "Name": "Sales" } ]}Ordering the nodes in the result is up to the service and may be controlled with a subsequent traverse transformation. Descendants of NodesThis section introduces a new $apply transformation for use case 3b: An OData request with a filter expression restricts the entities to be included in the result. If entities are related to a recursive hierarchy, a client may be interested in an extended result also comprising the sub-hierarchies rooted at the entities matching the filter criteria. For this purpose, the input set is supplemented with descendants of the entities matching the filter criteria. The descendants transformation determines descendants from a recursive hierarchy provided in the input set. The first parameter specifies the hierarchy structure to apply and takes the value of a Qualifier attribute of an annotation with term RecursiveHierarchy. The second parameter receives a filter expression to qualify start nodes in the input set for which the descendants are to be determined. An optional third parameter is an integer greater than 0 and specifies the maximum number of edges to consider on the paths from the start nodes. As a last parameter, keep start may be specified to include the start nodes in the returned result.Node entities in the input set passed to descendants must have values for the properties referenced by NodeProperty and ParentNavigationProperty in the RecursiveHierarchy term annotated to the entity’s type whose qualifier is passed as first parameter.Transformation descendants first applies the filter expression in the second parameter to the input set to determine the start nodes. For each start node, descendants then adds all instances ofin the input set to the result that are descendants of that node with respect to the hierarchy structure specified as first parameter and the maximum number of edges to consider specified as third parameter..Example: Sub-hierarchies of sales organizations with name 'US'.GET ~/SalesOrganizations?$apply= descendants(SalesOrgHierarchy,filter(Name eq 'US'),keep start)results in{ "@odata.context": "$metadata#SalesOrganizations", "value": [ { "ID": "US West", "SuperOrdinate@navigationlink": "SalesOrganization('US')", "Name": "US West" }, { "ID": "US", "SuperOrdinate@navigationlink": "SalesOrganization('Sales')", "Name": "US" }, { "ID": "US East", "SuperOrdinate@navigationlink": "SalesOrganization('US')", "Name": "US East" } ]}Ordering the nodes in the result is up to the service and may be controlled with a subsequent traverse transformation. Retrieving Hierarchy Nodes in Tree OrderThis section introduces a new $apply transformation for use case 4.The traverse transformation returns the nodes from the input set traversed in the specified tree order. It takes the value of a Qualifier attribute of an annotation with term RecursiveHierarchy as first parameter. The second parameter specifies the order in which a node of the input set appears in the result. If it is preorder, then it is output before its children nodes; if it is postorder, then it is output after its children. Node entities in the input set passed to traverse must have values for the properties referenced by NodeProperty and ParentNavigationProperty in the RecursiveHierarchy term annotated to the entity’s type whose qualifier is passed as first parameter.traverse retains the order of sibling nodes in the input set, hence this order can optionally be controlled with a previously applied orderby transformation. If the input set consists of multiple disconnected node sets, the order of their root nodes in the input set determines the order in which their subtrees are added to the result.Example: Sub-hierarchy of sales orgs in 'US' to those with 'East' in the nameGET ~/SalesOrganizations?$apply= descendants(SalesOrgHierarchy,filter(Name eq 'US'),keep start) /ancestors(SalesOrgHierarchy,filter(contains(Name,'East')),keep start) /traverse(SalesOrgHierarchy,preorder)results in{ "@odata.context": "$metadata#SalesOrganizations", "value": [ { "ID": "Sales", "Name": "Sales" }, { "ID": "US", "SuperOrdinate@navigationlink": "SalesOrganization('Sales')", "Name": "US" }, { "ID": "US East", "SuperOrdinate@navigationlink": "SalesOrganization('US')", "Name": "US East" } ]}Aggregating Along Hierarchy PathsAggregation along a leveled hierarchy is already covered in section 3.10.2 in the current specification by the combination of groupby with rollup. The following section is a proposal to extend 3.10.2 for addressing aggregation along a recursive hierarchy (use case 5).Section 3.10.2 Grouping with rollup and $allThe rollup grouping operator allows applying set transformations to instances of an input set organized in a hierarchy. It can be used instead of a property path in the first parameter of groupby.The rollup grouping operator has two overloads, depending on the number of parameters. If used with one parameter, the parameter MUST be the value of the Qualifier attribute of an annotation with term LeveledHierarchy or term RecursiveHierarchy. This named hierarchy is used for grouping instances. If used with two or more parameters, it defines an unnamed leveled hierarchy (link to section 6.3.1 Leveled Hierarchy). This unnamed hierarchy is used for grouping instances.After resolving named hierarchies, the same property path MUST NOT appear more than once.Grouping with rollup is processed for leveled hierarchies using the following equivalence relationships, in which pn is a property path, T is a transformation, the ellipsis stands in for zero or more property paths, and R stands in for zero or more rollup operators or property paths:groupby((rollup(p1,…,pn-1,pn),R),T) is equivalent to concat(groupby((p1,…,pn-1, pn,R),T), groupby((rollup(p1,…,pn-1),R),T))groupby((rollup(p1,p2),R),T) is equivalent to concat(groupby((p1,p2,R),T), groupby((p1,R),T))groupby((rollup($all, p1),R),T) is equivalent to concat(groupby((p1,R),T),groupby((R),T))groupby((rollup($all,p1)),T) is equivalent to concat(groupby((p1),T),T)Loosely speaking groupby with rollup applied to a leveled hierarchy splits the input set into groups using all grouping properties, then removes the last property from one of the hierarchies and splits it again using the remaining grouping properties. This is repeated until all of the hierarchies have been used up.Example SEQ Example \* ARABIC 26: rolling up two hierarchies, the first with two levels, the second with three levels:(rollup(p1,1,p1,2),rollup(p2,1,p2,2,p2,3)) will result in the six groupings (p1,1,p1,2,p2,1,p2,2,p2,3) (p1,1,p1,2,p2,1,p2,2) (p1,1,p1,2,p2,1) (p1,1,p2,1,p2,2,p2,3) (p1,1,p2,1,p2,2) (p1,1,p2,1) Note that rollup stops one level earlier than GROUP BY ROLLUP in TSQL, see REF Rollup \h \* MERGEFORMAT [TSQL ROLLUP], unless the virtual property $all is used as the hierarchy root level. Loosely speaking the root level is never rolled up.Example SEQ Example \* ARABIC 27: answering the second question in section REF _Ref354053854 \r \h \* MERGEFORMAT 2.4GET ~/Sales?$apply=groupby((rollup(Customer/Country,Customer/Name), rollup(Product/Category/Name,Product/Name), Currency/Code), aggregate(Amount with sum as Total))results in seven entities for the finest grouping level{"@odata.context":"$metadata#Sales(Customer(Country,Name),Product(Category(Name),Name),Total,Currency(Code))", "value": [ { "@odata.id": null, "Customer": { "Country": "USA", "Name": "Joe" }, "Product": { "Category": { "Name": "Non-Food" }, "Name": "Paper" }, "Total": 1, "Currency": { "Code": "USD" } }, ...plus additional fifteen rollup entities for subtotals: five without customer name { "@odata.id": null, "Customer": { "Country": "USA" }, "Product": { "Category": { "Name": "Food" }, "Name": "Sugar" }, "Total": 2, "Currency": { "Code": "USD" } }, ...six without product name { "@odata.id": null, "Customer": { "Country": "USA", "Name": "Joe" }, "Product": { "Category": { "Name": "Food" } }, "Total": 6, "Currency": { "Code": "USD" } }, ...and four with neither customer nor product name { "@odata.id": null, "Customer": { "Country": "USA" }, "Product": { "Category": { "Name": "Food" } }, "Total": 14, "Currency": { "Code": "USD" } }, ... ]}Note that the absence of one or more properties of the result structure imposed by the surrounding OData context allows distinguishing rollup entities from other entities.If rollup is used with the qualifier of a recursive hierarchy, node entities in the input set passed to rollup must have values for the properties referenced by NodeProperty and ParentNavigationProperty in the RecursiveHierarchy term annotated to the entity’s type whose qualifier is passed as first parameter.Grouping with rollup is processed for recursive hierarchies using the following equivalence relationships, in which RHQ is a qualifier of a RecursiveHierarchy annotation and nodeID is the property referenced in NodeProperty of that annotation , ri, 1≤i≤n, are the root nodes of the recursive hierarchy passed as input set, T is a transformation, R stands in for one or more rollup operators or property paths, and for a root node r let p1, …, pkdenote the properties in r with values v1, …, vk. Finally, compute_p stands for a transformation that does the same as compute, but for a given instance of the input set considers only those compute expressions whose alias is not already used for a property of that instance (their value is preserved).The result of groupby((rollup(RHQ),R),T) is defined asconcat(descendants(RHQ, r1,keep start)/groupby((rollup(RHQ),R),T), … descendants(RHQ, rn,keep start)/groupby((rollup(RHQ),R),T))concat(groupby((rollup(RHQ),R),T) for root node r1, … groupby((rollup(RHQ),R),T) for root node rn)where the result of groupby((rollup(RHQ),R),T) for some root node r with m≥0 children nodes is defined as:If cjr, 101≤j≤m, having nodeIDcjr as their nodeID property value, denotes the non-empty set of child nodes of node r,is defined as: thengroupby((rollup(RHQ),R),T) for root node r is equivalent to concat(descendants(RHQ,filter($this eq r),keep start) /groupby((R),T)/compute_p(v1 as p1,…, vk as pk), descendants(RHQ,filter(nodeID eq nodeIDc1r$this eq c1r),keep start) /groupby((rollup(RHQ),R),T), … descendants(RHQ,filter(nodeID eq nodeIDcmr$this eq cmr),keep start) /groupby((rollup(RHQ),R),T))groupby((rollup(RHQ)),T) for root node r is equivalent to concat(descendants(RHQ,filter($this eq r),keep start) /T/compute_p(v1 as p1,…, vk as pk), descendants(RHQ,filter(nodeID eq nodeIDc1r$this eq c1r),keep start) /groupby((rollup(RHQ)),T), … descendants(RHQ,filter(nodeID eq nodeIDcmr$this eq cmr),keep start) /groupby((rollup(RHQ)),T))groupby((rollup(RHQ))) for root node r is equivalent to concat(descendants(RHQ,filter($this eq r),0,keep start) , descendants(RHQ,filter($this eq c1r),keep start) /groupby((rollup(RHQ))), … descendants(RHQ,filter($this eq cmr),keep start) /groupby((rollup(RHQ))))if r has no child nodes, thengroupby((rollup(RHQ),R),T) for root node r is equivalent to groupby((R),T)/compute(v1 as p1,…, vk as pk)groupby((rollup(RHQ)),T) for root node r is equivalent to T/compute(v1 as p1,…, vk as pk)Loosely speaking groupby with rollup processes the input set with a recursive hierarchy using these steps:For each node in the input set, it determines the set of all descendants of this node contained in the input set, plus the originating node itself,applies the transformation sequence to each set resulting in a new set of potentially different structure,ensures that the instance in each intermediate result set contains all structural properties with the correct values and all navigation links from the originating root node,concatenates the intermediate result sets into one result set.Example: Total number of sub-organizations for all organizations in the hierarchyGET ~/SalesOrganizations?$apply= groupby((rollup(SalesOrgHierarchy)), aggregate($count as OrgCnt)/compute(OrgCnt sub 1 as SubOrgCnt)) &$select=ID,Name,SubOrgCnt &$expand=Superordinate($select=ID)results in{ "@odata.context": "metadata#SalesOrganizations", "value": [ { "ID": "US West", "Name": "US West", "SubOrgCount": 0, "SuperOrdinate": { "ID": "US" } }, { "ID": "US East", "Name": "US East", "SubOrgCount": 0, "SuperOrdinate": { "ID": "US" } }, { "ID": "US", "Name": "US", "SubOrgCount": 2, "SuperOrdinate": { "ID": "Sales" } }, { "ID": "EMEA Central", "Name": "EMEA Central", "SubOrgCount": 0, "SuperOrdinate": { "ID": "EMEA" } }, { "ID": "EMEA", "Name": "EMEA", "SubOrgCount": 1, "SuperOrdinate": { "ID": "Sales" } }, { "ID": "Sales", "Name": "Sales", "SubOrgCount": 5, "SuperOrdinate": null } ]}Ordering of rollup instances within detail instances is up to the service and may be controlled with a subsequent orderby or traverse transformation or an $orderby. Highlight aggregation of amount w/ different currenciesExample: Total sales amounts for the hierarchy restricted to sales orgs with 'East' in the nameGET ~/SalesOrganizations?$apply= /groupby((rollup(SalesOrgHierarchy)), aggregate(Sales/Amount with sum as TotalAmount)) /ancestors(SalesOrgHierarchy,filter(contains(Name,'East')),keep start)results in{ "@odata.context": "$metadata#SalesOrganizations", "value": [ { "ID": "Sales", "Name": "Sales", "TotalAmount": 24 }, { "ID": "US", "Name": "US", "TotalAmount": 19, "SuperOrdinate@navigationlink": "SalesOrganization('Sales')" }, { "ID": "US East", "Name": "US East", "TotalAmount": 12, "SuperOrdinate@navigationlink": "SalesOrganization('US')" } ]}ClarificationsThis section lists changes to the Data Aggregation specification that came up during discussion of this document in the TC.Section 2.1 DefinitionsAdd definition: single-valued property path – property path ending in a single-valued primitive, complex, or navigation propertySection 3.10.1 Simple GroupingCreate a link from “single-valued property path” to term in 2.1 Definitions and remove “(path ending in a single-valued primitive, complex, or navigation property)”Data Aggregation Vocabulary<ComplexType Name="RecursiveHierarchyType"> <Property Name="NodeProperty" Type="Edm.PropertyPath" Nullable="false"> <Annotation Term="Core.Description" String="Property holding the hierarchy node value that must not be null" /> </Property> <Property Name="ParentNavigationProperty" Type="Edm.NavigationPropertyPath" Nullable="false"> <Annotation Term="Core.Description" String="Property for navigating to the parent node. Its type MUST be the entity type annotated with this term, and it MUST be nullable." /> </Property> <Property Type="Edm.NavigationPropertyPath" Name="ChildrenNavigationProperty" Nullable="true"> <Annotation Term="Core.Description" String="Property for navigating to the children nodes. Its type MUST be a collection of the entity type annotated with this term."/> </Property <Property Name="DistanceFromRootProperty" Type="Edm.PropertyPath" Nullable="true"> <Annotation Term="Core.Description" String="Property holding the number of edges between the node and the root node" /> </Property> <Property Name="IsLeafProperty" Type="Edm.PropertyPath" Nullable="true"> <Annotation Term="Core.RequiresType" String="Edm.Boolean" /> <Annotation Term="Core.Description" String="Property indicating whether the node is a leaf of the hierarchy" /> </Property></ComplexType> ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download