dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values.

Frank Shou-Cheng Tseng, Arbee L. P. Chen, Wei-Pang Yang: Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values. VLDB J. 2(4): 489-512(1993)
@article{DBLP:journals/vldb/TsengCY93,
  author    = {Frank Shou-Cheng Tseng and
               Arbee L. P. Chen and
               Wei-Pang Yang},
  title     = {Searching a Minimal Semantically-Equivalent Subset of a Set of
               Partial Values},
  journal   = {VLDB J.},
  volume    = {2},
  number    = {4},
  year      = {1993},
  pages     = {489-512},
  ee        = {http://www.vldb.org/journal/VLDBJ2/P489.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Imprecise data exist in databases due to their unavailability or to data/schema incompatibilities in a multidatabase system. Partial values have been used to represent imprecise data. Manipulation of partial values is therefore necessary to process queries involving imprecise data. In this article, we study the problem of eliminating redundant partial values that result from a projection on an attribute with partial values. The redundancy of partial values is defined through the interpretation of a set of partial values. This problem is equivalent to searching a minimal semantically-equivalent subset of a set of partial values. A semantically-equivalent subset contains exactly the same information as the original set. We derive a set of useful properties and apply a graph matching technique to develop an efficient algorithm for searching such a minimal subset and therefore eliminating redundant partial values. By this process, we not only provide a concise answer to the user, but also reduce the communication cost when partial values are requested to be transmitted from one site to another site in a distributed environment. Moreover, further manipulation of the partial values can be simplified. This work is also extended to the case of multi-attribute projections.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Imprecise data, minimal elements, multidatabase systems, partial values, bipartite graph, graph matching.

References

[Abiteboul & Grahne 1985]
Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon & Spyratos 1981]
François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Biskup 1983]
Joachim Biskup: A Foundation of Codd's Relational Maybe-Operations. ACM Trans. Database Syst. 8(4): 608-636(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bondy & Murty 1976]
...
[Codd 1979]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Codd 1986]
E. F. Codd: Missing Information (Applicable and Inapplicable) in Relational Databases. SIGMOD Record 15(4): 53-78(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Codd 1987]
E. F. Codd: More Commentary on Missing Information in Relational Databases (Applicable and Inapplicable Information). SIGMOD Record 16(1): 42-50(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeMichiel 1989]
Linda G. DeMichiel: Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains. IEEE Trans. Knowl. Data Eng. 1(4): 485-493(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ford & Fulkerson 1962]
...
[Garey & Johnson 1979]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Grant 1977]
John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Grant 1979]
John Grant: Partial Values in a Tabular Database Model. Inf. Process. Lett. 9(2): 97-99(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hall 1935]
...
[Hopcroft & Karp 1973]
John E. Hopcroft, Richard M. Karp: An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4): 225-231(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Imielinski & Lipski 1981]
Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Imielinski & Lipski 1983]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information and Dependencies in Relational Databases. SIGMOD Conference 1983: 178-184 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Imielinsky & Vadaparty 1989]
Tomasz Imielinski, Kumar V. Vadaparty: Complexity of Query Processing in Databases with OR-Objects. PODS 1989: 51-65 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Imielinsky 1991]
...
[Lewis & Papadimitriou 1981]
...
[Lien 1979]
Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lipski 1979]
Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Liu & Sunderraman 1990]
Ken-Chih Liu, Rajshekhar Sunderraman: Indefinite and Maybe Information in Relational Databases. ACM Trans. Database Syst. 15(1): 1-39(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Liu & Sunderraman 1991]
Ken-Chih Liu, Rajshekhar Sunderraman: A Generalized Relational Model for Indefinite and Maybe Information. IEEE Trans. Knowl. Data Eng. 3(1): 65-77(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Maier 1983]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Motro 1990]
Amihai Motro: Accommodating Imprecision in Database Systems: Issues and Solutions. SIGMOD Record 19(4): 69-74(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Papadimitriou & Steiglitz 1982]
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Suppes 1960]
...
[Tsai & Chen 1993]
Pauray S. M. Tsai, Arbee L. P. Chen: Querying Uncertain Data in Heterogeneous Databases. RIDE-IMS 1993: 161-168 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tseng et al. 1993a]
Frank Shou-Cheng Tseng, Arbee L. P. Chen, Wei-Pang Yang: Answering Heterogeneous Database Queries with Degrees of Uncertainty. Distributed and Parallel Databases 1(3): 281-302(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tseng et al. 1993b]
...
[Tseng et al. 1993c]
...
[Ullman 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vassiliou 1979]
Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vassiliou 1980]
Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:08 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page