Defensive Points-To Analysis: Effective Soundness via Laziness
We present a defensive may-point-to analysis approach, which offers soundness even in the presence of arbitrary opaque code.
Authors: Yannis Smaragdakis, George Kastrinis´. 2018.
In Proceedings of the 32nd European Conference on Object-Oriented Programming (ECOOP ‘18).
We present a defensive may-point-to analysis approach, which offers soundness even in the presence of arbitrary opaque code: all non-empty points-to sets computed are guaranteed to be over-approximations of the sets of values arising at run time. A key design tenet of the analysis is laziness: the analysis computes points-to relationships only for variables or objects that are guaranteed to never escape into opaque code.
Worst-Case Optimal Join Algorithms: Techniques, Results and Open Problems
Worst-case optimal join algorithms are the class of join algorithms whose runtime match the worst-case output size of a given join query. While the first provably worst-case optimal join algorithm was discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory, constraint satisfaction, database theory, and geometric inequalities.
What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?
Recent works on bounding the output size of a conjunctive query with functional dependencies and degree bounds have shown a deep connection between fundamental questions in information theory and database theory. This paper connects semantic query optimization, physical query optimization & cost estimation, to information theory with provable bounds.