Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/17775
Title: | On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements | Authors: | GYSSENS, Marc Niepert, Mathias Van Gucht, Dirk |
Issue Date: | 2014 | Publisher: | ELSEVIER SCIENCE BV | Source: | INFORMATION PROCESSING LETTERS, 114 (11), p. 628-633 | Abstract: | Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A, B vertical bar C), with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of S. Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones. (C) 2014 Elsevier B.V. All rights reserved. | Notes: | [Gyssens, Marc] Hasselt Univ, B-3500 Hasselt, Belgium. [Gyssens, Marc] Transnat Univ Limburg, Fac Sci, B-3500 Hasselt, Belgium. [Niepert, Mathias] Univ Washington, Paul G Allen Ctr, Dept Comp Sci & Engn, Seattle, WA 98195 USA. [Van Gucht, Dirk] Indiana Univ, Div Comp Sci, Bloomington, IN 47405 USA. marc.gyssens@uhasselt.be; mniepert@cs.washington.edu; vgucht@cs.indiana.edu | Keywords: | Conditional independence statement; Saturated conditional independence statement; Axiom system; Semigraphoid axioms; Soundness; Completeness; Databases;conditional independence statement; saturated conditional independence; statement; axiom system; semigraphoid axioms; soundness; completeness; databases | Document URI: | http://hdl.handle.net/1942/17775 | ISSN: | 0020-0190 | e-ISSN: | 1872-6119 | DOI: | 10.1016/j.ipl.2014.05.010 | ISI #: | 000340324300008 | Rights: | © 2014 Elsevier B.V. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2015 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
gyssens 1.pdf Restricted Access | Published version | 360.67 kB | Adobe PDF | View/Open Request a copy |
semigraphoids-ipl.pdf | 297.92 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
9
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
11
checked on Sep 20, 2024
Page view(s)
110
checked on Sep 5, 2022
Download(s)
260
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.