Publications of the UCSD DB lab

Y. Papakonstantinou, V. Vassalos "Rewriting Queries Using Semistructured Views"(pdf) (ps) (Talk) In ACM SIGMOD 99. We present an algorithm that, given a semistructured query q and a set of semistructured views V, finds rewriting queries, i.e., queries that access the views and produce the same result with q. The algorithm is based on generalizing containment mappings, the chase, and unification. We prove that all rewriting queries are found and we characterize the complexity. Applications of the algorithm include (i) reformulating queries in order to use materialized views or a cache and (ii) rewriting queries in order to adapt them to the limited capabilities of semistructured sources.
C. Baru, A. Gupta, B. Ludaescher, R. Marciano, Y. Papakonstantinou, P. Velikhov, "XML-Based Information Mediation with MIX"(pdf) (ps) In Exhibitions Program of ACM SIGMOD 99.
Y. Papakonstantinou, P. Velikhov "Enhancing Semistructured Data Mediators with Document Type Definitions"(pdf) (ps) In Data Engineering 99. Mediators, such as MIX, have to provide DTDs of the views that they compute in order to facilitate query formulation, query processing, and so on. However, a view has more than one DTDs. We propose two quality metrics of view DTDs - roughly similar to "precision" and "recall". The first one, soundness, requires that every possible view document is described by the view DTD. The second one, tightness, requires that the view DTD describes the minimum number of documents that may not appear in the view (ideally, the number is zero). Finally we describe an algorithm for deriving a sound and tight view DTD given a view that has a single variable in the head (SELECT clause) and no recursion (or regular expressions) in the body (WHERE clause).
B. Ludaescher, Y. Papakonstantinou, P. Velikhov, V. Vianu "View Definition and DTD Inference for XML" Post-ICDT Workshop on Query Processing for Semistructured Data and Non-Standard Data Formats, 99.
C. Baru, B. Ludaescher, Y. Papakonstantinou, P. Velikhov, V. Vianu "Features and Requirements for an XML View Definition Language: Lessons from XML Information Mediation" Position paper in W3C's Query Language Workshop.
L. Gravano, Y. Papakonstantinou "Mediating and Metasearching on the Internet"(pdf) (ps)In Data Engineering Bulletin 21(2), 1998. Query Optimization in Mediators" (ps) In AAAI98 Workshop on AI and Data Integration. Discusses the similarities and differences between metasearchers, as known in the IR community, and mediators, as known in the database community.
L. Segoufin and V. Vianu: Querying spatial databases via topological invariants(ps), PODS 98.
S. Abiteboul, V. Vianu, B. Fordham, Y. Yesha: Relational Transducers for Electronic Commerce (ps), PODS 98.
Chen Li, R. Yerneni, V. Vassalos, H. Garcia-Molina, Y. Papakonstantinou, J. Ullman "Capability-Based Mediation in TSIMMIS"(pdf) (ps) In Exhibits Program of SIGMOD 98.
R. Yerneni, Y. Papakonstantinou, S. Abiteboul, H. Garcia-Molina "Fusion Query Optimization" (ps) In EDBT 98. Mediators create virtual entities from information that is distributed across multiple sources. Fusion queries select the entities that satisfy some user-specified conditions. The fusion query optimization problem becomes particularly challenging when the conditions have to be tested on multiple sources. We show that under common assumptions a limited class of plans, the semijoin adaptive plans, contain the optimal fusion plan. An experimental evaluation delivers further results on choosing the optimal fusion plan.
V. Vassalos, Y. Papakonstantinou "Expressive Capabilities Description Languages and Query Rewriting Algorithms" (ps) In Journal of Logic Programming.Extends the formal arguments and improves the algorithms of the VLDB 97 paper. In addition, it shows (1) how the query capabilities of a mediator can be automatically computed from the query capabilities of the sources and (2) a limited (yet practically very common) class of descriptions for which the algoriths are much more efficient.
V. Vassalos, Y. Papakonstantinou "Describing and Using Query Capabilities of Heterogeneous Sources". (ps) In VLDB 97. First the paper compares the capabilities expressive power of RQDL and p-Datalog. The latter is a version of Datalog where the expansions of the Datalog program that have only EDBs stand for the set of supported queries. We prove that p-Datalog is not sufficient for expressing the capabilties of "powerful" sources such as SQL DBs; on the other hand RQDL is powerful enough to describe such sources. Then we describe a reduction of RQDL into Datalog with function symbols and based on this reduction some efficient CBR algorithms are derived.
S. Abiteboul and V. Vianu: Regular path queries with constraints(ps), Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 1997.
S. Abiteboul and V. Vianu: Queries and computation on the Web (ps), Proc. Int'l. Conf. on Database Theory, 262-275, 1997.
V. Vianu: Rule-Based Languages (ps), Annals of Mathematics and Artificial Intelligence,vol. 19, 215-259, 1997.
V. Vianu: Databases and Finite-Model Theory (ps), AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.31, N. Immerman and P. Kolaitis eds, vol. 31, pp. 97-148, 1997.
Y. Papakonstantinou, A. Gupta, L. Haas "Capabilities-Based Query Rewriting in Mediator Systems (Extended Version)"(pdf) (ps) In Distributed And Parallel Databases, 6(1), Jan 98. Extends PDIS 96. It also extends the Capabilities Based Rewriting algorithm with the appropriate hooks for cost optimization and describes what plan pruning may be performed without losing the CBR's completeness. Finally it compares the CBR architecture with a real CBR-enhanced optimizer that was developed for Garlic.
Y.Papakonstantinou, A. Gupta, L. Haas. "Capabilities-Based Query Rewriting in Mediator Systems"(pdf). (ps) In PDIS 96. Selected in the "Best of PDIS". A mediator has to make sure that the queries that it sends to the sources are supported by them. Furthermore, the mediator has to leverage as much as possible on the source query capabilities. The described Capabilities-Based Rewriter (CBR) module of a mediator takes as input (i) a description of the queries supported by the underlying sources and (ii) a client Select-Project-Join query. From these it determines SPJ sub-queries to be sent to the sources (the sub-queries are commensurate to the sources' abilities) and computes a plan for combining the sub-queries' results using selection, projections, and joins. The description of the supported queries is done in RQDL, a description language that can be schema independent and can describe infinitely many "query patterns".
C.H. Papadimitriou, D. Suciu and V. Vianu: Topological Queries in Spatial Databases (ps), Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 81-92, 1996. Full paper.
P. Picouet and V. Vianu: Semantics and Expressiveness Issues in Active Databases (ps), Proc. ACM SIGACT-SIGART-SIGMOD Symp. on Principles of Database Systems , 19 95, 126-138. Full paper (preliminary version), invited to J. of Computer and System Sciences
S. Grumbach and V.Vianu: Tractable Query Languages for Complex Object Databases (ps), J. of Computer and System Sciences , 51:2,1995, 149-167.
H. Garcia-Molina , Y. Papakonstantinou , D. Quass , A. Rajaraman , Y. Sagiv , J. Ullman , V. Vassalos , J. Widom "The TSIMMIS approach to mediation: Data models and Languages"(pdf). (ps) In Journal of Intelligent Information Systems".
Y.Papakonstantinou, S. Abiteboul, H. Garcia-Molina. "Object Fusion in Mediator Systems"(pdf). (ps) In VLDB 96. Mediators fuse information from multiple heterogeneous information sources. In the process they remove redundancies and resolve inconsistencies. The problem becomes harder when the sources are unstructured/semistructured and we do not have complete knowledge of their contents and structure. We show the use of skolem constants in the view definition language of the TSIMMIS mediator.
Y. Papakonstantinou "Query Processing in Heterogeneous information systems"(pdf). (ps) Stanford University Thesis, 1997. Paper saving condensed version(pdf). (ps) Is the result of 4 years at Stanford this document which has been read by 3 people? Are such facts demoralizing for graduate students? They should be. Now the ball is in your field: By clicking one of the links you give hope to current and future graduate students who wonder why they spend their 20's to write a document that only three people will read. BTW, insofar that's the only document that covers both MSL's query processing and capabilities issues.
S. Adali, S. Candan, Y. Papakonstantinou, V.S. Subrahmanyan. "Query Caching and Optimization in Mediator Systems"(pdf). (ps) In ACM SIGMOD 96.
Y. Papakonstantinou, H. Garcia-Molina, J. Ullman. "MedMaker: A Mediation System Based on Declarative Specifications"(pdf). (ps) In ICDE 96.
S.Abiteboul and V.Vianu: Computing with First-Order Logic (ps), J. of Computer and System Sciences , 50:2, 1995, 309-335.
Y.Papakonstantinou, A. Gupta, H. Garcia-Molina, J. Ullman. "A Query Translation Scheme for Rapid Implementation of Wrappers"(pdf). (ps) In DOOD 95.
S. Lifschitz and V. Vianu: A Probabilistic View of Datalog Parallelization, Proc. Int'l. Conf. on Database Theory , 1995. Full version(ps) in Theoretical Computer Science , vol. 190, 211-239, 1998.
N. Roussopoulos, C.M. Chen, S. Kelley, A. Delis, Y. Papakonstantinou. "The ADMS Project: Views R Us"(pdf). (ps) In IEEE Data Engineering Bulletin, June 95.
Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. "Object Exchange Across Heterogeneous Information Sources"(pdf). (ps) In Proceedings of ICDE, Taipei, Taiwan, March 1995. This paper describes the (strikingly similar to XML) semistructured Object Exchange Model (OEM) and describes its suitability in mediating over heterogeneous and Internet sources. The paper also provides the first description of wrappers and mediators. Two years later XML was formulated and by 1998 you'd find hundreds of quotations by industry people on the suitability of XML for mediation and information exchange. We are happy to be there 4 years ahead!
J. Hammer, H. Garcia-Molina, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. "Information Translation, Mediation, and Mosaic-Based Browsing in the TSIMMIS System"(pdf). (ps) In Exhibits Program of ACM SIGMOD, San Jose, California, June 1995.
H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A. Rajaraman, Y. Sagiv, J. Ullman, J. Widom. "The TSIMMIS approach to Mediation: Data Models and Languages"(pdf). (ps) In NGITS 95
S.Abiteboul, M.Vardi and V.Vianu: Computing with Infinitary Logic (ps), Theoretical Computer Science , 149, 1995, 101-128.
H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. "Integrating and Accessing Heterogeneous Information Sources in TSIMMIS"(pdf). (ps) In Proceedings of the AAAI Symposium on Information Gathering,Stanford, California, March 1995.
S.Abiteboul, C.H. Papadimitriou and V.Vianu: The Power of the Reflective Relational Machine (ps), Proc. IEEE Symp. on Logic in Computer Science, Paris, 1994.
S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. "The TSIMMIS Project: Integration of Heterogeneous Information Sources". (ps) In Proceedings of the 100th IPSJ Anniversary Meeting, Tokyo, Japan, October 1994.
S. Abiteboul, M. Vardi, and V. Vianu: Fixpoint Logics, Relational Machines, and Computational Complexity (ps), Proc. Conf. on Structure in Complexity Theory , 1992. Full version(ps) J. of the ACM , 44(1), 30-56, 1997.
G. Papakonstantinou (Dept. of Electr. Eng., Nat. Tech.Univ. of Athens, Greece), T. Panayiotopoulos, N. Georgoulis, and Y. Papakonstantinou. "A parallel full theorem prover with uncertainties". In Parallel and Distributed Computing in Engineering Systems. Proceedings of the IMACS/IFAC International Symposium., pages 117-21, Corfu, Greece, 23-28 June 1991.
A. Stafylopatis (Dept. of Electr. Eng., Nat. Tech.Univ. of Athens, Greece), Y. Papakonstantinou, and S. Kaxiras. "PSM: software tool for simulating, prototyping, and monitoring of multiprocessor systems". Information and Software Technology, May 1992, vol.34, no.5, pages 313-28.