場所：国立情報学研究所(NII) 20階ミーティングルーム室 (2009/2010)（地図）
お問い合わせ：加藤 弘之 (kato_AT_nii.ac.jp)_AT_を＠に書き換えてください。
Nobutaka Suzuki (Tsukuba University)
Kth-best approaches to two problems related to XML
In this talk, we present two Kth-best approaches to problems related to XML. In the first half of the talk, we introduce a problem related to XML transformation and schema evolution. Let t be an XML document valid against a DTD D, and suppose that D is updated by an update script s. In general, we cannot uniquely “infer” a transformation script for t from s, i.e., we cannot uniquely determine the elements in t that should be deleted and/or the positions in t that new elements should be inserted into. Thus it is useful to infer K-optimum transformation scripts from an update script so that users find the most desirable transformation script among the K transformation scrips. We show an intractability result of this problem, and then present a pseudopolynomial-time algorithm for solving the problem assuming that an update script is of length one.
In the second half of the talk, we introduce a problem related to correcting “invalid” XPath expressions. If a DTD is large and/or complex, it is not easy to write “valid” XPath expressions conforming to the DTD. Thus we propose an algorithm that finds, for a DTD D, an invalid XPath expression p, and a positive integer K, K optimum valid XPath expressions “most similar” to p. Currently, the algorithm assumes that an XPath expression contains only child, descendant-or-self, following-sibling, and preceding-sibling axes and that only a label is allowed as a node test. The similarity between two XPath expressions are measured by the edit distance between XPath expressions. We also show some results on exploratory experiments.
received his B.E. degree in information and computer sciences from Osaka University in 1993, and his M.E. and Ph.D. degrees in information science from Nara Institute of Science and Technology in
1995 and 1998, respectively. He was with Okayama Prefectural University as a Research Associate in 1998-2004. In 2004, he joined University of Tsukuba as an Assistant Professor. Since 2009, he has been an Associate Professor of Graduate School of Library, Information and Media Studies, University of Tsukuba. His current research interests include database theory and structured documents.
Yasunori Ishihara (Osaka University)
Tractability results on XPath satisfiability with sibling axes
XPath satisfiability is one of the major theoretical topics in the field of XML databases. Deciding the satisfiability of a given XPath expression under a given DTD (Document Type Definition) is useful for query optimization on XML databases. The tractability of the satisfiability is, of course, governed by the combination of the classes of XPath expressions and DTDs. The tractability results known so far were only for small subclasses of XPath expressions (e.g., with only downward axes and qualifiers) or small subclasses of DTDs (e.g., disjunction-free DTDs).
The aim of this talk is to introduce broader subclasses of DTDs under which the satisfiability of broader subclasses of XPath expressions is tractable. Especially, we deal with XPath expressions with sibling axes because there were hardly any tractability results on the satisfiability for such XPath expressions. In the first half of the talk, we introduce disjunction-capsuled DTDs, DC-DTDs for short, which are a proper superclass of disjunction-free DTDs. Then, we show several (in)tractability results of XPath satisfiability under DC-DTDs. In the second half of the talk, we provide a condition to extend a class of DTDs without spoiling the tractability of XPath satisfiability, provided that only child, descendant-or-self, parent, ancestor-or-self, following-sibling, and preceding-sibling axes, path union, and qualifier are taken into account. Actually, DC-DTDs can be obtained by applying this condition to disjunction-free DTDs, and hence, DC-DTDs inherit the tractability of disjunction-free DTDs.
Also, by applying the condition to DC-DTDs, a strictly broader but still tractable class of DTDs can be obtained, where operators ? (zero or one occurrence) and + (one or more occurrences) are allowed in regular expressions in a restricted manner.
received the B.E., M.E., and Ph.D. degrees in information and computer sciences from Osaka University in 1990, 1992, and 1995, respectively.
In 1994, he joined the faculty of Graduate School of Information Science, Nara Institute of Science and Technology. From 1999 to 2002, he was an Assistant Professor of Department of Informatics and Mathematical Science, Osaka University. Since April 2002, he has been an Associate Professor of Graduate School of Information Science and Technology, Osaka University. His research interests include database theory and information security.