Abstract
Data dependencies are well known in the context of relational database. They aim to specify constraints that the data must satisfy-to model correctly the part of the world under consideration. The implication problem for dependencies is to decide whether a given dependency is logically implied by a given set of dependencies. A proof procedure for the implication problem, called “chase”, has already been studied in the generalized case of tuple-generating and equality-generating dependencies. The chase is a bottom-up procedure: from hypotheses to conclusion, and thus is not goal-directed. It also requires the dynamic creation of new symbols. This paper introduces a new proof procedure which is top-down: from conclusion to hypothesis, that is goal-directed. The originality of this procedure is that it does not act as classical theorem proving procedures, by requiring a special form of expressions, such as clausal form, obtained after skolemisation. We show, with our procedure, that this step is useless, and that the notion of piece allows inferring directly on dependencies, without dynamically creating new symbols. With the recent introduction of constrained dependencies, some interesting perspectives also arise.
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
Marianne Baudinet, Jan Chomicki, and Pierre Wolper. Constraint-generating dependencies. In Georg Gottlob and Moshe Y. Vardi, editors, Database Theory— ICDT’95, 5th International Conference, volume 893of Lecture Notes in Computer Science, pages 322–337, Prague, Czech Republic, 11–13January1995. Springer.
Catriel Beeri, Ronald Fagin, and John H. Horward. A complete axiomatization for functional and multivalued dependencies in database relations. In Diane C. P. Smith, editor, Proceedings of the 1977 ACM SIGMOD International Conference on Management of Data, pages 47–61, Toronto, Canada, 3–5 August1977. ACM, New York.
François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 1–16, Cambridge, Massachusetts, 24–26 Marseille 1986.
Catriel Beeri and Moshe Y. Vardi. The implication problem for data dependencies. In Shimon Even and Oded Kariv, editors, Automata, Languages and Programming, 8th Colloquium, volume 115 of Lecture Notes in Computer Science, pages 73–85, Acre (Akko), Israel, 13–17 July 1981. Springer-Verlag.
C. Beeri and M. Y. Vardi. Formal systems for tuple and equality generating dependencies. SIAM Journal on Computing, 13(l):76–98, 1984.
Catriel Beeri and Moshe Y. Vardi. A proof procedure for data dependencies. Journal of the ACM, 31(4):718–741, October 1984.
E. F. Codd. Further Normalization of the Database Relational Model. R. Rustin, Ed.. Prentice-Hall, Englewood Cliffs, NJ, 1972.
Stphane Coulondre. A top-down proof procedure for data dependencies. Technical report, LIRMM, Montpellier, France, 2000.
Stéphane Coulondre and Eric Salvat. Piece resolution: Towards larger perspectives. In Proceedings of the Sixth International Conference on Conceptual Structures (ICCS-98), Montpellier, France, 1998.
R. Fagin and M. Y. Vardi. The theory of data dependencies: a survey. In Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics, volume 34, pages 19–72. American Mathematical Society, 1986.
Yuri Gurevich and Harry R. Lewis. The inference problem for template dependencies. Information and Control, 55(1–3):69–79, October/November/December 1982.
David Genest and Eric Salvat. A platform allowing typed nested graphs: How cogito became cogitant. In Proceedings of the Sixth International Conference on Conceptual Structures (ICCS-98), LNAI, Berlin, 1998. Springer-Verlag.
Christian Herrmann. On the undecidability of implications between embedded multivalued database dependencies. Information and Computation, 122(2):221–235, 1 November1995.
C. S. Jensen and R. T. Snodgrass. Temporal specialization. In F. Golshani, editor, Proceedings of the International Conference on Data Engineering, pages 594–603, Tempe, AZ, February1992. IEEE.
Mark Levene and George Loizou. The additivity problem for functional dependencies in incomplete relations. Acta Informatica, 34(2):135–149, 1997.
Mark Levene and George Loizou. Null inclusion dependencies in relational databases. Information and Computation, 136(2):67–108, 1 August1997.
M. Levene and G. Loizou. The additivity problem for data dependencies in incomplete relational databases. Lecture Notes in Computer Science, 1358:136-?? 1998.
Michael Maher. Constrained dependencies. In Proceedings ILPS’94 Workshop on Constraints and Databases, Ithaca, November 1994.
M. J. Maher. Constrained dependencies. Theoretical Computer Science, 173(1):113–149, February 1997.
M. J. Maher and D. Srivastava. Chasing constrained tuple-generating dependencies. In PODS’ 96. Proceedings of the Fifteenth ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1996, Montréal, Canada, June 3–5, 1996, volume 15, pages 127–138, New York, NY 10036, USA, 1996. ACM Press.
Eric Salvat. Raisonner avec des oprations de graphes: graphes conceptuels et règles d’inférence. PhD thesis, Université Montpellier II, Montpellier, France, December 1997.
Edward Sciore. A complete axiomatization of full join dependencies. Journal of the ACM, 29(2):373–393, April 1982.
Iztok Savnik and Peter A. Flach. Discovery of multivalued dependencies from relations. Technical Report report00135, Albert-Ludwigs-Universitaet Freiburg, Institut fuer Informatik, Marseille 6, 2000.
Eric Salvat and Marie-Laure Mugnier. Sound and complete forward and backward chainings of graph rules. In Proceedings of the Fourth International Conference on Conceptual Structures (ICCS-96), volume 1115 of LNAI, pages 248–262, Berlin, August l9–22 1996. Springer.
J. F. Sowa. Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, Reading, Mass., 1984.
K. Sagonas, T. Swift, and D. S. Warren. XSB as a deductive database. SIGMOD Record (ACM Special Interest Group on Management of Data), 23(2):512–512, June1994.
Fereidoon Sadri and Jeffrey D. Ullman. Template dependencies: A large class of dependencies in relational databases and its complete axiomatization. Journal of the ACM, 29(2):363–372, April 1982.
Hisao Tamaki and Taisuke Sato. OLD resolution with tabulation. In Ehud Shapiro, editor, Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, pages 84–98, London, 1986. Springer-Verlag.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems. Volume I: Classical Database Systems. Computer Science Press, 1988.
Moshe Y. Vardi. The implication and finite implication problems for typed template dependencies. Journal of Computer and System Sciences, 28(1):3–28, February1984.
L. Vielle. Recursive axioms in deductive databases: The query-sub query approach. In 1st Conference on Expert Database Systems, Kerschberg (ed), April1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coulondre, S. (2000). Chasing Relational Database Constraints Backwards. In: Ibrahim, M., Küng, J., Revell, N. (eds) Database and Expert Systems Applications. DEXA 2000. Lecture Notes in Computer Science, vol 1873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44469-6_17
Download citation
DOI: https://doi.org/10.1007/3-540-44469-6_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67978-3
Online ISBN: 978-3-540-44469-5
eBook Packages: Springer Book Archive