iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/S10844-012-0216-5
A sound and complete chase procedure for constrained tuple-generating dependencies | Journal of Intelligent Information Systems Skip to main content
Springer Nature Link
Log in

A sound and complete chase procedure for constrained tuple-generating dependencies

  • Published:
Journal of Intelligent Information Systems Aims and scope Submit manuscript

Abstract

We present a chase procedure for solving the implication problem of constrained tuple-generating dependencies (ctgds), a general class of database dependencies that is also able to handle data and predicates on interpreted domains. Current chase procedures for ctgds are sound but not complete, in the sense that they are unguaranteed to stop successfully whenever implication is true. The procedure we present is sound and complete, the first to our knowledge. It follows a linear reasoning over constraint domains that have the Independence of Negative Constraints property. We then soundly extend this procedure by a disjunctive reasoning over unrestricted constraint domains. To achieve these results, we used a different approach. Previous chases act like a closure operator, whereas we used a goal-directed design.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Notice the double meaning of the word constraint. From now on, this word will no more mean integrity constraints, but instead semantic relations on variables, interpreted on a given domain (i.e. linear arithmetic constraints, order constraints, sets constraints, etc.)

References

  • Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D. (1986). Magic sets and other strange ways to implement logic programs. In Proc. 5th ACM symposium on principles of database systems (pp. 1–15). Cambridge, Massachusetts, USA, 24–26 Mar 1986.

  • Baudinet, M., Chomicki, J., Wolper, P. (1995). Constraint-generating dependencies. In Proc. 5th international conference on database theory. Prague, Czech Republic, 11–13 Jan 1995.

  • Baudinet, M., Chomicki, J., Wolper, P., (1999). Constraint-generating dependencies. Journal of Computer and System Sciences, 59(1), 94–115.

    Article  MathSciNet  MATH  Google Scholar 

  • Beeri, C., & Vardi, M.Y. (1984). A proof procedure for data dependencies. Journal of the ACM, 31(4), 718–741.

    Article  MathSciNet  MATH  Google Scholar 

  • Bohannon, P., Fan, W., Geerts, F., Jia, X., Kementsietsidis, A. (2007). Conditional functional dependencies for data cleaning. In Proc. 23rd international conference on data engineering, ICDE 2007 (pp. 746–755). Istanbul, Turkey, 15–20 Apr 2007.

  • Bravo, L., Fan, W., Ma, S. (2007). Extending dependencies with conditions. In Proceedings of the 33rd international conference on very large data bases (VLDB Endowment, 2007), VLDB ’07, pp. 243–254. http://dl.acm.org/citation.cfm?id=1325851.1325882.

  • Coulondre, S. (2003). A top-down proof procedure for generalized data dependencies. Acta Informatica, 39(1), 1–29.

    Article  MathSciNet  MATH  Google Scholar 

  • Deutsch, A., Ludäscher, B., Nash, A. (2005). Rewriting queries using views with access patterns under integrity constraints. In Proc. 10th int. conf. on database theory. Edinburgh, UK, 5–7 Jan 2005.

  • Deutsch, A., Nash, A., Remmel, J.B. (2008). The chase revisited. In Proc. 27th ACM symposium on principles of database systems. Vancouver, BC, Canada, 9–11 June 2008.

  • Deutsch, A., & Tannen, V. (2003). Reformulation of XML queries and constraints. In Proc. 9th int. conf. on database theory. Siena, Italy, 8–10 Jan 2003.

  • Fagin, R., Kolaitis, P.G., Nash, A., Popa, L. (2008). Towards a theory of schema-mapping optimization. In Proc. 27th ACM symposium on principles of database systems. Vancouver, BC, Canada, 9–11 June 2008.

  • Fagin, R., Kolaitis, P.G., Popa, L. (2003). Data exchange: getting to the core. In Proc. 22th ACM symposium on principles of database systems. San Diego, CA, USA, 9–12 June 2003.

  • Fan, W., Geerts, F., Jia, X., Kementsietsidis, A. (2008). Conditional functional dependencies for capturing data inconsistencies. ACM Transactions on Database Systems, 33(2), 6:1–6:48.

    Article  Google Scholar 

  • Fan, W., Li, J., Tang, N., Yu, W. (2012). Incremental detection of inconsistencies in distributed data. In ICDE, (pp. 318–329).

  • Fuxman, A., Hernández, M.A., Ho, C.T.H., Miller, R.J., Papotti, P., Popa, L. (2006). Nested mappings: schema mapping reloaded. In Proc. 32nd international conference on very large data bases. Seoul, Korea, 12–15 Sept 2006.

  • Gottlob, G., & Nash, A. (2006). Data exchange: computing cores in polynomial time. In Proc. 25th ACM symposium on principles of database systems. Chicago, Illinois, USA, 26–28 June 2006.

  • Jafar, J., & Maher, M. (1994). Constraint logic programming: a survey. Journal of Logic Programming, 19/20, 503–581.

    Article  Google Scholar 

  • Kanellakis, P.C., Kuper, G.M., Revesz, P.Z. (1990). Constraint query languages. In Proc. 9th ACM symposium on principles of database systems. Nashville, Tennessee, 2–4 Apr 1990.

  • Lassez, J.L., & McAloon, K. (1989). Independence of negative constraints. In Proc. international joint conference on theory and practice of software development. Barcelona, Spain, 13–17 Mar 1989.

  • Maher, M.J. (1993). A logic programming view of CLP. In Proc. 10th international conference on logic programming. Budapest, Hungary, 21–25 June 1993.

  • Maher, M.J. (1995). Constrained dependencies. In Proc. first international conference on principles and practice of constraint programming (pp. 170–185). Cassis, France, 19–22 Sep 1995.

  • Maher, M.J., & Srivastava, D. (1996). Chasing constrained tuple-generating dependencies. In Proc. 15th ACM Symposium on Principles of Database Systems. Montreal, Canada, 3–5 June 1996.

  • Salvat, E., & Mugnier, M.L. (1996). Sound and Complete Forward and backward Chaining of Graph Rules. In Proc. 4th international conference on conceptual structures (pp. 248–262). Sydney, Australia, 19–22 Aug 1996.

  • Sowa, J.F. (1984). Conceptual structures: Information processing in mind and machine. Addison-Wesley.

  • Wang, J., Topor, R.W., Maher, M.J. (2001). Reasoning with disjunctive constrained tuple-generating dependencies. In Proc. 12th international conference on database and expert systems applications. Munich, Germany, 3–5 Sept 2001.

Download references

Author information

Authors and Affiliations

  1. CNRS, INSA-Lyon, LIRIS, UMR5205, Université de Lyon, 69621, Lyon, France

    Deming Dou & Stéphane Coulondre

Authors
  1. Deming Dou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stéphane Coulondre
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deming Dou.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dou, D., Coulondre, S. A sound and complete chase procedure for constrained tuple-generating dependencies. J Intell Inf Syst 40, 63–84 (2013). https://doi.org/10.1007/s10844-012-0216-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10844-012-0216-5

Keywords

Search

Navigation