Article

Free access

View-based query processing for regular path queries with inverse

Authors:

Diego Calvanese,

Moshe Y. Vardi,

Giuseppe de Giacomo,

Maurizio LenzeriniAuthors Info & Claims

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

Pages 58 - 66

https://doi.org/10.1145/335168.335207

Published: 01 May 2000 Publication History

Abstract

View-based query processing is the problem of computing the answer to a query based on a set of materialized views, rather than on the raw data in the database. The problem comes in two different forms, called query rewriting and query answering, respectively. In the first form, we are given a query and a set of view definitions, and the goal is to reformulate the query into an expression that refers only to the views. In the second form, besides the query and the view definitions, we are also given the extensions of the views and a tuple, and the goal is to check whether the knowledge on the view extensions logically implies that the tuple satisfies the query.

In this paper we address the problem of view-based query processing in the context of semistructured data, in particular for the case of regular-path queries extended with the inverse operator. Several authors point out that the inverse operator is one of the fundamental extensions for making regular-path queries useful in real settings. We present a novel technique based on the use of two-way finite-state automata. Our approach demonstrates the power of this kind of automata in dealing with the inverse operator, allowing us to show that both query rewriting and query answering with the inverse operator has the same computational complexity as for the case of standard regular-path queries.

References

[1]

S. Abiteboul. Querying semi-structured data. In Proc. of the 6th Int. Conf. on Database Theory (ICDT'97), pages 1-18, 1997.]]

Digital Library

[2]

S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In Proc. of the 17th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'98), pages 254-265, 1998.]]

Digital Library

[3]

S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.]]

[4]

S. Adali, K. S. Candan, Y. Papakonstantinou, and V. S. Subrahmanian. Query caching and optimization in distributed mediator systems. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 137-148, 1996.]]

Digital Library

[5]

F. N. Afrati, M. Gergatsoulis, and T. Kavalieros. Answering queries using materialized views with disjunction. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 435-452. Springer-Verlag, 1999.]]

Digital Library

[6]

C. Beeri, A. Y. Levy, and M.-C. Rousset. Rewriting queries using views in description logics. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'97), pages 99-108, 1997.]]

Digital Library

[7]

P. Buneman. Semistructured data. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'97), pages 117-121, 1997.]]

Digital Library

[8]

P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization technique for unstructured data. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 505-516, 1996.]]

Digital Library

[9]

D. Calvanese, G. De Giacomo, and M. Lenzerini. Answering queries using views in description logics. In Proc. of the 1999 Description Logic Workshop (DL '99), pages 9-13. CEUR Electronic Workshop Proceedings http://sunsite.informatik.rwthaachen, de / Pub licat ions / CE UR-WS/Vol- 22/, 1999.]]

[10]

D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In Proc. of the 18th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'99), pages 194-204, 1999.]]

Digital Library

[11]

D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Answering regular path queries using views. In Proc. of the 16th IEEE Int. Conf. on Data Engineering (ICDE 2000), 2000. To appear.]]

Digital Library

[12]

D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In Proc. of the 7th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2000), 2000. To appear.]]

[13]

S. Chaudhuri, S. Krishnamurthy, S. Potarnianos, and K. Shim. Optimizing queries with materialized views. In Proc. of the 11th IEEE Int. Conf. on Data Engineering (ICDE'95), Waipei (Waiwan), 1995.]]

Digital Library

[14]

J. Clark and S. Deach. Extensible Stylesheet Language (XSL). Technical report, World Wide Web Consortium, 1999. Available at http://www.w3.org/WR/WD-xsl.]]

[15]

S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In Proc. of the 18th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'99), pages 155-166, 1999.]]

Digital Library

[16]

O. M. Duschka and M. R. Genesereth. Answering recursive queries using views. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'97), pages 109-116, 1997.]]

Digital Library

[17]

O. M. Duschka and A. Y. Levy. Recursive plans for information gathering. In Proc. of the 15th Int. Joint Conf. on Artificial Intelligence (IJCAI'97), pages 778-784, 1997.]]

[18]

M. F. Fernandez, D. Florescu, J. Kang, A. Y. Levy, and D. Suciu. Catching the boat with strudel: Experiences with a web-site management system. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 414-425, 1998.]]

Digital Library

[19]

M. F. Fernandez and D. Suciu. Optimizing regular path expressions using graph schemas. In Proc. of the l~th IEEE Int. Conf. on Data Engineering (ICDE'98), pages 14-23, 1998.]]

Digital Library

[20]

M. L. Ginsberg, editor. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, Los Altos, 1987.]]

Digital Library

[21]

G. Grahne and A. O. Mendelzon. Tableau techniques for querying information sources through global schemas. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 332-347. Springer-Verlag, 1999.]]

Digital Library

[22]

J. Gryz. Query folding with inclusion dependencies. In Proc. of the l~th IEEE Int. Conf. on Data Engineering (ICDE'98), pages 126-133, 1998.]]

Digital Library

[23]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley Publ. Co., Reading, Massachussetts, 1979.]]

Digital Library

[24]

A. Y. Levy. Obtaining complete answers from incomplete databases. In Proc. of the 22nd Int. Conf. on Very Large Data Bases (VLDB'96), pages 402-412, 1996.]]

Digital Library

[25]

A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proc. of the l~th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'95), pages 95-104, 1995.]]

Digital Library

[26]

T. Milo and D. Suciu. Index structures for path expressions. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 277-295. Springer-Verlag, 1999.]]

Digital Library

[27]

Y. Papakonstantinou and V. Vassalos. Query rewriting using semistructured views. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, 1999.]]

Digital Library

[28]

A. Rajaraman, Y. Sagiv, and J. D. Ullman. Answering queries using templates with binding patterns. In Proc. of the l~th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'95), 1995.]]

Digital Library

[29]

R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 119-140. Plenum Publ. Co., New York, 1978. Republished in {20}.]]

[30]

D. Srivastava, S. Dar, H. V. Jagadish, and A. Levy. Answering queries with aggregation using views. In Proc. of the 22nd Int. Conf. on Very Large Data Bases (VLDB'96), pages 318-329, 1996.]]

Digital Library

[31]

O. G. Tsatalos, M. H. Solomon, and Y. E. Ioannidis. The GMAP: A versatile tool for phyisical data independence. Very Large Database J., 5(2):101-118, 1996.]]

Digital Library

[32]

J. D. Ullman. Information integration using logical views. In Proc. of the 6th Int. Conf. on Database Theory (ICDT'97), volume 1186 of Lecture Notes in Computer Science, pages 19-40. Springer-Verlag, 1997.]]

Digital Library

[33]

R. van der Meyden. Logical approaches to incomplete information. In J. Chomicki and G. Saake, editors, Logics for Databases and Information Systems, pages 307-356. Kluwer Academic Publishers, 1998.]]

Digital Library

[34]

M. Y. Vardi. The complexity of relational query languages. In Proc. of the l~th A CM SIGA CT Sym. on Theory of Computing (STOC'82), pages 137-146, 1982.]]

Digital Library

[35]

M. Y. Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30(5):261-264, 1989.]]

Digital Library

Cited By

Bonifati AFletcher GVoigt HYakovets N(2022)Querying GraphsundefinedOnline publication date: 25-Feb-2022
Bonifati AIleana I(2018)Graph Data Integration and ExchangeEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_209-1(1-8)Online publication date: 29-Jan-2018
Vardi MMilo TTan W(2016)A Theory of Regular QueriesProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902305(1-9)Online publication date: 15-Jun-2016
Show More Cited By

Index Terms

View-based query processing for regular path queries with inverse
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

View-based query processing: On the relationship between rewriting, answering and losslessness

As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
View-based query processing: on the relationship between rewriting, answering and losslessness
ICDT'05: Proceedings of the 10th international conference on Database Theory

As a result of the extensive research in view-based query processing, three notions have been identi.ed as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
Materialized View Selection & View-Based Query Planning for Regular Path Queries
SIGMOD

A regular path query (RPQ) returns node pairs connected by a path whose edge label sequence satisfies the given regular expression. Given a workload of RPQs, selecting the shared subqueries as materialized views to precompute offline can speed up the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

May 2000

281 pages

ISBN:158113214X

DOI:10.1145/335168

Chairmen:
Victor Vianu
Univ. of California at San Diego, La Jolla
,
Georg Gottlob
Technische Univ. Wien, Vienna, Austria

Copyright © 2000 ACM.

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]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS00

Sponsor:

SIGMOD

SIGMOD/PODS00: ACM International Conference on Management of Data and Symposium on Principles of Database Systems

May 15 - 18, 2000

Texas, Dallas, USA

Acceptance Rates

PODS '00 Paper Acceptance Rate 26 of 119 submissions, 22%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
401
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)9

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bonifati AFletcher GVoigt HYakovets N(2022)Querying GraphsundefinedOnline publication date: 25-Feb-2022
Bonifati AIleana I(2018)Graph Data Integration and ExchangeEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_209-1(1-8)Online publication date: 29-Jan-2018
Vardi MMilo TTan W(2016)A Theory of Regular QueriesProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902305(1-9)Online publication date: 15-Jun-2016
Colazzo DSartiani CCheney JNeumann T(2015)Typing regular path query languages for data graphsProceedings of the 15th Symposium on Database Programming Languages10.1145/2815072.2815082(69-78)Online publication date: 27-Oct-2015
Losemann KMartens W(2013)The complexity of regular expressions and property paths in SPARQLACM Transactions on Database Systems10.1145/249452938:4(1-39)Online publication date: 4-Dec-2013
Barceló PPérez JReutter J(2013)Schema mappings and data exchange for graph databasesProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448520(189-200)Online publication date: 18-Mar-2013
Calvanese DDe Giacomo GLenzerini MVardi M(2013)On simplification of schema mappingsJournal of Computer and System Sciences10.1016/j.jcss.2013.01.00579:6(816-834)Online publication date: 1-Sep-2013
Chen DChirkova RSadri FSalo T(2013)Query optimization in information integrationActa Informatica10.1007/s00236-013-0179-150:4(257-287)Online publication date: 1-Jun-2013
Losemann KMartens WLenzerini MBenedikt M(2012)The complexity of evaluating path expressions in SPARQLProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems10.1145/2213556.2213573(101-112)Online publication date: 21-May-2012
CALVANESE DDE GIACOMO GLENZERINI MNARDI DROSATI R(2012)DATA INTEGRATION IN DATA WAREHOUSINGInternational Journal of Cooperative Information Systems10.1142/S021884300100034510:03(237-271)Online publication date: May-2012
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents