Practical algorithm for evaluating database queries

J.H.M. de Vet

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    This paper describes an algorithm for evaluating database queries represented as expressions in a logical language. Such a database query expression can be evaluated efficiently by focusing on the variable dependencies. The algorithm recursively computes the values of subexpressions to evaluate the input expression, but it avoids re-evaluation of those subexpressions whose values are not affected by new variable assignments. The input expression is internally structured as a directed acyclic graph. Two additional techniques to improve efficiency of the evaluation are discussed: transformations of the input expression and special primitive database operations. Finally, its implementation in the natural language question-answering system SPICOS is described.

    Original languageEnglish
    Pages (from-to)491-504
    Number of pages14
    JournalSoftware : Practice and Experience
    Volume19
    Issue number5
    DOIs
    Publication statusPublished - May 1989

    Cite this