# US 2019/0377735 A1 · Defining subgraphs declaratively with vertex and edge filters > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0377735 A1 - Document ID: US20190377735A1 - Status: Published application - Kind: A1 - Application number: 16/548,687 - Filed: 2019-08-22 - Published: 2019-12-12 - Earliest claimed: 2017-05-10 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Alexander Weld; Korbinian Schmid; Sungpack Hong; Hassan Chafi; Hyungyu Shin - Web page: https://patentgrep.com/patent/US20190377735A1 ## CPC - G06F 16/24535: {of sub-queries or views} - G06F 16/248: Presentation of query results - G06F 16/252: {between a Database Management System and a front-end application} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques herein optimally distribute graph query processing across heterogeneous tiers. In an embodiment, a computer receives a graph query to extract a query result (QR) from a graph in a database operated by a database management system (DBMS). The graph has vertices interconnected by edges. Each vertex has vertex properties, and each edge has edge properties. The computer decomposes the graph query into filter expressions (FE's). Each FE is processed as follows. A filtration tier to execute the FE is selected from: the DBMS which sends at least the QR to a stream, a stream evaluator that processes the stream as it arrives without waiting for the entire QR to arrive and that stores at least the QR into memory, and an in-memory evaluator that identifies the QR in memory. A translation of the FE executes on the filtration tier to obtain vertices and/or edges that satisfy the FE. ## Claims ### Claim 1 A method comprising: executing a graph query to be applied to content of a computerized data store by: automatically decomposing the graph query into at least a first filter expression and a second filter expression; executing the first filter expression on a database management system (DBMS) tier that comprises a DBMS; executing the second filter expression on a second processing tier, wherein data in the second processing tier comprises data retrieved from the DBMS tier. ### Claim 2 (depends on 1) The method of claim 1 wherein said data retrieved from the DBMS tier comprises extensible markup language (XML). ### Claim 3 (depends on 1) The method of claim 1 wherein said executing the first filter expression on the DBMS tier comprises sending an XML query to the DBMS for execution. ### Claim 4 (depends on 1) The method of claim 1 wherein said executing the second filter expression on the second processing tier comprises: a) not storing said data in the second processing tier unless a streaming XML parser detects that said data in the second processing tier satisfies said second filter expression, and/or b) generating a logical graph or tree. ### Claim 5 (depends on 1) The method of claim 1 wherein: said data in the second processing tier comprises a first portion and a second portion; said executing the second filter expression on the second processing tier comprises concurrently processing the first portion and the second portion by respective cores of a processor. ### Claim 6 (depends on 1) The method of claim 1 wherein said executing the first filter expression on the DBMS tier and said executing the second filter expression on the second processing tier concurrently occur. ### Claim 7 (depends on 1) The method of claim 1 wherein said executing the second filter expression on the second processing tier comprises: a) a relational join, b) native object deserialization, b) unmarshalling said data in the second processing tier into data binding objects, c) a sliding window storing a portion of said data in the second processing tier, and/or d) detecting that said executing the second filter expression has quadratic complexity. ### Claim 8 (depends on 1) The method of claim 1 wherein the second filter expression is context free, and/or the first filter expression cannot be context free. ### Claim 9 (depends on 1) The method of claim 1 wherein the DBMS tier and the second processing tier reside on: separate computers, or a same computer. ### Claim 10 (depends on 1) The method of claim 1 wherein said data in the second processing tier exceeds available memory in the second processing tier. ### Claim 11 One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause: executing a graph query to be applied to content of a computerized data store by: automatically decomposing the graph query into at least a first filter expression and a second filter expression; executing the first filter expression on a database management system (DBMS) tier that comprises a DBMS; executing the second filter expression on a second processing tier, wherein data in the second processing tier comprises data retrieved from the DBMS tier. ### Claim 12 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said data retrieved from the DBMS tier comprises extensible markup language (XML). ### Claim 13 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said executing the first filter expression on the DBMS tier comprises sending an XML query to the DBMS for execution. ### Claim 14 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said executing the second filter expression on the second processing tier comprises: a) not storing said data in the second processing tier unless a streaming XML parser detects that said data in the second processing tier satisfies said second filter expression, and/or b) generating a logical graph or tree. ### Claim 15 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein: said data in the second processing tier comprises a first portion and a second portion; said executing the second filter expression on the second processing tier comprises concurrently processing the first portion and the second portion by respective cores of a processor. ### Claim 16 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said executing the first filter expression on the DBMS tier and said executing the second filter expression on the second processing tier concurrently occur. ### Claim 17 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said executing the second filter expression on the second processing tier comprises: a) a relational join, b) native object deserialization, b) unmarshalling said data in the second processing tier into data binding objects, c) a sliding window storing a portion of said data in the second processing tier, and/or d) detecting that said executing the second filter expression has quadratic complexity. ### Claim 18 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the second filter expression is context free, and/or the first filter expression cannot be context free. ### Claim 19 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the DBMS tier and the second processing tier reside on: separate computers, or a same computer. ### Claim 20 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said data in the second processing tier exceeds available memory in the second processing tier.