Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (4): 795-817.doi: 10.1007/s11390-019-1943-7

Special Issue: Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

On the Expressive Power of Logics on Constraint Databases with Complex Objects

Hong-Cheu Liu, Jixue Liu   

  1. School of Information Technology and Mathematical Sciences, University of South Australia, Adelaide 5095, Australia
  • Received:2018-09-01 Revised:2019-04-23 Online:2019-07-11 Published:2019-07-11
  • Supported by:
    This work was supported in part by the Taiwan Science Council, China, under Grant No. NSC90-2218-E-126-001.

We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases. The tools we use come in the form of collapse results which are well established in the context of first-order logic. We show that the natural-active collapse with a condition and the activegeneric collapse carry over to the second-order logic for structures with o-minimality property and any signature in the complex value relations. The expressiveness results for more powerful logics including monadic second-order logic, monadic second-order logic with fix-point operators, and fragments of second-order logic are investigated in the paper. We discuss the data complexity for second-order logics over constraint databases. The main results are that the complexity upper bounds for three theories, MSO + Lin, MSO + Poly, and Inflationary Datalogactcv,¬(SC, M) without powerset operator are ∪iiNC1, NCH=∪iiNC, and AC0/poly, respectively. We also consider the problem of query closure property in the context of embedded finite models and constraint databases with complex objects and the issue of how to determine safe constraint queries.

Key words: constraint database; monadic second-order logic; natural-active collapse; Ramsey property; o-minimality structure;

