[en] Traditionally, dependency theory has been developed for uninterpreted data. Specifically, the only assumption that is made about the data domains is that data values can be compared for equality. However, data is often interpreted and there can be advantages in considering data as such, for instance, obtaining more compact representations as is done in constraint databases. This paper considers dependency theory in the context of interpreted data. Specifically, it studies constraint-generating dependencies. These are a generalization of equality-generating dependencies where equality requirements are replaced by constraints on an interpreted domain. The main technical results in the paper are a general decision procedure for the implication and consistency problems for constraint-generating dependencies and complexity results for specific classes of such dependencies over given domains. The decision procedure proceeds by reducing the dependency problem to a decision problem for the constraint theory of interest and is applicable as soon as the underlying constraint theory is decidable. The complexity results are, in some cases, directly lifted from the constraint theory; in other cases, optimal complexity bounds are obtained by taking into account the specific form of the constraint decision problem obtained by reducing the dependency implication problem. (C) 1999 Academic Press.
Disciplines :
Computer science
Author, co-author :
Baudinet, Marianne
Chomicki, Jan
Wolper, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (parallélisme et banques de données)
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Aspvall B., Plass M., Tarjan R. A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8:1979;121-123.
M. Baudinet, Temporal logic programming is complete and expressive, in Sixteenth Association for Computing Machinery Symposium on Principles of Programming Languages, Austin, Texas, January 1989, pp. 267-280.
Baudinet M. On the expressiveness of temporal logic programming. Inform. and Comput. 117:1995;157-180.
Baudinet M., Chomicki J., Wolper P. Temporal deductive databases. Tansel A., Clifford J., Gadia S., Jajodia S., Segev A., Snodgrass R. Temporal Databases. Theory, Design, and Implementation. 1993;294-320 Benjamin-Cummings, Redwood City.
M. Baudinet, M. Niézette, and P. Wolper, On the representation of infinite temporal data and queries, in Tenth Association for Computing Machinery Symposium on Principles of Database Systems, Denver, Colorado, May 1991, pp. 280-290,.
Beeri C., Vardi M. A proof procedure for data dependencies. J. Assoc. Comput. Mach. 31:1984;718-741.
Benedikt M., Dong G., Libkin L., Wong L. Relational expressive power of constraint query languages. J. Assoc. Comput. Mach. 45:1998;1-34.
Brodsky A., Jaffar J., Maher M. J. Towards practical constraint databases. Constraints. 2:1997;279-304.
A. Brodsky, C. Lassez, and, J.-L. Lassez, Separability of polyhedra for optimal filtering of spatial and constraint data, in, Fourteenth Association for Computing Machinery Symposium on Principles of Databases Systems, San Jose, California, May 1995.
J. Chomicki, Polynomial time query processing in temporal deductive databases, in Ninth Association for Computing Machinery on Principles of Database Systems, Nashville, Tennessee, April 1990, pp. 379-391.
J. Chomicki and T. Imieliński, Temporal deductive databases and infinite objects, in Seventh Association for Computing Machinery Symposium on Principles of Database Systems, Austin, Texas, March 1988, pp. 61-73.
Chomicki J., Imieliński T. Finite representation of infinite query answers. ACM Trans. Database Systems. 18:1993;181-223.
Cox J., McAloon K. Decision procedures for constraint based extensions of Datalog. Benhamou F., Colmerauer A. Constraint Logic Programming: Selected Research. 1993;MIT Press, Cambridge.
Garey M. R., Johnson D. S. Computer and Intractability: A Guide to the Theory of NP-Completeness. 1979;Freeman, New York.
Ginsburg S., Hull R. Order dependency in the relational model. Theoret. Comput. Sci. 26:1983;149-195.
Ginsburg S., Hull R. Sort sets in the relational model. J. Assoc. Comput. Mach. 33:1986;465-488.
S. Grumbach and J. Su, First-order definability over constraint databases, in Principles and Practice of Constraint Programming, First International Conference, CP'95, Cassis, France, September 1995, Lecture Notes in Computer Science, Vol. 976, pp. 121-136, Springer-Verlag, Berlin/New York.
Grumbach S., Su J. Finitely, Representable databases. J. Comput. System Sci. 55:1997;273-298.
Grumbach S., Su J. Queries with arithmetical constraints. Theor. Comput. Sci. 173:1997;151-181.
Guo S., Sun W., Weiss M. A. Solving satisfiability and implication problems in database systems. ACM Trans. Database Systems. 21:1996;270-293.
A. Gupta, Y. Sagiv, J. D. Ullman, and J. Widom, Constraint checking with partial information, in Thirteenth Association for Computing Machinery Symposium on Principles of Database Systems, Minneapolis, Minnesota, May 1994, pp. 45-55.
N. S. Ishakbeyoglu and Z. M. Oszoyoglu, On the maintenance of implication integrity constraints, in Fourth International Conference on Database and Expert Systems Applications, Prague, September 1993, Lecture Notes in Computer Science, Vol. 720, pp. 221-232, Springer-Verlag, Berlin/New York.
Jensen C., Snodgrass R. Temporal specialization and generalization. IEEE Trans. Knowledge Data Engineering. 6:1994;954-974.
Kabanza F., Stévenne J.-M., Wolper P. Handling infinite temporal data. J. Comput. System Sci. 51:1995;3-17.
Kannellakis P., Kuper G., Revesz P. Constraint query languages. J. Comput. System Sci. 51:1995;26-52.
P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter, Indexing for data models with constraints and classes, in Twelfth Association for Computing Machinery Symposium on Principles of Database Systems, Washigton, DC, May 1993, pp. 233-243.
M. Koubarakis, Complexity results for first-order theories of temporal constraints, in Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR'94), May 1994, pp. 379-390.
Koubarakis M. Database models for infinite and indefinite temporal information. Inform. Systems. 19:1994;141-174.
Koubarakis M. The complexity of query evaluation in indefinite temporal constraint databases. Theoret. Comput. Sci. 171:1997;25-60.
Maher M. J. Constrained dependencies. Theor. Comput. Sci. 173:1997;113-149.
M. J. Maher, and, D. Srivastava, Chasing constrained tuple-generating dependencies, in, Fifteenth Association for Computing Machinery Symposium on Principle of Database Systems, Montreal, Canada, June 1996, ACM Press.
Maier D. The Theory of Relational Databases. 1983;Comput. Sci. Press, New York.
Revesz P. Z. A closed-form evaluation for datalog queries with integer (gap)-order constraints. Theor. Comput. Sci. 116:1993;117-149.
Rosenkrantz D., Hunt H. B. I. Processing conjunctive predicates and queries. International Conference on Very Large Data Bases. 1980;. p. 64-72.
Schrijver A. Theory of Linear and Integer Programming. 1986;Wiley, New York.
Srivastava D. Subsumption and indexing in constraint query languages with linear arithmetic constraints. Ann. Math. and Artificial Intelligence. 1993.
A. P. Stolboushkin and M. A. Taitslin, Linear vs. order constraint queries over rational databases, in Fifteenth Association for Computing Symposium on Principle of Database Systems, Montreal, Canada, June 1996, pp. 17-27, ACM Press.
Sun W., Weiss M. A. An efficient algorithm for testing implication involving arithmetic inequalities. IEEE Trans. Knowledge and Data Eng. 6:1994;997-1001.
Thalheim B. Dependencies in relational databases. Teubner-Texte Math. 1991;Teubner, Stuttgart.
Toman D., Chomicki J. Datalog with integer periodicity constraints. J. Logic Programming. 35:1998;263-290.
Toman D. Memoing evaluation for constraint extensions of datalog. Constraints. 2:1998;337-359.
Ullman J. D. Principles of Database and Knowledge-Base Systems. Volume II: The New Technologies. 1989;Comput. Sci. Press, New York.
van der Meyden R. The complexity of querying indefinite data about linearly ordered domains. J. Comput. System Sci. 54:1997;113-135.
X. Zhang, and, Z. M. Ozsoyoglu, On efficient reasoning with implication constraints, in, Third International Conference on Deductive and Object-Oriented Databases, Phoenix, Arizona, December 1993.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
