×

zbMATH — the first resource for mathematics

Constrained dependencies. (English) Zbl 0902.68042
Summary: We extend the notions of functional and finiteness dependencies to apply to subsets of a relation that are specified by constraints. These dependencies have many applications. We are able to characterize those constraint domains which admit a polynomial time solution of the implication problem (assuming \(P\neq NP\)) and give an efficient algorithm for these cases, modulo the cost of constraint manipulation. For other cases we offer approximate algorithms. Finally, we outline some applications of these dependencies to the analysis and optimization of CLP programs and database queries.

MSC:
68P15 Database theory
Software:
XSB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K.R.; Gabbrielli, M., Declarative interpretations reconsidered, ()
[2] Armstrong, T.; Marriott, K.; Schachte, P.; Søndergaard, H., Boolean functions for dependency analysis: algebraic properties and efficient representation, (), 266-280
[3] Bagnara, R., A hierarchy of constraint systems for data-flow analysis of constraint logic-based languages, (1995), manuscript
[4] Baudinet, M.; Chomicki, J.; Wolper, P., Constraint-generating dependencies, (), 322-337
[5] Beeri, C.; Bernstein, P.A., Computational problems related to the design of normal form relational schemas, ACM trans. database systems, 4, 30-59, (1979)
[6] Braem, C.; Le Charlier, B.; Modart, S.; Van Hentenryck, P., Cardinality analysis of prolog, (), 457-471
[7] Chakravarthy, U.S.; Grant, J.; Minker, J., Foundations of semantic query optimization for deductive databases, (), 243-274
[8] Codish, M.; Dams, D.; Yardeni, E., Bottom-up abstract interpretation of logic programs, Theoret. comput. sci., 124, 93-125, (1994) · Zbl 0795.68038
[9] Dart, P., On derived dependencies and connected databases, J. logic programming, 11, 163-188, (1991) · Zbl 0735.68023
[10] De Bra, P.; Paredaens, J., Horizontal decomposition for handling exceptions to functional dependencies, (), 123-141
[11] Debray, S.K.; Ramakrishnan, R., Abstract interpretation of logic programs using magic transformations, J. logic programming, 18, 149-176, (1994) · Zbl 0795.68037
[12] Debray, S.K.; Warren, D.S., Functional computations in logic programs, ACM trans. programming languages systems, 11, 451-481, (1989)
[13] Elkan, C., A decision procedure for conjunctive query disjointness, (), 134-139
[14] Elkan, C., Independence of logical database queries and updates, (), 154-160
[15] Falaschi, M.; Levi, G.; Martelli, M.; Palamidessi, C., A new declarative semantics for logic languages, () · Zbl 0699.68113
[16] Gabbrielli, M.; Levi, G., Modeling answer constraints in constraint logic programs, (), 238-252
[17] Gao, H.; Warren, D.S., A powerful evaluation strategy for CLP programs, (), 92-99
[18] Jaffar, J.; Lassez, J.-L., Constraint logic programming, (), 111-119
[19] Jaffar, J.; Maher, M.J., Constraint logic programming: a survey, J. logic programming, 19 & 20, 503-581, (1994)
[20] Kanellakis, P., Elements of relational database theory, (), 1073-1156 · Zbl 0900.68090
[21] P. Kanellakis, G. Kuper and P. Revesz, Constraint query languages, J. Comput. System Sci., to appear.
[22] Kemp, D.; Stuckey, P., Analysis based constraint query optimization, (), 666-682
[23] Klug, A., Calculating constraints on relational expressions, ACM trans. database systems, 5, 260-290, (1980) · Zbl 0441.68119
[24] Lassez, J.-L.; McAloon, K., A constraint sequent calculus, (), 52-62
[25] Lassez, J.-L.; McAloon, K., A canonical form for generalized linear constraints, J. symbolic comput., (1992) · Zbl 0745.90046
[26] Maher, M.J., A logic programming view of CLP, (), 737-753
[27] Maher, M.J.; Ramakrishnan, R., Déjà vu in fixpoints of logic programs, (), 963-980
[28] Maher, M.J.; Ramakrishnan, R., Déjà vu in fixpoints of logic programs, (), 963-980, manuscript
[29] Maher, M.; Srivastava, D., Chasing constrained tuple-generating dependencies, ()
[30] Marriott, K.; Sondergaard, H., Notes for a tutorial on abstract interpretation of logic programs, (1989), distributed at NACLP
[31] van der Meyden, R., The complexity of querying indefinite data about linearly ordered domains, (), 331-345 · Zbl 0876.68035
[32] Paredaens, J.; De Bra, P.; Gyssens, M.; Van Gucht, D., The structure of the relational database model, () · Zbl 0669.68060
[33] R. Ramakrishnan, personal communication, 1993.
[34] Ramakrishnan, R.; Bancilhon, F.; Silberschatz, A., Safety of recursive Horn clauses with infinite relations, (), 328-339
[35] Sagonas, K.; Swift, T.; Warren, D.S., XSB as an efficient deductive database engine, SIGMOD record, (1994)
[36] Srivastava, D., Subsumption and indexing in constraint query languages with linear arithmetic constraints, Ann. math. artifi. intell., 8, 315-343, (1993) · Zbl 1034.68516
[37] Vardi, M., Fundamentals of dependency theory, IBM research report RJ4858, (1985)
[38] Wang, X.S.; Bettini, C.; Brodsky, A.; Jajodia, S., Logical design for temporal databases with multiple granularities, (1995), manuscript
[39] Zhang, X.; Ozsoyoglu, Z.M., On efficient reasoning with implication constraints, (), 236-252
[40] Zhang, X.; Ozsoyoglu, Z.M., Some results on the containment and minimization of (in)equality queries, Inform. processing lett., 50, 259-267, (1994) · Zbl 0796.68082
[41] Ziarko, W., The discovery, analysis and representation of data dependencies in databases, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.