Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

View-Based Query Processing for Regular Path Queries with Inverse


Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi

  View Paper (PDF)  

Return to Views / Query Containment


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


Note: References link to DBLP on the Web.

[1]
Serge Abiteboul : Querying Semi-Structured Data. ICDT 1997 : 1-18
[2]
Serge Abiteboul , Oliver M. Duschka : Complexity of Answering Queries Using Materialized Views. PODS 1998 : 254-263
[3]
Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997)
[4]
Sibel Adali , K. Selçuk Candan , Yannis Papakonstantinou , V. S. Subrahmanian : Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conf. 1996 : 137-148
[5]
Foto N. Afrati , Manolis Gergatsoulis , Theodoros G. Kavalieros : Answering Queries Using Materialized Views with Disjunctions. ICDT 1999 : 435-452
[6]
Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset : Rewriting Queries Using Views in Description Logics. PODS 1997 : 99-108
[7]
Peter Buneman : Semistructured Data. PODS 1997 : 117-121
[8]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[9]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : Answering Queries Using Views in Description Logics. KRDB 1999 : 6-10
[10]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204
[11]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Answering Regular Path Queries Using Views. ICDE 2000 : 389-398
[12]
...
[13]
Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200
[14]
...
[15]
Sara Cohen , Werner Nutt , Alexander Serebrenik : Rewriting Aggregate Queries Using Views. PODS 1999 : 155-166
[16]
Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116
[17]
Oliver M. Duschka , Alon Y. Levy : Recursive Plans for Information Gathering. IJCAI (1) 1997 : 778-784
[18]
Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425
[19]
Mary F. Fernandez , Dan Suciu : Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998 : 14-23
[20]
...
[21]
Gösta Grahne , Alberto O. Mendelzon : Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999 : 332-347
[22]
Jarek Gryz : Query Folding with Inclusion Dependencies. ICDE 1998 : 126-133
[23]
John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02888-X
[24]
Alon Y. Levy : Obtaining Complete Answers from Incomplete Databases. VLDB 1996 : 402-412
[25]
Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104
[26]
Tova Milo , Dan Suciu : Index Structures for Path Expressions. ICDT 1999 : 277-295
[27]
Yannis Papakonstantinou , Vasilis Vassalos : Query Rewriting for Semistructured Data. SIGMOD Conference 1999 : 455-466
[28]
Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112
[29]
Raymond Reiter : On Closed World Data Bases. Logic and Data Bases 1977 : 55-76
[30]
Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329
[31]
Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996)
[32]
Jeffrey D. Ullman : Information Integration Using Logical Views. ICDT 1997 : 19-40
[33]
Ron van der Meyden : Logical Approaches to Incomplete Information: A Survey. Logics for Databases and Information Systems 1998 : 307-356
[34]
Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146
[35]
Moshe Y. Vardi : A Note on the Reduction of Two-Way Automata to One-Way Automata. IPL 30(5) : 261-264(1989)

Referenced by

  1. Moshe Y. Vardi : Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000 : 76-85

BIBTEX


@inproceedings{DBLP:conf/pods/CalvaneseGLV00,
  author    = {Diego Calvanese and
                Giuseppe De Giacomo and
                Maurizio Lenzerini and
                Moshe Y. Vardi},
   title     = {View-Based Query Processing for Regular Path Queries with Inverse},
   booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
                on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
                USA},
   publisher = {ACM},
   year      = {2000},
   isbn      = {1-58113-214-X},
   pages     = {58-66},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.