In this project you will implement three core algorithms that together form an efficient pipeline for evaluating conjunctive queries:
compute_tree_decomposition— find an optimal fractional hypertree decomposition of a query using variable elimination.worst_case_optimal_join— evaluate a set of relations using the Generic Join algorithm.evaluate_tree_decomposition— evaluate a full conjunctive query via Yannakakis' algorithm on a tree decomposition.
All of your work goes in student.py. Tests go in test_student.py.
pip install -r requirements.txt.
├── student.py # YOUR CODE GOES HERE
├── test_student.py # YOUR TESTS GO HERE
│
├── query.py # Relation and ConjunctiveQuery classes (provided)
├── tree_decomposition.py # TreeDecomposition class (provided)
├── trie.py # Trie data structure (provided)
├── utils.py # Fractional edge cover LP solver (provided)
│
├── evaluate.py # Example driver script
├── data/ # CSV graph data for testing
│ ├── triangle/ # R.csv, S.csv, T.csv
│ └── four_cycle/ # R.csv, S.csv, T.csv, U.csv
└── requirements.txt
Relation(name, variables) — represents a database relation.
rel.variables— list of variable names, e.g.["x", "y"]rel.data— list of row dicts, e.g.[{"x": 1, "y": 2}, ...]rel.add_data(rows)— append rowsrel.load_csv(filepath)— load data from a CSV file
ConjunctiveQuery(head, relations) — represents a query Q(head) :- R1(...), R2(...), ...
query.head— list of output variable namesquery.relations— list ofRelationobjectsquery.get_variables()— returns the set of all variables in the query body
TreeDecomposition(tree_edges, bag_to_variables, bag_to_relations)
tree_edges— list of(bag_id, bag_id)tuplesbag_to_variables— dict mappingbag_id -> set of variablesbag_to_relations— dict mappingbag_id -> list of relation namestd.bags— set of all bag IDstd.rooted_order(root=None)— returns(order, parent): a BFS traversal order and a dict mapping each bag to its parent (Nonefor the root)td.get_neighbors(bag)— returns the set of adjacent bagstd.variables_to_bags— dict mappingvariable -> set of bag_idscontaining it
Trie(relation, variable_order) — builds a trie index over the rows of a Relation.
trie.lookup(prefix)— returns the set of values at the next level given a list of prefix valuestrie.contains(values)— returnsTrueif the full tuple exists
fractional_edge_cover_value(variables, query) — returns the cover number ρ* (minimum total weight).
Search for raise NotImplementedError to find each stub.
Test whether tree_decomposition satisfies the necessary properties of a TD.
Compute an optimal hypertree decomposition (i.e. a TD with optimal fractional hypertree width).
Implement the Generic Join algorithm.
Evaluate the tree decomposition by materializing the bags then running Yannakakis' algorithm.
The test file contains three empty test classes with TODO comments:
TestValidateTreeDecomposition- testvalidate_tree_decompositionwith few examples of valid and invalid TDs.TestTreeDecomposition— testcompute_tree_decomposition. Usevalidate_tree_decompositionto check structural correctness. Consider also checking that the fractional hypertree width is optimal for known queries.TestWCOJ— testworst_case_optimal_joindirectly with small hand-crafted examples.TestEvaluateQuery— end-to-end tests. The helperbrute_force_join(query)is provided as a correctness oracle.
Run your tests with:
python -m pytest test_student.py -vpython evaluate.pyThis runs two example queries (triangle and path) end-to-end and prints the results.
For the core tree decomposition optimizer, there are a few approaches to take:
-
Variable Elimination (also known as Bucket Elimination): In this approach, we choose an order on the variables in our query that don't appear in the head. In order, we try to project them out one-at-a-time, and this corresponds to a TD where each bag projects away one variable. The tricky part is identifying which relations correspond to which bag and how to arrange the bags into a tree. Section 3.1 of this paper provides a good description as does Section 2 of this paper.
-
Candidate Bag -> Candidate Tree Decomposition: In this approach, we start by selecting a set of candidate bags (e.g. bags which have an AGM bound of <c), then we try to construct a TD from that set of bags. If no TD can be constructed, we create a larger candidate set and try again. Here, the algorithm has two phases 1) the candidate set generation and 2) the tree construction algorithm. This paper takes that approach and describes it in Section 3 of this paper.
-
Hypergraph Separators: In this approach, we start by identifying all "balanced separators" of the hypergraph. These are variable sets that split the query into roughly equal sized pieces. We treat each balanced separator as the root node of a TD, then we recurse on the now disconnected sub-queries. Their balanced separators connected as child bags of the first one, and so on. This is described in this paper.
I would recommend variable elimination as a starting place, but all of these algorithms are cool!
For Generic Join, the following resources are available:
- The lecture slides from our join algorithms lecture
- These two blog posts (1, 2)
- The original paper
I will run an additional test suite to grade your implementation's correctness & optimality. 50% of the grade will be based on this check. In addition, we will schedule short in-person code reviews to discuss your implementation and the design decisions. 50% of your grade will be based on the code reviews.
Further, extensions to this work that go significantly beyond the required implementation will be eligible for up to 25% extra credit! These extensions could:
- Apply the technique to another problem (e.g. optimizing linear algebra/tensor algebra).
- Significantly improve the scalability of the optimizer.
- Significantly improve the runtime of the execution layer (e.g. the WCOJ and Yannakakis' Algorithm).
- Use an improved cost function to guide the selection of the tree decomposition. For example, this could leverage better statistics about the input relations like degree constraints.
- Provide detailed benchmarks for the runtime of the optimization and evaluation on different queries and datasets.
- Whatever else you can think of!