article

On the expressive power of database queries with intermediate types

Authors:

Richard Hull,

Jianwen SuAuthors Info & Claims

Journal of Computer and System Sciences, Volume 43, Issue 1

Pages 219 - 267

https://doi.org/10.1016/0022-0000(91)90036-5

Published: 01 August 1991 Publication History

Abstract

No abstract available.

Cited By

View all

Partridge CDe Cesare SMitchell AOdell J(2018)Formalization of the classification patternSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0521-517:1(167-203)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10270-016-0521-5
Freire CMartins A(2011)The Descriptive Complexity of the Deterministic Exponential Time HierarchyElectronic Notes in Theoretical Computer Science (ENTCS)10.5555/2952797.2952921269:C(71-82)Online publication date: 22-Apr-2011
https://dl.acm.org/doi/10.5555/2952797.2952921
Schewe KTurull Torres J(2006)Fixed-Point Quantifiers in Higher Order LogicsProceedings of the 2006 conference on Information Modelling and Knowledge Bases XVII10.5555/1565027.1565045(237-244)Online publication date: 17-May-2006
https://dl.acm.org/doi/10.5555/1565027.1565045
Show More Cited By

Index Terms

On the expressive power of database queries with intermediate types
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Approximating expressive queries on graph-modeled data

We present GeX for the approximate matching of complex queries on graph-modeled data.GeX generalizes existing approaches and allows for querying any graph-based datasets.GeX query language supports queries ranging from keyword-based to complex ones.GeX ...
On the expressive power of database queries with intermediate types
PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of ...
Containment of Expressive SPARQL Navigational Queries
The Semantic Web – ISWC 2016
Abstract
Query containment is one of the building block of query optimization techniques. In the relational world, query containment is a well-studied problem. At the same time it is well-understood that relational queries are not enough to cope with graph-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 43, Issue 1

Aug. 1991

266 pages

ISSN:0022-0000

Editor:
E. K. Blum
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 August 1991

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Partridge CDe Cesare SMitchell AOdell J(2018)Formalization of the classification patternSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0521-517:1(167-203)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10270-016-0521-5
Freire CMartins A(2011)The Descriptive Complexity of the Deterministic Exponential Time HierarchyElectronic Notes in Theoretical Computer Science (ENTCS)10.5555/2952797.2952921269:C(71-82)Online publication date: 22-Apr-2011
https://dl.acm.org/doi/10.5555/2952797.2952921
Schewe KTurull Torres J(2006)Fixed-Point Quantifiers in Higher Order LogicsProceedings of the 2006 conference on Information Modelling and Knowledge Bases XVII10.5555/1565027.1565045(237-244)Online publication date: 17-May-2006
https://dl.acm.org/doi/10.5555/1565027.1565045
Hella LTurull-Torres J(2006)Computing queries with higher-order logicsTheoretical Computer Science10.1016/j.tcs.2006.01.009355:2(197-214)Online publication date: 11-Apr-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.01.009
Hella LTurull-Torres J(2006)Complete problems for higher order logicsProceedings of the 20th international conference on Computer Science Logic10.1007/11874683_25(380-394)Online publication date: 25-Sep-2006
https://dl.acm.org/doi/10.1007/11874683_25
Vorobyov S(2004)The most nonelementary theoryInformation and Computation10.1016/j.ic.2004.02.002190:2(196-219)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.1016/j.ic.2004.02.002
Benedikt MLibkin L(2000)Relational queries over interpreted structuresJournal of the ACM10.1145/347476.34747747:4(644-680)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1145/347476.347477
Vorobyov SVoronkov AMendelson AParedaens J(1998)Complexity of nonrecursive logic programs with complex valuesProceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/275487.275515(244-253)Online publication date: 1-May-1998
https://dl.acm.org/doi/10.1145/275487.275515
Benedikt MLibkin LMendelzon AÖzsoyoglu Z(1997)Languages for relational databases over interpreted structuresProceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/263661.263672(87-98)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/263661.263672
Suciu DParedaens J(1997)The Complexity of the Evaluation of Complex Algebra ExpressionsJournal of Computer and System Sciences10.1006/jcss.1997.152655:2(322-343)Online publication date: 1-Oct-1997
https://dl.acm.org/doi/10.1006/jcss.1997.1526
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Approximating expressive queries on graph-modeled data

On the expressive power of database queries with intermediate types

Containment of Expressive SPARQL Navigational Queries

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations