[
Lists Home |
Date Index |
Thread Index
]
Henry, this is very neat, and excellent. As the others later pointed out,
this shows that arbitrary usages of ID/IDREFs is not good.
However, the NP completeness result is not true if we do not allow #FIXED
attributes. Also I will argue that ID/IDREF can be used analogously to
key-foreign keys in RDBs. We know that checking whether there exists a
non-empty instance is trivially satisfiable for relational databases (I am
very sure). For XML, it becomes more complicated because the content of an
element eventually becomes relationships.
Anyways, this thread is very interesting. Looking to hear more.
cheers and regards - murali.
On 28 Mar 2003, Henry S. Thompson wrote:
> Somewhat surprisingly, it turns out that answering the question, for an
> arbitrary XML DTD, "Are there any valid instances of the document type
> defined by this DTD?", is an NP-hard problem.
>
> This is true, because it is possible to encode a 3SAT problem [1] in a
> DTD, so that there is an instance of the DTD's document type iff the
> problem can be satisfied. So finding a valid instance is as hard a
> problem as solving the 3SAT problem, and 3SAT is known to be NP-hard.
>
> Here's the DTD for a 4-variable, 3-clause example. The 'clauses'
> element is the encoding of the 3SAT problem
>
> (v1 | -v2 | v3) & (-v1 | v3 | v4 ) & (v2 | -v3 | -v4)
>
> The complexity arises in finding a set of values for the 'value' IDs
> of the children of <bindings> which are consistent with some sequence of
> choices from the <clauses>.
>
> The choices interspersed among the value bindings ensure that every
> variable gets exactly one binding, which in turn makes it impossible
> to choose <v2n> for one clause and <v2y> for the other, without
> causing an IDREF failure.
>
> <!ELEMENT root (bindings, clauses)>
>
> <!ELEMENT bindings (v1, (v1y|v1n) , v2, (v2y|v2n),
> v3, (v3y|v3n) , v4, (v4y|v4n))>
>
> <!ELEMENT clauses (( v1y | v2n | v3y ) ,
> ( v1n | v3y | v4y ) ,
> ( v3n | v4n | v2y ))>
>
> <!ELEMENT v1 EMPTY>
> <!ATTLIST v1 value ID #REQUIRED>
> <!ELEMENT v2 EMPTY>
> <!ATTLIST v2 value ID #REQUIRED>
> <!ELEMENT v3 EMPTY>
> <!ATTLIST v3 value ID #REQUIRED>
> <!ELEMENT v4 EMPTY>
> <!ATTLIST v4 value ID #REQUIRED>
>
> <!ELEMENT v1y EMPTY>
> <!ATTLIST v1y value IDREF #FIXED "v1true">
> <!ELEMENT v1n EMPTY>
> <!ATTLIST v1n value IDREF #FIXED "v1false">
> <!ELEMENT v2y EMPTY>
> <!ATTLIST v2y value IDREF #FIXED "v2true">
> <!ELEMENT v2n EMPTY>
> <!ATTLIST v2n value IDREF #FIXED "v2false">
> <!ELEMENT v3y EMPTY>
> <!ATTLIST v3y value IDREF #FIXED "v3true">
> <!ELEMENT v3n EMPTY>
> <!ATTLIST v3n value IDREF #FIXED "v3false">
> <!ELEMENT v4y EMPTY>
> <!ATTLIST v4y value IDREF #FIXED "v4true">
> <!ELEMENT v4n EMPTY>
> <!ATTLIST v4n value IDREF #FIXED "v4false">
>
>
> There is at least one solution:
>
> <!DOCTYPE root SYSTEM "3sat.dtd">
> <root>
> <bindings>
> <v1 value="v1false"/><v1n/>
> <v2 value="v2false"/><v2n/>
> <v3 value="v3false"/><v3n/>
> <v4 value="v4false"/><v4n/>
> </bindings>
> <clauses>
> <v2n/>
> <v1n/>
> <v3n/>
> </clauses>
> </root>
>
> Henry S. Thompson
> Richard Tobin
>
> [1] http://www.wikipedia.org/siki/Satisfiability_problem
> --
> Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
> Half-time member of W3C Team
> 2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
> Fax: (44) 131 650-4587, e-mail: ht@cogsci.ed.ac.uk
> URL: http://www.ltg.ed.ac.uk/~ht/
> [mail really from me _always_ has this .sig -- mail without it is forged spam]
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://lists.xml.org/ob/adm.pl>
>
|
