Database evaluation of anchored length-limited path expressions

• US 10,223,475 B2
• Filed: 08/31/2016
• Issued: 03/05/2019
• Est. Priority Date: 08/31/2016
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Johnson, Theodore, Shkapenyuk, Vladislav, Kanza, Yaron
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US15/253,591
• Publication Number:
  US 20180060396A1
• Time in Patent Office: 916 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method includes parsing a regular pathway expression into fragments including an anchored fragment and at least one other fragment. A number of the fragments is based on at least a length limitation of the regular pathway expression. The method includes generating an operator directed acyclic graph (DAG) including non-operator nodes, operator nodes, and a root based on at least the anchored fragment. The method includes removing, from the operator DAG, at least one of the non-operator nodes and connecting a first operator node to a second operator node of the operator nodes. The first operator node includes an edge into the at least one removed non-operator node, and the second operator node includes an edge from the at least one removed node. The method includes executing the operator DAG on a graph database to return a pathway set comprising at least one pathway that satisfies the regular pathway expression.

Claims

1. A system comprising:

a graph database representative of a network inventory;

a processor communicatively coupled to the graph database;

a user input communicatively coupled to the processor;

memory storing instructions that cause the processor to effectuate operations, the operations comprising;

receiving, via the user input, a database query comprising a regular pathway expression;

parsing the regular pathway expression into fragments, the fragments comprising an anchored fragment and at least one other fragment, a number of the fragments based on at least a length limitation of the regular pathway expression;

generating an operator directed acyclic graph (DAG) based on at least the fragments, the operator DAG comprising non-operator nodes, operator nodes, and a root, wherein the root is based on at least the anchored fragment;

removing, from the operator DAG, at least one of the non-operator nodes;

connecting, within the operator DAG, a first operator node of the operator nodes to a second operator node of the operator nodes, wherein the first operator node comprises a first edge into the removed at least one non-operator node and wherein the second operator node comprises a second edge from the removed at least one non-operator node; and

executing the operator DAG on the graph database to return a pathway set comprising at least one pathway that satisfies the regular pathway expression.

2. The system of claim 1, wherein the operator nodes include a selection node.

3. The system of claim 2, the operations further comprising:

determining that no pathway from the selection node to a third operator node of the operator nodes exists; and

prior to executing the operator DAG on the graph database, removing the third operator node from the operator DAG.

4. The system of claim 1, wherein generating the operator DAG further comprises:

for each of the fragments, applying a respective transformation to generate a respective sub-DAG,

wherein the operator DAG is based on at least the respective sub-DAGs.

5. The system of claim 4, wherein generating the operator DAG further comprises:

generating an operator DAG comprising at least a first placeholder associated with the anchored fragment and at least a second placeholder associated with the at least one other fragment,

connecting the first placeholder to the second placeholder with at least one non-operator node; and

replacing the first placeholder and the second placeholder with the respective sub-DAGs.

6. The system of claim 4, wherein the operator DAG comprises the respective sub-DAGs, and wherein a first sub-DAG of the respective sub-DAGs is connected to another sub-DAG of the respective sub-DAGs.

7. The system of claim 1, wherein the at least one other fragment comprises a non-anchored fragment.

8. The system of claim 1, wherein the at least one other fragment comprises another anchored fragment.

9. A method, comprising:

parsing a regular pathway expression into a plurality of fragments comprising an anchored fragment and at least one other fragment, a number of the fragments based on at least a length limitation of the regular pathway expression;

for each of the plurality of fragments, applying a respective transformation to generate a respective sub-director acyclic graph (sub-DAG),

generating an operator directed acyclic graph (DAG) based on at least the respective sub-DAGs, the operator DAG comprising a non-operator node, an operator node, and a root, wherein the root is based on at least the anchored fragment, wherein generating the DAG based on at least the respective sub-DAGS comprises;

generating the operator DAG comprising at least a first placeholder associated with the anchored fragment and at least a second placeholder associated with the at least one other fragment,

connecting the first placeholder to the second placeholder with at least one non-operator node; and

replacing the first placeholder and the second placeholder with the respective sub-DAGs;

removing, from the operator DAG, the non-operator node; and

executing the operator DAG on a graph database to return a pathway set comprising at least one pathway that satisfies the regular pathway expression.

10. The method of claim 9, wherein the operator node includes a selection node.

11. The method of claim 10, further comprising:

determining that no pathway from the selection node to a second operator node of the operator nodes exists; and

prior to executing the operator DAG on the graph database, removing the second operator node from the operator DAG.

12. The method of claim 9, wherein the operator DAG comprises the respective sub-DAGs, and wherein a first sub-DAG of the respective sub-DAGs is connected to another sub-DAG of the respective sub-DAGs.

13. The method of claim 9, wherein the at least one other fragment comprises a non-anchored fragment.

14. The method of claim 9, wherein the at least one other fragment comprises another anchored fragment.

15. A method comprising:

parsing a regular pathway expression into fragments, the fragments comprising an anchored fragment and at least one other fragment, a number of the fragments based on at least a length limitation of the regular pathway expression;

recursively applying one or more transformations to the fragments to generate an operator directed acyclic graph (DAG), the operator DAG comprising at least one non-operator node and at least one operator node;

eliminating an extraneous node of the at least one non-operator node from the operator DAG;

connecting, within the operator DAG, a first operator node of the at least one operator node to a second operator node of the at least one operator node, wherein the first operator node comprises a first edge into the extraneous node and wherein the second operator node comprises a second edge from the extraneous node; and

executing the operator DAG on a graph database to return a pathway set comprising at least one pathway that satisfies the regular pathway expression.

16. The method of claim 15, wherein the at least one other fragment comprises at least one of a non-anchored fragment or another anchored fragment.

17. The method of claim 15, further comprising:

determining that no pathway from a selection node to a third operator node of the operator nodes exists, wherein the third operator node comprises the extraneous node.