[1] Revesz P. Big data and spatial constraint databases. In Encyclopedia of GIS, Shekhar S, Xiong H, Zhou X (eds.), Springer, 2017, pp.118-122.
[2] Kanellakis P, Kuper G, Revesz P. Constraint query languages. Journal of Computer and System Sciences, 1995, 51(1):26-52.
[3] Libkin L. Embedded finite models and constraint databases. In Finite Model Theory and Its Applications, Grädel E, Kolaitis P G, Libkin L, Marx M, Spencer J, Vardi M Y (eds.), Springer, 2007, pp.257-337.
[4] Libkin L. Query languages with arithmetic and constraint databases. SIGACT News, 1999, 30(4):41-50.
[5] Hull R, Su J. Domain independence and the relational calculus. Acta Informatica, 1994, 31(6):513-524.
[6] Moschovakisl Y. Elementary Induction on Abstract Structures. North-Holland, 1974.
[7] Chandra A, Harel D. Structure and complexity of relational queries. Journal of Computer and System Sciences, 1982, 25(1):99-128.
[8] Kuper G, Libkin L, Paredaens J. Constraint Databases. Springer, 2000.
[9] Benedikt M, Dong G, Libkin L, Wong L. Relational expressive power of constraint query languages. Journal of the ACM, 1998, 45(1):1-34.
[10] Basu S. New results on quantifier elimination over real closed fields and application to constraint databases. Journal of the ACM, 1999, 46(4):537-555.
[11] Tarski A. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.
[12] van den Dries L. O-minimal structures. In Logic:From Foundations to Applications:European Logic Colloquium, Hodges W, Hyland M, Steinhorn C, Truss J (eds.), Oxford Science Publications, 1996, pp.99-108.
[13] Nešetřil J, Rödl V. Mathematics of Ramsey Theory. Springer-Verlag Berlin Heidelberg, 1990.
[14] Graham R L, Rothschild B L, Spencer J H. Ramsey Theory (2nd edition). Wiley-Interscience, 1990.
[15] Benedikt M, Libkin L. Relational queries over interpreted structures. Journal of the ACM, 2000, 47(4):644-680.
[16] Abiteboul S, Beeri C. The power of languages for the manipulation of complex values. The Very Large Data Bases Journal, 1995, 4(4):727-794.
[17] Grädel E, Gurevich Y. Metafinite model theory. Information and Computation, 1998, 140(1):26-81.
[18] Rose E, Segev A. TOODM-A temporal object-oriented data model with temporal constraints. In Proc. the 10th International Conference on the Entity Relationship Approach, October 1991, pp.205-229.
[19] Revesz P. Safe query languages for constraint databases. Transactions on Database Systems, 1998, 23(1):58-99.
[20] Abiteboul S, Hull R, Vianu V. Foundations of Databases. Addison-Wesley, 1995.
[21] Libkin L. A collapse result for constraint queries over structures of small degree. Information Processing Letter, 2003, 86(5):277-281.
[22] Goldin D, Kanellakis P C. Constraint query algebras. Constraints, 1996, 1(1/2):45-83.
[23] Grädel E, Kreutzer S. Descriptive complexity theory for constraint databases. In Proc. the 13th International Workshop on Computer Science Logic, September 1999, pp.67-81.
[24] Kuijpers B, Paredaens J, van den Bussche J. Lossless representation of topological spatial data. In Proc. the 4th Symposium on Spatial Databases, August 1995, pp.1-13.
[25] Segoufin L, Vianu V. Querying spatial databases via topological invariants. In Proc. the 17th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, June 1998, pp.89-98.
[26] Wong L. A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator. In Proc. the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June 2013, pp.285-295.
[27] Otto M, van den Bussche J. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 1996, 60(1):37-41.
[28] Aylamazyan A K, Gilula M M, Stolboushkin A P, Schwartz G F. Reduction of the relational model with infinite domains to the case of finite domains. Doklady Akademii Nauk SSSR, 1986, 286(2):308-311. (in Russian)
[29] Benedikt M, Grohe M, Libkin L, Segoufin L. Reachability and connectivity queries in constraint databases. Journal of Computer and System Sciences, 2003, 66(1):169-206.
[30] Arora S, Barak B. Computational Complexity:A Modern Approach (1st edition). Cambridge University Press, 2009.
[31] Kanellakis P C, Goldin D Q. Constraint programming and database query languages. In Proc. the 1994 International Conference on Theoretical Aspects of Computer Software, April 1994, pp.96-120.
[32] Karp R, Ramachandran V. Parallel algorithms for sharedmemory machines. In Handbook of Theoretical Computer Science:Volume A:Algorithm and Complexity, van Leeuween J (ed.), 1990, pp.869-941.
[33] Jonsson P, Lööw T. Computational complexity of linear constraints over the integers. Artificial Intelligence, 2013, 195:44-62.
[34] Benedikt M, Libkin L. Safe constraint queries. SIAM Journal on Computing, 2000, 29(5):1652-1682.
[35] Escobar-Molano M, Hull R, Jacobs D. Safety and translation of calculus queries with scalar functions. In Proc. the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1993, pp.253-264.
[36] Avron A, Lev S, Levi N. Safety, absoluteness, and computability. In Proc. the 27th EACSL Annual Conference on Computer Science Logic, September 2018, Article No. 8.
[37] Liu H C, Yu J X, Liang W F. Safety, domain independence and translation of complex value database queries. Inf. Sci., 2008, 178(12):2507-2533.
[38] Stolboushkin A, Taitslin M. Finite queries do not have effective syntax. In Proc. the 14th ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, May 1995, pp.277-285.
[39] Pillary A, Steinhorn C. Definable sets in ordered structures. Ⅲ. Transactions of the American Mathematical Society, 1988, 309(2):469-476.
[40] Ebbinghaus H D, Flum J. Finite Model Theory (2nd edition). Springer-Verlag Berlin Heidelberg, 1995.
[41] Immerman N. Descriptive Complexity. Springer-Verlag New York, 1999.
[42] Libkin L. Elements of Finite Model Theory. Springer-Verlag Berlin Heidelberg, 2004.
[43] Paredaens J, van den Bussche J, van Gucht D. First-order queries on finite structures over the reals. SIAM Journal on Computing, 1998, 27(6):1747-1763.
[44] Pillay A, Steinhorn C. Definable sets in ordered structures. Bulletin of the American Mathematical Society, 1984, 11(1):159-162.
[45] van den Dries L. Tame Aopology and O-Minimality Structures. Cambridge University Press, 1998.
[46] Kuijpers B, Paredaens J, van den Bussche J. Topological elementary equivalence of closed semi-algebraic sets in the real plane. Journal of Symbolic Logic, 2000, 65(4):1530-1555.
[47] Kuijpers B, van den Bussche J. On capturing first-order topological properties of planar spatial databases. In Proc. the 7th International Conference on Database Theory, January 1999, pp.187-198.
[48] Papadimitriou C, Suciu D, Vianu V. Topological queries in spatial databases. Journal of Computer and System Sciences, 1999, 58(1):29-53.
[49] Segoufin L, Vianu V. Querying spatial databases via topological invariants. Journal of Computer and System Sciences, 2000, 61(2):270-301.
[50] Vandeurzen L, Gyssens M, van Gucht D. On the expressiveness of linear-constraint query languages for spatial databases. Theoretical Computer Sciences, 2001, 254(1/2):423-463.
[1] WANG Wei; WaNG Yujun; SHI Baile;. Dynamic Interval Index Structure in Constraint Database Systems [J]. , 2000, 15(6): 542-551.
[2] WANG Wei(汪卫),WANG Yujun(王宇君)and SHI Baile(施伯乐). Dynamic Interval Index Structure in Constraint Database Systems [J]. , 2000, 15(6): 0-0.
Full text



[1] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[2] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[3] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[4] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[5] Xia Peisu; Fang Xinwo; Wang Yuxiang; Yan Kaiming; Zhang Tingjun; Liu Yulan; Zhao Chunying; Sun Jizhong;. Design of Array Processor Systems[J]. , 1987, 2(3): 163 -173 .
[6] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[7] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[8] Xie Li; Chen Peipei; Yang Peigen; Sun Zhongxiu;. The Design and Implementation of an OA System ZGL1[J]. , 1988, 3(1): 75 -80 .
[9] Luo Yinfang;. Algorithm and Implementation of Parallel Multiplication in a Mixed Number System[J]. , 1988, 3(3): 203 -213 .
[10] Chen Guoliang;. A Partitioning Selection Algorithm on Multiprocessors[J]. , 1988, 3(4): 241 -250 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved