Afrati, F., Papadimitriou, C.H.' The parallel complexity of simple chain queries. Proc. 6th A CM Syrup. on Principles of Database Systems, San Diego, 1987, pp. 210-213.

Digital Library

Google Scholar

[2]

Aho, V.H., Ullman, j.D.' Universality of data retrieval languages. Proc. 6th A CM Syrup. on Principles of Programming Languages, 1979, pp. 110-117.

Digital Library

Google Scholar

[3]

Bancilhon, F., Ramakrishnan, R.: An amateur's introduction to recursive query processing strategies. Proc. A CM Conf on Management of Data, Washington, 1986, pp. 16-52.

Digital Library

Google Scholar

[4]

Beeri, C., Kanellakis, P.C., Bancilhon, F., Ramakrishnan, R.' Bounds on the propagation of selection into logic programs. Proc. 6th A CM Syrup. on Principles of Database Systems, S~n Diego, 1987, pp. 214-226.

Digital Library

Google Scholar

[5]

Chandra, A.K.' Programming primitives for database languages. Proc. 8th A CM Syrup. on Principles of Programming Languages, Williamsburg, 1981, pp. 50-62.

Digital Library

Google Scholar

[6]

Chandra, A.K., Harel, D.: Computable queries for relational databases. J. Computer and Systems Sciences 21(1980), pp. 156-178.

Crossref

Google Scholar

[7]

Chandra, A.K., Harel, D.' Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99-128.

Crossref

Google Scholar

[8]

Chandra, A.K., Harel, D.' Hornclause queries and generalizations, j. Logic Programming 1(1985), pp. 1-15.

Crossref

Google Scholar

[9]

Chandra, A.K., Merlin, P.M.' Optimal implementation of conjunctive queries in relational databases. Pvoc. ~th A CM Syrup. on Theory of Computing, Boulder, 1977, pp. 77-90.

Digital Library

Google Scholar

[10]

Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: Decidable optimization problents for database logic programs. Proc. 2Oth A CM $ymp. on Theory of Computing, Chicago, 1988, pp. 477-490.

Digital Library

Google Scholar

[11]

Cosmadakis, S.S., Kanellakis, P.C.: Parallel evaluation of recursive rule queries. Proc. 5th A CM Syrup. on Principles of Database Systems, Cambridge, 1986, pp. 280-293.

Digital Library

Google Scholar

[12]

Cook, S.A.' An observation on time-storage trade off. J. Computer and System Sciences 9 (1974), pp. 308-316.

Digital Library

Google Scholar

[13]

Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proc. 2nd IEEE Symp. on Logic in Computer Science, Ithaca, 1987, pp. 106-115.

Google Scholar

[14]

Gallaire, H., Minker, J- Logic and Databases. Plenum Press, 1978.

Digital Library

Google Scholar

[15]

Henschen, L.J., Naqvi, S.A.: On compiling queries in recursive firstorder databases. J. ACM 31(1984), pp. 47-85.

Digital Library

Google Scholar

[16]

Hopcroft, J.E., Ullman, J.D.' Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.

Digital Library

Google Scholar

[17]

hnmerman, N.' Number of quantifiers is better titan number of tape cells. J. Computer and System Sciences 22(1981), pp. 384-406.

Crossref

Google Scholar

[18]

Immerman, N.' Relational queries computable in polynomial time. bformation and Control 68(1986), pp. 86-104.

Digital Library

Google Scholar

[19]

hnmerman, N.' Expressibility as a complexity measure: results and directions. Pvoc. ~nd IEEE Conf. on Structure in Complexity Theory, Ithaca, 1987, pp. 194-202.

Google Scholar

[20]

Immerman, N.: Languages that capture complexity classes. SIAM J. Comp. 16 (1987), pp.760-778.

Digital Library

Google Scholar

[21]

Ioannidis, Y.E.' A time bound on the materialization of some recursively defined views. Proc. 111h }nt 'l Conf. on Very Large Data Bases, Stockholm, 1985, pp. 219-226.

Google Scholar

[22]

Kanellakis, P.C.: Logic programming and parallel complexity, in Foundations of Deductive Databases and Logic Programming, J. Minker ed., (to appear).

Digital Library

Google Scholar

[23]

MMer, D., Warren, D.S.' Computing with Logic: Logic Programming with Prolog. Benjamin Cummings, 1988.

Digital Library

Google Scholar

[24]

Moschovakis, Y.N.: Elementary Induction on Abstract Structures. North-Holland, 1974.

Digital Library

Google Scholar

[25]

Naughton, J.F.' Data independent recursion in deductive databases. Proc. 5th A CM Syrup. on Principles of Database Systems, Cambridge, 1986, pp. 267-279. Full version- Stanford University Technical Report STAN-CS-86-1102, to appear in J. Computer and System Sciences.

Digital Library

Google Scholar

[26]

Naughton, J.F., Sagiv, Y.' A decidable class of bounded recursions. Pvoc. 6th A UM Syrup. on Principles of Database Systems, San Diego, 1987, pp. 227-236.

Digital Library

