We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 34 Issue 4
July  2019
Turn off MathJax
Article Contents
Abstract
References
Supplements
Hong-Cheu Liu, Jixue Liu. On the Expressive Power of Logics on Constraint Databases with Complex Objects[J]. Journal of Computer Science and Technology, 2019, 34(4): 795-817. DOI: 10.1007/s11390-019-1943-7
Citation: Hong-Cheu Liu, Jixue Liu. On the Expressive Power of Logics on Constraint Databases with Complex Objects[J]. Journal of Computer Science and Technology, 2019, 34(4): 795-817. DOI: 10.1007/s11390-019-1943-7
shu

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

  • School of Information Technology and Mathematical Sciences, University of South Australia, Adelaide 5095, Australia

Funds: This work was supported in part by the Taiwan Science Council, China, under Grant No. NSC90-2218-E-126-001.
More Information
  • Received Date: August 31, 2018
  • Revised Date: April 22, 2019
  • Published Date: July 10, 2019
    Abstract
  • 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 ∪i ∑iNC1, NCH =∪i ∑iNC, 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.
    • FullText(HTML)
    • References (50)
  • [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.
    • Relative Articles
  • Supplements (1)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Article views (28) PDF downloads (11) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return