学会員メーリングリストアーカイブ (2009年)

[dbjapan] Lecture series on database design and query compilation (NII, 2/15-19 & 26, 2010)


NIIの加藤と申します.
本MLをお借りして,以下のお知らせをさせて頂きます.

来年の2月に,NIIで下記のようなlecture seriesが開 催されます.
ご都合がよろしければ,是非ご参加頂ければと存じます.
また,お知り合いでご興味がありそうな方へもお知らせ頂ければと 存じます. 尚,講義レベルはWaterloo大学の 講義番号8xx レベルの研究セミナーに相当し
SIGMODやICDT会議に繋がる内容だそうです.

どうぞよろしくお願い致します.

国立情報学研究所 加藤弘之

----

Lecture Series: Fundamentals of Physical Design and Query Compilation
http://www.nii.ac.jp/index.php?action=pages_view_main&page_id=992

- Lecturer: Dr. David Toman, University of Waterloo, Canada
- Place: National Institute of Informatics, 20F, Meeting Room
- Date: 3pm - 4:30pm, February 15-19 & 26, 2010.
- Fee: Free (registration is not required)
- Inquiry: Zhenjiang Hu (hu [at] nii.ac.jp)

Overall schedule:

Lecture 1: Introduction Goals and Current Practice (2/15)
Lecture 2: Physical Design and Schema Languages (2/16)
Lecture 3: How do we execute queries? (take 1: conjunctive queries) (2/17) Lecture 4: How do we execute queries? (take 2: first-order queries) (2/18)
Lecture 5: Look into the Future (discussion/seminar) (2/19)
Lecture 6: Querying Databases through Ontologies: the "open world" approach (2/26)

Biography:

David Toman is an Associate Professor in the David R. Cheriton School
of Computer Science at the University of Waterloo. His research
focuses on database theory and systems, in particular on query
processing under constraints and on query compilation; on tem aspects
of data management; and on logic in Computer Science, in general. He
has published extensively in his research area including preparing
invited contributions to several reference collections, such as the
Encyclopedia of Database Systems and the Handbook of Temporal
Reasoning in Artificial Intelligence. He has earned Bachelor's and
Master's degrees from the Masaryk University in Czechoslovakia in 1992
and a PhD from Kansas State University in 1996, all in Computer
Science. He has been awarded numerous research grants, among which are
the NATO-NSERC Postdoctoral fellowship and the Ontario Premier's
Research Excellence Award.

Detailed Description:

Lecture 1
Introduction Goals and Current Practice.
Feb 15th, 15h00-16h30 at NII, 20F, 2009 Meeting Room

The current approaches to physical design closely follows conceptual
design: e.g., creating base files for all tables, adding additional
indices, etc. New applications and performance requirements have lead
to the introduction of additional physical structures, e.g.,
materialized views, but query optimization technology has fallen
behind; typically using only ad-hoc techniques for including
materialized views into query plans. The lecture will survey current
practices, identify their weaknesses and outline possible
solutions. It will also introduce the unifying theme for the remaining
lectures: the development of an uniform and integrated approach to
physical design that is decoupled from conceptual schemes and to query
compilation and optimization in this setting.

Lecture 2
Physical Design and Schema Languages.
Feb 16th, 15h00-16h30 at NII, 20F, 2009 Meeting Room

How do we describe actual physical designs and how do we link them to
a conceptual view of the data? The lecture will review data models and
integrity constraints with the help of Description Logic and show how
such a development relates to classical database constraints such as
functional and inclusion dependencies. Furthermore it will discuss
additional annotations, such as binding patterns and their use to
describe physical designs, possibly up to the level of (sets of)
main-memory records connected by pointers. The theoretical
underpinnings will be accompanied by examples of fine-grained
descriptions of physical designs by elaborating on traditionally
monolithic data structures (such as B+ trees) via constraints. It will
also consider the reasoning complexity (decidability) vs. expressive
power trade-offs in schema languages: what the right trade-off and the
impact on query languages, query evaluation, and query "safety" issues
might be.

Lecture 3
How do we execute queries? (take 1: conjunctive queries)
Feb 17th, 15h00-16h30 at NII, 20F, 2009 Meeting Room

The lecture will study chase-based approaches to query rewriting and
its limitations (e.g., the inability of rewriting conjunctive queries
over conjunctive views); the impact of binding patterns for accessing
indices, and the integration with (simple) cost models. Other issues
discussed in this lecture will relate to handling duplicates and order
of data and to approaches for accommodating these crucial features in
query plans.

Lecture 4
How do we execute queries? (take 2: first-order queries)
Feb 18th, 15h00-16h30 at NII, 20F, 2009 Meeting Room

The lecture will first discuss shortcomings of existing approaches to
rewriting complex queries based on ad-hoc approaches, such as the
query graph model (QGM), and then introduce a novel technique based on
the application of Craig's Interpolation Theorem to the query
rewriting problem, in particular it will show how to extract
rewritings from refutation proofs. In addition it will discuss the
usual extensions needed for efficient query processing, e.g., binding
patterns, duplicates, and ordering.

Lecture 5
Look into the Future (discussion/seminar)
Feb 19th, 15h00-16h30 at NII, 20F, 2009 Meeting Room

The last lecture (organized as a seminar) will conclude with an
overview of topics for future investigation and research: the topics
will relate to studying constraints and queries beyond first-order
logic, such as Datalog/inductive data types and their impact on
physical design and query processing, the issue of updates in a
decoupled conceptual and physical designs, and the impact of
transactions.

Lecture 6
Querying Databases through Ontologies: the "open world" approach.
Feb 26th, 15h00-16h30 at NII, 20F, 2005 Lecture Room

The presentation will consider an alternative to query rewriting
(equivalent under constraints): the computation of certain answers. It
will introduce the approach and discuss its computational price in
terms of how powerful query and constraint languages are used. It will
show that such an approach is computationally feasible for only
relatively weak languages. It will then discuss the possibility of
generating certain answer based on first-order rewritability in such a
setting, i.e., for conjunctive queries over ontologies formulated in
families of suitably restricted description logics, such as ELH and
DL-Lite.