Google Scholar

[27]

Ulhuan, J.D.' Implementation of logical query languages for databases. A CM Trans. on Database Systems 10(1985), pp. 289-321.

Digital Library

Google Scholar

[28]

Ullman, J.D., Van Gelder, A.' Parallel complexity of logical query programs. P~'oc. ~7th IEEE Syrup. on Foundaiions of Uomp. Sci., Toronto, 1986, pp. 438-454.

Google Scholar

[29]

Vardi, M.Y.' The complexity of relational query languages. Pvoc. l dth ACM Syrup. on Theory of Computing, San Francisco, 1982, pp. 137- 146.

Digital Library

Google Scholar

[30]

Vardi, M.Y.' Decidability and Undecidablity Results for Boundedness of Linear Recursive Queries. Proc. 7th A CM Syrup. on Principles of Database Systems, Austin, 1988, pp. 341-351.

Digital Library

Google Scholar

Cited By

View all

Bodirsky MBulín JStarke FWernthaler M(2023)The smallest hard treesConstraints10.1007/s10601-023-09341-828:2(105-137)Online publication date: 25-Mar-2023
https://doi.org/10.1007/s10601-023-09341-8
Sciascio CBrusilovsky PTrattner CVeas E(2019)A Roadmap to User-Controllable Social Exploratory SearchACM Transactions on Interactive Intelligent Systems10.1145/324138210:1(1-38)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3241382
Todi KJokinen JLuyten KOulasvirta A(2019)Individualising Graphical Layouts with Predictive Visual Search ModelsACM Transactions on Interactive Intelligent Systems10.1145/324138110:1(1-24)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3241381
Show More Cited By

Index Terms

Expressiveness of restricted recursive queries

Recommendations

Expressiveness of guarded existential rule languages
PODS '14: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

The so-called existential rules have recently gained attention, mainly due to their adequate expressiveness for ontological query answering. Several decidable fragments of such rules have been introduced, employing restriction such as various forms of ...
A Step Up in Expressiveness of Decidable Fixpoint Logics
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

Guardedness restrictions are one of the principal means to obtain decidable logics --- operators such as negation are restricted so that the free variables are contained in an atom. While guardedness has been applied fruitfully in the setting of first-...
On the first-order expressibility of recursive queries
PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

A Datalog program is bounded iff it is equivalent to a recursion-free Datalog program. We show that, for some classes of Datalog programs, expressibility in first-order query languages coincides with boundedness. Our results imply that testing first-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

February 1989

600 pages

ISBN:0897913078

DOI:10.1145/73007

Editor:
D. S. Johnson

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC89

Sponsor:

SIGACT

STOC89: 21st Annual ACM Symposium on the Theory of Computing

May 14 - 17, 1989

Washington, Seattle, USA

Acceptance Rates

STOC '89 Paper Acceptance Rate 56 of 196 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
473
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)24

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bodirsky MBulín JStarke FWernthaler M(2023)The smallest hard treesConstraints10.1007/s10601-023-09341-828:2(105-137)Online publication date: 25-Mar-2023
Sciascio CBrusilovsky PTrattner CVeas E(2019)A Roadmap to User-Controllable Social Exploratory SearchACM Transactions on Interactive Intelligent Systems10.1145/324138210:1(1-38)Online publication date: 30-Aug-2019
Todi KJokinen JLuyten KOulasvirta A(2019)Individualising Graphical Layouts with Predictive Visual Search ModelsACM Transactions on Interactive Intelligent Systems10.1145/324138110:1(1-24)Online publication date: 30-Aug-2019
Maier DTekle KKifer MWarren D(2018)DatalogDeclarative Logic Programming10.1145/3191315.3191317(3-100)Online publication date: 1-Sep-2018
(2018)Declarative Logic ProgrammingundefinedOnline publication date: 1-Sep-2018
Lutz CSabellek L(2017)Ontology-mediated querying with the description logic ELProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171810(1181-1187)Online publication date: 19-Aug-2017
Acharya K(2017)User value and usability in technical communicationCommunication Design Quarterly10.1145/3071078.30710834:3(26-34)Online publication date: 27-Mar-2017
Ishii ROtsuka KKumano SYamato J(2016)Using Respiration to Predict Who Will Speak Next and When in Multiparty MeetingsACM Transactions on Interactive Intelligent Systems10.1145/29468386:2(1-20)Online publication date: 3-Aug-2016
Bosch ND'mello SOcumpaugh JBaker RShute V(2016)Using Video to Automatically Detect Learner Affect in Computer-Enabled ClassroomsACM Transactions on Interactive Intelligent Systems10.1145/29468376:2(1-26)Online publication date: 20-Jul-2016
Greco SMolinaro C(2015)Datalog and Logic DatabasesSynthesis Lectures on Data Management10.2200/S00648ED1V01Y201505DTM0417:2(1-169)Online publication date: 5-Nov-2015
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Expressiveness of guarded existential rule languages

A Step Up in Expressiveness of Decidable Fixpoint Logics

On the first-order expressibility of recursive queries