Complexity of finding maximally-contained plans (Certain answers)
Source inversion approach has poly-time complexity for the case considered in EMERAC
Complexity doesn’t depend on the query
- Can handle recursive queries just as easily
Complexity does change if the sources are not “conjunctive queries”
- Sources as unions of conjunctive queries (NP-hard)
- Sources as recursive queries (Undecidable)
Complexity also changes based on Open vs. Closed world assumption