Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
We investigate the complexity of query processing in the logical data model (LDM). We use two measures: data complexity, which is complexity with respect to the size of the data, and expression complexity, which is complexity with respect to the size of the expressions denoting the queries. Our investigation shows that while the operations of product and union are essentially first-order operations, the power set operation is inherently a higher-order operation and is exponentially expensive. We define a hierarchy of queries based on the depth of nesting of power set operations and show that this hierarchy corresponds to a natural hierarchy of Turing machines that run in multiply exponential time. © 1993.
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Fan Jing Meng, Ying Huang, et al.
ICEBE 2007
Robert E. Donovan
INTERSPEECH - Eurospeech 2001