Cited By
View all- Benczúr ASzabó G(2016)Towards a Normal Form and a Query Language for Extended Relations Defined by Regular ExpressionsJournal of Database Management10.4018/JDM.201604010227:2(27-48)Online publication date: 1-Apr-2016
Functional dependencies on extended relations defined by regular languages
Pages 205 - 243
Abstract
Functional dependency (FD) is one of the most analyzed integrity constraints for any data model. In the relational data model, FDs are defined in a natural way: the values of an attribute set Y depend on the values of another attribute set X, that is, "Y is a function of X". FDs are well studied and are widely used in normalization theory. XML functional dependencies (XFD) can be defined in different ways and no universally best definition has been proposed. They are defined by very intricate concepts, and they are mostly based upon XML elements described by XML schema languages such as a DTD or an XML Schema definition. The instances of these elements are semi-structured tuples. A semi-structured tuple is an ordered list of (attribute: value) pairs. We may think of a tuple as a sentence of a formal language, where the values are the terminal symbols and the attribute names are the nonterminal symbols. In this way, the sequence of the attribute names is the left side of a production rule used to accept the next terminal symbol, that is, the next value of the tuple. So the list of values forms the sentence and the list of attributes forms the dual sentence. In this paper, we introduce the notion of the extended tuple as a sentence from a regular language generated by a grammar where the nonterminal symbols of the grammar are the attribute names of the tuple. Sets of extended tuples are the extended relations (relations are instances). We then introduce the dual language, which generates the tuple types allowed to occur in extended relations. We define functional dependencies over extended relations. The syntax of functional dependencies will be given on the graph of the finite state automaton accepting the regular language. Using this model, we can also handle extended relations generated by recursive regular expressions. The implication problem of our class of dependencies is decidable and finitely axiomatizable by a version of the Chase algorithm performed on the graph of the associated finite state automaton.
References
[1]
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)
[2]
Amano, S., Libkin, L., Murlak, F.: XML schema mappings. In: Proc. PODS, pp. 33---42 (2009)
[3]
Arenas, M., Libkin, L.: A normal form for XML documents. ACM Trans. Datab. Syst. 29, 195---232 (2004)
[4]
Atzeni, P., Morfuni, N.: Functional dependencies and constraints on null values in database relations. Inf. Control 70(1), 1---31 (1986)
[5]
Berry, G., Sethi, R.: From regular expressions to deterministic automata. Theor. Comput. Sci. 48, 117---126 (1986)
[6]
Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481---494 (1964)
[7]
Buneman, P., Davidson, S.B., Fan, W., Hara, C.S., Tan, W.C.: Keys for XML. Comput. Netw. 39(5), 473---487 (2002)
[8]
Buneman, P., Davidson, S.B., Fan, W., Hara, C.S., Tan, W.C.: Reasoning about keys for XML. Inf. Syst. 28(8), 1037---1063 (2003)
[9]
Champarnaud, J.-M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289(1), 137---163 (2002)
[10]
Chen, Y., Davidson, S.B., Zheng, Y.: Constraint preserving XML storage in relations. In: Proceedings of the International Workshop on the Web and Databases (WEBDB), pp. 7---12 (2002)
[11]
Davidson, S., Fan, W., Hara, C.: Propagating XML constraints to relations. J. Comput. Syst. Sci. 73(3), 316---361 (2007)
[12]
Fagin, R.: Functional dependencies in a relational database and propositional logic. IBM J. Res. Develop. 21(6), 543---544 (1977)
[13]
Fischer, P.C., Saxton, L.V., Thomas, S.J., Van Gucht, D.: Interactions between dependencies and nested relational structures. J. Comput. Syst. Sci. 31(3), 343---354 (1985)
[14]
Glushkov, V.M.: The abstract theory of automata. Russ. Math. Surv. 16, 1---53 (1961)
[15]
Hara, C.S., Davidson, S.B.: Reasoning about nested functional dependencies. In: Proc. PODS, pp. 91---100 (1999)
[16]
Hartmann, S., Link, S: More functional dependencies for XML. In: Proc. ADBIS, pp. 355---369 (2003)
[17]
Hartmann, S., Link, S., Schewe, K-D.: Functional dependencies over XML documents with DTDs. Acta Cybern. 17(1), 153---171 (2005)
[18]
Hartmann, S., Link, S., Schewe, K-D.: Axiomatisation of functional dependencies in the presence of records, lists, sets and multisets. Theor. Comput. Sci. 355, 167---196 (2006)
[19]
Hartmann, S., Link, S: Characterising nested database dependencies by fragments of propositional logic. Ann. Pure Appl. Logic 152, 84---106 (2008)
[20]
Hartmann, S., Link, S.: Efficient reasoning about a robust XML key fragment. ACM Trans. Datab. Syst. 34(2), 1---33 (2009)
[21]
Hartmann, S., Link, S: Numerical constraints on XML data. Inf. Comput. 208(5), 521---544 (2010)
[22]
Hartmann, S., Köhler, H., Trinh, T.: On the existence of Armstrong data trees for XML functional dependencies. In: Proc. FoIKS LNCS, vol. 5956, pp. 94---113 (2010)
[23]
Hartmann, S., Link, S., Trinh, T.: Solving the implication problem for XML functional dependencies with properties. In: Logic, Language, Information and Computation, 17th International Workshop, WoLLIC, pp. 161---175 (2010)
[24]
Kot, L., White, W.: Characterization of the interaction of XML functional dependencies with DTDs. In: Proc. ICDT, pp. 119---133 (2007)
[25]
Lee, D., Mani, M., Murata, M.: Reasoning about XML schema languages using formal language theory. Technical Report, IBM Almaden Research Center (2000). http://www.cs.ucla.edu/dongwon/paper
[26]
Liu, C., Vincent, M.W., Liu, J.: Constraint preserving transformation from relational schema to XML schema. WWW 9(1), 93---110 (2006)
[27]
Lv, T., Yan, P.: Mapping relational schemas to XML DTDs with constraints. In: Proc. First International Multi-Symposiums on Computer and Computational Sciences, pp. 528---533 (2006)
[28]
Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Technol. 5(4), 660---704 (2005)
[29]
Nicaud, C., Pivoteau, C., Razet, B.: Average analysis of Glushkov automata under a BST-like model. In: Proc. FSTTCS, pp. 388---399 (2010)
[30]
Sali, A., Schewe, K-D.: Counter-free keys and functional dependencies in higher-order datamodels. Fundam. Inform. 70(3), 277---301 (2006)
[31]
Sperberg-McQueen, C.M., Thompson, H.: XML schema. Technical report, World Wide Web Consortium (2005). http://www.w3.org/XML/Schema
[32]
Szabó, G.I., Benczúr, A.: Functional dependencies on extended relations defined by regular languages. In: Proc. FoIKS LNCS, vol. 7153, pp. 385---404 (2012)
[33]
Vincent, M.W., Liu, J., Liu, C.: Strong functional dependencies and their application to normal forms in XML. ACM Trans. Datab. Syst. 29, 445---462 (2004)
[34]
Vincent, M.W., Liu, J., Mohania, M.K.: On the equivalence between FDs in XML and FDs in relations. Acta Informatica 44, 207---247 (2007)
[35]
Wang, J.: A comparative study of functional dependencies for XML. In: APWeb, pp. 308---319 (2005)
[36]
Wang, J., Topor, R.W.: Removing XML data redundancies using functional and equality-generating dependencies. In: Proc. ADC 2005, pp. 65---74 (2005)
[37]
Watson, B.W.: A taxonomy of finite automata construction algorithms. In: Computing Science Note, pp. 93---43. Eindhoven University of Technology, The Netherlands (1993)
[38]
Yu, C., Jagadish, H.V.: XML schema refinement through redundancy detection and normalization. VLDB J. 17(2), 203---223 (2008)
[39]
Zhou, R., Liu, C., Li, J.: Holistic constraint-preserving transformation from relational schema into XML schema. In: Proc. DSFAA, pp. 4---18 (2008)
- Functional dependencies on extended relations defined by regular languages
Recommendations
Towards a Normal Form and a Query Language for Extended Relations Defined by Regular Expressions
This paper introduces a generalized data base concept that unites relational and semi structured data models. As an important theoretical result we could find a quadratic decision algorithm for the implication problem of functional and join dependencies ...
On Defining Functional Dependency for XML
ICSC '09: Proceedings of the 2009 IEEE International Conference on Semantic ComputingFunctional dependency (FD) is one of the integrity constraints for any data model. In relational data model, FDs are well studied and are widely used in normalization theory and in key algorithm. In recent years, XML has emerged as an widely used data ...
Mapping DTDs to relational schemas with semantic constraints
XML is becoming a prevalent format and standard for data exchange in many applications. With the increase of XML data, there is an urgent need to research some efficient methods to store and manage XML data. As relational databases are the primary ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer International Publishing Switzerland.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 January 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
Cited By
View all- Benczúr ASzabó G(2016)Towards a Normal Form and a Query Language for Extended Relations Defined by Regular ExpressionsJournal of Database Management10.4018/JDM.201604010227:2(27-48)Online publication date: 1-Apr-2016
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in