Article

Free access

Structural query optimization—a uniform framework for semantic query optimization in deductive databases

Authors:

Laks V. S. Lakshmanan,

Héctor J. HernándezAuthors Info & Claims

PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 102 - 114

https://doi.org/10.1145/113413.113423

Published: 01 April 1991 Publication History

PDF eReader

References

[1]

Abiteboul, S. "Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule," Information Processing Letters 3e (1#89), pp. 282-287.

Digital Library

Google Scholar

[2]

Abiteboul, S. and R. Hull. "Data Functions, Datalog and Negation," in Proc, ACM SIGMOD, 1988, pp. 143-153.

Digital Library

Google Scholar

[3]

Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y., "Decidable Optimization Problems for Database Logic Programs," IBM Research Report R2 6145 (60855), Yorktown Heights, New York, March 22, 1988.

Google Scholar

[4]

Gaifman, It., Mairson, H., Sagiv, Y., Vardi, M.Y., "Undecidable Optimization Problems for Database Logic Programs," IBM Research Report R2 5583 (56702), Yorktown Heights, New York, April 3, 1987.

Google Scholar

[5]

Hull, R., Personal Communication, November 1990.

Google Scholar

[6]

Ioannidis, Y.E., "A time bound on the materialization of some recursively defined views," Proc. VLDB lg85, pp. 219- 226.

Google Scholar

[7]

Kanellakis, P. "Logic Programming and Parallel Complexity," Foundations of Deductive Databases and Logic Programming," J. Minker ed., Morgan Kaufmann (1988), 547-586.

Digital Library

Google Scholar

[8]

Kanellakis, P., Abiteboul, S. "Database Theory Column" Deciding Bounded Recurslon in Database Logic Programs, SIGACT News, Vol. 20, No. 4, pp. 17- 23, Fall 1989.

Digital Library

Google Scholar

[9]

Lakshmanan V.S. and Hernandez H., "Structural Query Optimization- A Uniform Framework For Semantic Query Optimization in Deductive Databases," Tech. Report. CSD-90-06, Deot. of Comp.Sci. Concordia Univ., Montreal, (NMSU-TR-91-CS-02, Dept. of Computer Sci. New Mexico State Univ., Las Crucez, NM), Dec. 1990.

Google Scholar

[10]

inker, J. and Nicolas, j.M. "On recursive axioms in relational databases." Information Systems, 8(1), pp. 1-13, 1982.

Google Scholar

[11]

Naughton, J.F. "Data Independent Recursion in deductive databases," in Proc. A CM PODS, 1986, pp. 267-279.

Digital Library

Google Scholar

[12]

Naughton, J.F. "Redundancy in function free recursive inference rules." in Proc. of the IEEE Symposium on Logic PrQgramming# 1988.

Google Scholar

[13]

Naughton, J.F., Sagiv, Y. "A decidable class of bounded recursions," in Proc. A CM PODS, 1987, pp. 227-236.

Digital Library

Google Scholar

[14]

Ramakrishnan, R., Sagiv, Y., Ullman, J.D., Vardi, M. Proof-tree Transformation Theorems and Their Applications." in Proc. ACM PODS, 1989, pp. 172-181.

Digital Library

Google Scholar

[15]

Sagiv, Y., "On Bounded Database Schemes and Bounded Horn-Clause Programs," SIAM J. on Computing, 17:1 (1988), pp. 1-22.

Digital Library

Google Scholar

[16]

Saraiya, Y., "Linearizing nonlinear recursions in polynomial-time," in Proc. ACM PODS, 1989, pp. 182-189.

Digital Library

Google Scholar

[17]

Ullman, J.D., Principles of Database Systems, Computer Science Press, 1982.

Digital Library

Google Scholar

[18]

Ullman, J.D., Principles of Database and Knowledge.Base Systems, Vol. I,II, Computer Science Press, 1989.

Digital Library

Google Scholar

[19]

Vardi, M.Y., "Decidability and Undecidability Results for Boundedness of Linear Recursive Queries," in Proc. A CM PODS, 1988, pp. 341-351.

Digital Library

Google Scholar

Cited By

View all

Godfrey PGryz J(2007)View disassemblyJournal of Computer and System Sciences10.1016/j.jcss.2007.03.00273:6(941-961)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1016/j.jcss.2007.03.002
Brisaboa NFariña ALuaces MParamá J(2007)Chase of Recursive QueriesPerspectives of Systems Informatics10.1007/978-3-540-70881-0_12(112-123)Online publication date: 2007
https://doi.org/10.1007/978-3-540-70881-0_12
Brisaboa NFariña, ALuaces MParamá J(2006)Chase of recursive queriesProceedings of the 6th international Andrei Ershov memorial conference on Perspectives of systems informatics10.5555/1760700.1760714(112-123)Online publication date: 27-Jun-2006
https://dl.acm.org/doi/10.5555/1760700.1760714
Show More Cited By

Index Terms

Structural query optimization—a uniform framework for semantic query optimization in deductive databases
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)
      2. Database query processing and optimization (theory)

