Click on the title to obtain a gzip-ed PostScript version of the paper (76K).
Our approach uses tries as the basis for tables. Tries provide complete discrimination for terms, and permit a lookup and possible insertion to be performed in a single pass through a term. A novel technique of substitution factoring is also proposed. When substitution factoring is used in conjunction with tries, the access cost for answers is proportional to the size of the answer substitution, rather than to the size of the answer itself. As a special case, the access cost of answers to a datalog query is proportional to the number of non-ground arguments of the query, giving a means of dynamic argument reduction. Answer tries can be implemented both as interpreted structures and as compiled WAM-like code. When they are compiled, the speed of computing substitutions through answer tries is competitive with the speed of unit facts compiled as WAM code, or asserted. Because answer tries can also be created an order of magnitude more quickly than asserted code, they form a promising alternative for representing dynamic terms, even in SLD evaluation.