Qual è il miglior modello di dati per rappresentare l'intervallo matematico (in database, xml, json ...)?

Se lavori esclusivamente con intervalli di numeri interi, probabilmente stai pensando troppo al problema. Tutto ciò che serve per memorizzare è il limite inferiore e il limite superiore e utilizzare una regola fissa per stabilire se i limiti sono inclusivi. Ad esempio, le gamme Python tendono a utilizzare un intervallo semichiuso, in modo che:

range(5,10)

È ciò che i matematici avrebbero scritto come:

[5, 10)         # interval notation
5 <= x < 10     # inequality notation
5, 6, 7, 8, 9   # list notation

Questo è facilmente codificato in XML, JSON, o valori di database. Per esempio:.

<range low="5" high="10"/>   # XML
[5, 10]                      # simple list (brackets are data delimiters, 
                                            not mathematical interval notation)
{ "low": 5, "high": 10 }     # JSON fragment 

È molto facile prendere una serie fissa di regole, che sembra molto rigida, e recuperare ciò che vuoi. Ad esempio, se si desidera veramente che il limite massimo 10 sia incluso, non fornire un ulteriore macchinario di flessibilità e complessità (che richiede byte di codifica dati aggiuntivi, requisiti di test e complessità del codice). Basta codificarlo come:

<range low="5" high="11"/>  # XML

range(5, 11)                # Python

Se non ti piace l'asimmetria di un intervallo semiaperto, non c'è ragione per cui non puoi scegliere un intervallo completamente chiuso / compreso, o qualsiasi altra opzione (cioè, intervallo completamente aperto o semiaperto al intervallo di avvio). Il trucco sta nella scelta di una regola che sia coerente per tutto e che sia più coerente / conveniente con il tuo ambiente di programmazione.

Questa rappresentazione gestisce piacevolmente intervalli finiti. È molto compatto, può essere implementato in modo molto efficiente dal punto di vista delle prestazioni e, se desideri operazioni estese, può essere facilmente implementato come una classe pulita in Java, Python e in molti altri linguaggi.

Sembra anche che vogliate rappresentare insiemi discontinui e infiniti come x < 10 ∪ x > 40 . Questi non sono generalmente considerati "intervalli" dalla maggior parte dei linguaggi / sistemi di programmazione, e in effetti non sono nemmeno intervalli in senso matematico. Ma sono ovviamente interessanti concetti adiacenti da considerare - anche se aggiungerà una notevole complessità all'implementazione.

Ad esempio. il tuo set disgiunto può essere specificato come "multi-range", una combinazione di intervalli individuali:

<union>
    <range low="-Infinity" high="10"/>
    <range low="41" high="Infinity"/>
</union>

Ora hai dovuto aggiungere la gestione per i valori astratti (infinito negativo e positivo) e una combinazione di operazioni di combinazione ( union ) come costruttore a più intervalli. Ma ho letto la fonte di un certo numero di moduli numerici e multi-gamma, e questo è in realtà il modo in cui molti di loro lo fanno.

Quando si scende da questo percorso di generalizzazione da intervalli / intervalli individuali a serie multi-intervallo e multi-intervallo, si può anche iniziare a generalizzare le operazioni dell'insieme in altre formulazioni costruttive. Se fai union , perché non intersection , difference e symmetric-difference pure? Il tuo intervallo disgiunto potrebbe anche essere specificato alternativamente come:

<difference>
    <range low="-Infinity" high="Infinity"/>
    <range low="10" high="41"/>
</difference>

Ma devi stare attento, perché più operazioni e più complessità, maggiore possibilità di errori si insinuano.

In XSD, gli intervalli sono rappresentati utilizzando i quattro elementi minInclusive, maxInclusive, minExclusive, maxExclusive, ad esempio

<xs:restriction>
  <minExclusive="10"/>
  <maxInclusive="20"/>
</xs:restriction>

Nel mio design sperimentale FtanML ho preso questo approccio e l'ho semplificato a quattro attributi le, lt, ge, gt:

<integer gt=10 le=20>

Se adottiamo un approccio di modellazione dati pura, l'intervallo ha due proprietà, una minima e una massima, ognuna delle quali può essere assente, e ognuna delle quali, se presente, comprende un numero intero (il limite) e un valore booleano (indica se è consentito un valore pari al limite). Ciò potrebbe suggerire un design più pulito:

<range>
  <min limit="10" inclusive="true"/>
  <max limit="20" inclusive="false"/>
</range>

Ma a questo punto diventa chiaro che il miglior design dipende da cosa stai cercando di ottimizzare.

Inizia con la matematica in questione. Vuoi che il set sia chiuso sotto le operazioni che usi? Sicuramente sì, altrimenti non sarà utile. Quindi dovresti implementare: + e - infiniti, aperti e chiusi, un set vuoto e intervalli multi-intervallo.

L'archiviazione del database può procedere tramite un tipo di dati personalizzato (dovresti portare la tua logica di business al DB per recuperare, confrontare, ordinare e indicizzare in modo sano) o da una tabella separata in cui ogni intervallo atomico è memorizzato in 5 attributi (ID, tipo limite sinistro, valore limite sinistro, tipo con limite destro, valore limite destro).

L'archiviazione in-programma deve avere record che utilizzano gli stessi elementi, ma questa volta l'onere di indicizzazione è su di te - devi rendere il recupero / efficiente in ricerca (O (1) è la cosa migliore da avere) per essere in grado per elaborare ampie gamme disgiunte e operazioni algebriche / impostate su di esse.

Fonte: propria esperienza nell'implementazione di una libreria di opzioni operative per uso interno.

Hai bisogno di limiti sempre più alti e quale di questi due è inclusivo .

<lower inclusive="true">-50</lower>
<higher inclusive="false">100</higher

sarebbe l'intervallo [-50,100) .