Abstract
Data trees serve as an abstraction of XML documents: in such trees, every node comes with a label from a finite alphabet, as well as a data value from an infinite set. Incomplete data trees model XML documents with incomplete information; they may include both structural incompleteness and incompleteness of data. Here we study two basic problems for incomplete data trees under typical constraints such as keys and foreign keys. The first problem is consistency of specifications of incomplete data trees. We show that many of recently established results on consistency of constraints and schema descriptions can be transferred to the consistency of incomplete tree specifications without any increase in complexity. After that we examine query answering over incomplete data trees under constraints, and show that tractable bounds can be recovered under key constraints, but are lost under foreign keys.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arenas, M., Fan, W., Libkin, L.: On the complexity of verifying consistency of XML specifications. SIAM J. Comput. 38, 841–880 (2008)
Arenas, M., Libkin, L.: XML data exchange: consistency and query answering. Journal of the ACM 55, 2 (2008)
Barceló, P., Libkin, L., Poggi, A., Sirangelo, C.: XML with incomplete information. Journal of the ACM 58, 1 (2010)
Barceló, P., Libkin, L., Reutter, J.: On incomplete XML documents with integrity constraints. In: AMW 2010 (2010)
Björklund, H., Martens, W., Schwentick, T.: Conjunctive query containment over trees. J. Comput. Syst. Sci. 77(3), 450–472 (2011)
Bojanczyk, M.: Automata for data words and data trees. In: RTA 2010, pp. 1–4 (2010)
Bojanczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data words. ACM Trans. Comput. Log. 12(4), 27 (2011)
Bojanczyk, M., Lasota, S.: An extension of data automata that captures XPath. Logical Methods in Computer Science 8(1) (2012)
Buneman, P., Davidson, S., Fan, W., Hara, C., Tan, W.-C.: Keys for XML. Computer Networks 39(5), 473–487 (2002)
Calì, A., Lembo, D., Rosati, R.: On the decidability and complexity of query answering over inconsistent and incomplete databases. In: PODS 2003, pp. 260–271 (2003)
Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Regular XPath: constraints, query containment and view-based answering for XML documents. In: LID (2008)
David, C., Libkin, L., Tan, T.: Efficient reasoning about data trees via integer linear programming. ACM TODS 37(3), 19 (2012)
Fan, W., Libkin, L.: On XML integrity constraints in the presence of DTDs. Journal of the ACM 49, 368–406 (2002)
Figueira, D.: Forward-XPath and extended register automata on data-trees. In: ICDT 2010, pp. 231–241 (2010)
Figueira, D.: Bottom-up automata on data trees and vertical XPath. In: STACS 2011, pp. 93–104 (2011)
Gheerbrant, A., Libkin, L., Tan, T.: On the complexity of query answering over incomplete XML documents. In: ICDT 2012, pp. 169–181 (2012)
Gottlob, G., Koch, C., Schulz, K.: Conjunctive queries over trees. Journal of the ACM 53(2), 238–272 (2006)
Imieliński, T., Lipski, W.: Incomplete information in relational databases. Journal of the ACM 31(4), 761–791 (1984)
Jan Bex, G., Neven, F., Van den Bussche, J.: DTD versus XML Schema: A Practical Study. In: WEBDB 2004, pp. 79–84 (2004)
Laender, A., Moro, M., Nascimento, C., Martins, P.: An X-Ray on Web-Available XML Schemas. SIGMOD Record 38(1), 37–42 (2009)
Libkin, L., Sirangelo, C.: Reasoning about XML with temporal logics and automata. J. Applied Logic 8(2), 210–232 (2010)
Martens, W., Neven, F., Schwentick, T.: Simple off the shelf abstractions for XML schema. SIGMOD Record 36(3), 15–22 (2007)
Segoufin, L.: Automata and logics for words and trees over an infinite alphabet. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 41–57. Springer, Heidelberg (2006)
Segoufin, L.: Static analysis of XML processing with data values. SIGMOD Record 36(1), 31–38 (2007)
Tan, T.: An automata model for trees with ordered data values. In: LICS 2012 (2012)
Thatcher, J.W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. JCSS 1, 317–322 (1967)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Gheerbrant, A., Libkin, L., Reutter, J. (2013). Static Analysis and Query Answering for Incomplete Data Trees with Constraints. In: Tannen, V., Wong, L., Libkin, L., Fan, W., Tan, WC., Fourman, M. (eds) In Search of Elegance in the Theory and Practice of Computation. Lecture Notes in Computer Science, vol 8000. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41660-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-41660-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41659-0
Online ISBN: 978-3-642-41660-6
eBook Packages: Computer ScienceComputer Science (R0)