Type inference for datalog and its application to query optimisation
Type inference for datalog and its application to query optimisation
复制标题
数据记录的类型推断及其在查询优化中的应用
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Verbaere
中科院分区：
文献类型：
--
作者：
O. Moor;D. Sereni;Pavel Avgustinov;M. Verbaere
Certain variants of object-oriented Datalog can be compiled to Datalog with negation. We seek to apply optimisations akin to virtual method resolution (a well-known technique in compiling Java and other OO languages) to improve efficiency of the resulting Datalog programs. The effectiveness of such optimisations strongly depends on the precision of the underlying type inference algorithm. Previous work on type inference for Datalog has focussed on Cartesian abstractions, where the type of each field is computed separately. Such Cartesian type inference is inherently imprecise in the presence of field equalities. We propose a type system where equalities are tracked, and present a type inference algorithm. The algorithm is proved sound. We also prove that it is optimal for Datalog without negation, in the sense that the inferred type is as tight as possible. Extensive experiments with our type-based optimisations, in a commercial implementation of object-oriented Datalog, confirm the benefits of this non-Cartesian type inference algorithm.
