Complexity of database languages

摘要

A measure of complexity for database language is developed and tested. It is used to confirm many of the widely held professional opinions about the complexity of database languages. Complexity is measured by comparison to a reference language. A reference language of minimal components based on clausal form of first-order logic is developed to serve as a yardstick. As in the complexity of algorithms, the rate of change in complexity relative to the size of expressions is found to be critical. The complexity measure is tested against the perceived complexity by database users, and found to be a significant predictor of human perceived complexity.