nach oben

Journal of Intelligent Information Systems

Erschienen in:

01.02.2013

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

verfasst von: Deming Dou, Stéphane Coulondre

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 1/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Content-based and collaborative techniques for tag recommendation: an empirical evaluation

Nächster Artikel Automatic discovery of Web Query Interfaces using machine learning techniques

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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.)

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.MathSciNetMATHCrossRef

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

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.MathSciNetMATHCrossRef

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.CrossRef

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.CrossRef

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.

Titel: A sound and complete chase procedure for constrained tuple-generating dependencies
verfasst von: Deming Dou
Stéphane Coulondre
Publikationsdatum: 01.02.2013
Verlag: Springer US
Erschienen in: Journal of Intelligent Information Systems / Ausgabe 1/2013
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-012-0216-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2013

Content-based and collaborative techniques for tag recommendation: an empirical evaluation

Clustering interval data through kernel-induced feature space

Fiducial feature reduction analysis for electrocardiogram (ECG) based biometric recognition

Automatic discovery of Web Query Interfaces using machine learning techniques

E-FFC: an enhanced form-focused crawler for domain-specific deep web databases

NODAR: mining globally distributed substructures from a single labeled graph