Recommendations

Query Rewriting and Optimization for Ontological Databases

Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints that derive new intensional knowledge from the extensional database), rather than ...
Query Optimization for Ontology-Mediated Query Answering
WWW '24: Proceedings of the ACM Web Conference 2024

Ontology-mediated query answering (OMQA) consists in asking database queries on knowledge bases (KBs); a KB is a set of facts called the KB's database, which is described by domain knowledge called the KB's ontology. A widely-investigated OMQA technique ...
Query rewriting for semantic query optimization in spatial databases

Query processing is an important challenge for spatial databases due to the use of complex data types that represent spatial attributes. In particular, due to the cost of spatial joins, several optimization algorithms based on indexing structures exist. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

April 1991

341 pages

ISBN:0897914309

DOI:10.1145/113413

Chairman:
Daniel J. Rosenkrantz
State Univ. of New York, Albany

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 April 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS91

Sponsor:

SIGMOD/PODS91: SIGMOD/PODS 91

May 29 - 31, 1991

Colorado, Denver, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
330
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Godfrey PGryz J(2007)View disassemblyJournal of Computer and System Sciences10.1016/j.jcss.2007.03.00273:6(941-961)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1016/j.jcss.2007.03.002
Brisaboa NFariña ALuaces MParamá J(2007)Chase of Recursive QueriesPerspectives of Systems Informatics10.1007/978-3-540-70881-0_12(112-123)Online publication date: 2007
https://doi.org/10.1007/978-3-540-70881-0_12
Brisaboa NFariña, ALuaces MParamá J(2006)Chase of recursive queriesProceedings of the 6th international Andrei Ershov memorial conference on Perspectives of systems informatics10.5555/1760700.1760714(112-123)Online publication date: 27-Jun-2006
https://dl.acm.org/doi/10.5555/1760700.1760714
Paramá JBrisaboa NPenabad MPlaces Á(2006)A semantic approach to optimize linear datalog programsActa Informatica10.1007/s00236-006-0025-943:5(341-370)Online publication date: 2-Nov-2006
https://dl.acm.org/doi/10.1007/s00236-006-0025-9
Du XIshii N(2005)Normalization of linear recursions based on graph transformationsInformation Systems and Data Management10.1007/3-540-60584-3_38(265-282)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-60584-3_38
Paramá JBrisaboa NPenabad MPlaces Á(2002)A Semantic Query Optimization Approach to Optimize Linear Datalog ProgramsAdvances in Databases and Information Systems10.1007/3-540-45710-0_22(277-290)Online publication date: 23-Aug-2002
https://doi.org/10.1007/3-540-45710-0_22
Godfrey PGryz J(2001)Partial Evaluation of ViewsJournal of Intelligent Information Systems10.1023/A:100873691005816:1(21-39)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.1023/A%3A1008736910058
Lakshmanan LMissaoui R(1992)On semantic query optimization in deductive databases[1992] Eighth International Conference on Data Engineering10.1109/ICDE.1992.213173(368-375)Online publication date: 1992
https://doi.org/10.1109/ICDE.1992.213173

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

Query Rewriting and Optimization for Ontological Databases

Query Optimization for Ontology-Mediated Query Answering

Query rewriting for semantic query optimization in spatial databases