- Y. Papakonstantinou, V. Vassalos "Rewriting
Queries Using Semistructured Views"(pdf)
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
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.
"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),
Optimization in Mediators" (ps)
In AAAI98 Workshop on AI and Data Integration.
similarities and differences between metasearchers, as
known in the IR community, and mediators, as known in the
- L. Segoufin and V. Vianu: Querying
spatial databases via topological invariants(ps), PODS
- S. Abiteboul, V. Vianu, B. Fordham, Y. Yesha: Relational
Transducers for Electronic Commerce (ps), PODS
- 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.
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
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
- V. Vassalos, Y. Papakonstantinou "Describing
and Using Query Capabilities of Heterogeneous
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
- S. Abiteboul and V. Vianu: Queries
and computation on the Web (ps), Proc.
Int'l. Conf. on Database Theory,
- 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
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).
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
- 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
- S. Grumbach and V.Vianu: Tractable
Query Languages for Complex Object Databases (ps), J.
of Computer and System Sciences ,
- H. Garcia-Molina , Y. Papakonstantinou , D. Quass , A.
Rajaraman , Y. Sagiv , J. Ullman , V. Vassalos , J. Widom
TSIMMIS approach to mediation: Data models and
In Journal of Intelligent Information
- 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
Stanford University Thesis, 1997.
Paper saving condensed
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.
Caching and Optimization in Mediator Systems"(pdf).
In ACM SIGMOD 96.
- Y. Papakonstantinou, H. Garcia-Molina, J. Ullman. "MedMaker:
A Mediation System Based on Declarative
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.
Query Translation Scheme for Rapid Implementation of
In DOOD 95.
- S. Lifschitz and V. Vianu: A Probabilistic View
of Datalog Parallelization, Proc.
Int'l. Conf. on Database Theory ,
version(ps) in Theoretical
Computer Science , vol. 190,
- N. Roussopoulos, C.M. Chen, S. Kelley, A. Delis, Y.
ADMS Project: Views R Us"(pdf). (ps)
In IEEE Data Engineering Bulletin,
- Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. "Object
Exchange Across Heterogeneous Information
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
In NGITS 95
- S.Abiteboul, M.Vardi and V.Vianu: Computing
with Infinitary Logic (ps), Theoretical
Computer Science , 149, 1995,
- H. Garcia-Molina, J. Hammer, K. Ireland, Y.
Papakonstantinou, J. Ullman, and J. Widom. "Integrating
and Accessing Heterogeneous Information Sources in
In Proceedings of the AAAI Symposium on
Information Gathering,Stanford, California,
- S.Abiteboul, C.H. Papadimitriou and V.Vianu: The
Power of the Reflective Relational Machine (ps), Proc.
IEEE Symp. on Logic in Computer Science,
- S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland,
Y. Papakonstantinou, J. Ullman, and J. Widom. "The
TSIMMIS Project: Integration of Heterogeneous Information
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